[C#] Grote hoeveelheid XML inladen

[Leon-]

Als project voor school moeten wij een routeplanner maken van de campus in C#. We hebben de kaartdata in het formaat XML. Deze moeten wij dus op een slimme manier in gaan lezen en de kortste route gaan bepalen. Omdat het XML document uit ongeveer 30.000 regels code bestaat lijkt het ons niet slim om de DOM functionaliteit te gaan gebruiken, omdat we dan alle 30.000 regels code moeten gaan inlezen. Dus ook irrelevante data. Waar we ook rekening mee moeten houden is dat de campus uit meerdere gebouwen en meerdere verdiepingen bestaat.

We hebben het één en ander gebrainstormd en we kwamen tot het idee om een soort ‘a-star’ algoritme te gebruiken om de XML in te lezen. Hiermee bekijken we dus punt voor punt of het een mogelijkheid zou zijn voor de snelste route. Maar nu slaan wij een stap over, we gaan nu de snelste route al berekenen en tegelijkertijd de XML inladen. Dit is het dus nog niet helemaal.

Ook hebben het erover gehad om, om het begin- en eindpunt een vierkant te trekken en de data die daar binnen ligt in te laden. Maar dan kan het weer het geval zijn we bepaalde data niet inladen die we misschien toch nodig hebben? Misschien ligt de enige mogelijke route wel rondom de campus, en die data hebben we niet ingeladen.

Kan iemand ons een tip geven hoe we zouden moeten denken? Graag alleen tips en geen antwoorden.

Alvast bedankt.

[Hydra]

Kijk eens naar Sax parsers. Die werken op event basis in plaats van dat ze in een keer het hele DOM opbouwen. Random-access XML inlezen lijkt me niet handig, dan gaat het inlezen een bottleneck vormen lijkt me. 30k regels XML is niet bepaald iets waar je wakker van gaat liggen.

[ Voor 43% gewijzigd door Hydra op 11-03-2009 14:03 ]

[.oisyn]

kaartdata in XML formaat is natuurlijk sowieso onhandig om direct te gebruiken in je applicatie, ook al zou je het als DOM benaderen. Ik zou 'm eerst omzetten naar een datastructuur die je wel goed kunt handlen (en of je dat offline of online doet hangt een beetje van de use-case van je app af). Ik zou je algo iig zeker niet direct laten werken op de XML data.

[ Voor 10% gewijzigd door .oisyn op 11-03-2009 14:12 ]

[RobIII]

.oisyn schreef op woensdag 11 maart 2009 @ 14:11:
Ik zou je algo iig zeker niet direct laten werken op de XML data.

Seconded. Je wil gewoon eenmalig (bij het starten van de app of bij het initialiseren van het zoekalgoritme voor je 'm aan de gang zet of whatever) je data inlezen en daarna de XML links laten liggen. Aangenomen dat je onder "30.000 regels code" gewoon het aantal "regels" XML (of aantal nodes) verstaat en aangenomen dat die data niet al te gek is moet je dat easy in het geheugen kwijt kunnen in een optimalere structuur. Daar kan geen SAX of DOM tegen op

[ Voor 24% gewijzigd door RobIII op 11-03-2009 14:18 ]

[riezebosch]

RobIII schreef op woensdag 11 maart 2009 @ 14:16:
[...]

Seconded. Je wil gewoon eenmalig (bij het starten van de app of bij het initialiseren van het zoekalgoritme voor je 'm aan de gang zet of whatever) je data inlezen en daarna de XML links laten liggen. Aangenomen dat je onder "30.000 regels code" gewoon het aantal "regels" XML (of aantal nodes) verstaat en aangenomen dat die data niet al te gek is moet je dat easy in het geheugen kwijt kunnen in een optimalere structuur. Daar kan geen SAX of DOM tegen op

Maar dan nog kan je er voor kiezen om bij het parsen van je XML dit streaming te doen zodat je niet én je XML en je structuur compleet in het geheugen laadt.

[RobIII]

riezebosch schreef op woensdag 11 maart 2009 @ 14:23:
[...]

Maar dan nog kan je er voor kiezen om bij het parsen van je XML dit streaming te doen zodat je niet én je XML en je structuur compleet in het geheugen laadt.

Implementatiedetail

[Woy]

30.000 regels XML inlezen ( Om het in een gunstige datastructuur voor je algo te zetten ) is totaal geen probleem met de DOM die in het .NET framework gebruikt word.

Ik heb hier ook een verwerkingsprogramma draaien die XML files tot wel 250 MB inleest en verwerkt, en daar hebben we totaal geen performance problemen mee. Het is natuurlijk niet handig om je DOM je hele programma in je geheugen te houden.

Tuurlijk kun je het streaming gaan doen, maar zolang je niet tegen geheugen problemen oploopt zie ik er niet echt een groot probleem in.

[ Voor 5% gewijzigd door Woy op 11-03-2009 14:34 ]

[MrBucket]

Leon- schreef op woensdag 11 maart 2009 @ 14:01:
We hebben het één en ander gebrainstormd en we kwamen tot het idee om een soort ‘a-star’ algoritme te gebruiken om de XML in te lezen. Hiermee bekijken we dus punt voor punt of het een mogelijkheid zou zijn voor de snelste route. Maar nu slaan wij een stap over, we gaan nu de snelste route al berekenen en tegelijkertijd de XML inladen. Dit is het dus nog niet helemaal.

Klopt, dit is in veel gevallen niet de meest handige manier

Ik zou je willen aanraden om eerst een goede datastructuur te verzinnen waarmee je makkelijk kortste routes kunt bepalen (3D grid, graaf, ...?). Vervolgens vul je deze datastructuur met de informatie uit je xml-file, en voer je je zoekquery uit op de datastructuur. Zo heb je tijdens het zoeken geen last van het aangeleverde formaat (wat waarschijnlijk helemaal niet goed te doorzoeken is).

Wat betreft je 30.000 "regels" xml, dit is nog prima in een DOM te vouwen hoor. Stel dat elke node 100 bytes inneemt, dan neemt dit 3MB geheugen in. Aan de andere kant: als je de zoekstructuur gaat vullen zul je dit waarschijnlijk prima kunnen doen door sequentieel door alle nodes heen te wandelen, en daarvoor zou een XmlReader moeten volstaan