[Java] Efficiente manier van opslag routes

[YopY]

Ik ben op het moment met een project van school bezig, een simulator van het een en ander. Een onderdeel daarvan is het berekenen van een route van punt A naar punt B. Ik heb zelf gekozen voor het gebruik van Waypoints, punten met een X, een Y, en een link naar zijn buur / buren.

Nu heb ik een recursieve functie geschreven die de snelste route uitrekent en deze opslaat als een LinkedList van Waypoints, welke het vehikel vervolgens gewoon af kan lopen. Tot zover werkt het.

Het probleem waar ik tegenaanloop is dat ik het ietsje optimaliseren wil. Door middel van het opslaan van de tijd in ms zie ik dat het berekenen van een route over 100 Waypoints ongeveer 300-600 ms duurt.

Om dit nu voor elke keer dat een route gereden moet worden te doen lijkt mij een beetje overkill, dus ik dacht, dat kan ik wel opslaan. Met andere woorden, ik op zoek naar een manier om een LinkedList op te slaan, met als indices de ID van het huidige en het ID van de doel-waypoint.

Klinkt eenvoudig, min of meer. Maar dat valt tegen . Ten eerste, je kunt een LinkedList niet opslaan in een array, laat staan een 2-d array. Alternatief is de LinkedList converteren naar een Array mbv de toArray functie, ook niet al te moeilijk.

Het probleem waar ik echter tegenaan loop is nogal extreem geheugengebruik. Er zijn op het moment ~3000 waypoints, met veel snijden valt dit wel met een paar honderd terug te brengen, maar ook dat zal niet werken. De array die ik op het moment gebruik is een 3-dimensionale array, met als index 1 de bron ID, index 2 de doel ID, en index 3 is dan de lijst met Waypoints (de route, op het moment max 500).

Om nu alle mogelijke combinaties op te slaan van punt A naar punt B heb ik 3000*3000*500 = 4.500.000.000 Waypoints nodig, wat, natuurlijk, veel te veel is.


Om alles nu samen te vatten: Wat is de beste manier zijn om een LinkedList zodanig op te slaan dat hij terug te vinden is door een bron ID en een doel ID op te geven, waar in ieder geval de routes tussen 3000 waypoints op te slaan zijn, zonder dat het al te veel geheugen gebruikt?


(Ik heb ook al een hashTable gebruikt, maar daar kon ik geen goede index voor vinden. Het gebruiken van een string als index (met bv de bron id en doel id als index) werkte niet, omdat hij de String als een andere zag dan er al in zat)

(Ook heb ik al met een leraar overlegd, die stelde de array methode voor. Deze gebruikt echter veel te veel geheugen)

(Ik vraag niet om het uiteindelijke antwoord, ik wil op het moment alleen maar suggesties en dergelijke voor de opslag)

(En als laatste, ik kan ook wel doen dat hij gewoon elke keer de route opnieuw uitrekent; met een beetje geluk komt het bijna nooit voor dat er veel (>10) routes in een kloktik (van een seconde) uitgerekend hoeven te worden)

[Janoz]

Veel korter dan die array kun je het niet krijgen. Wil je je waypoints onthouden dan zul je de waypoints moeten onthouden.

Je zou verder wel een hashmap kunnen gebruiken, maar dan zul je voor je key even een nieuwe class moeten maken (waarom je daarvoor een string wilt gebruiken snap ik helemaal niet).

Welk algoritme heb je gebruikt voor het berekenen van je korste pad? Ik vermoed dat je vind algoritme nog wel een heel stuk sneller kan (Dijkstra's shortest path bv).

[momania]

Hoe zoek je nu in je LinkedList? Maak je wel gebruik van bv de binarySearch ?

[Soultaker]

Janoz schreef op woensdag 10 januari 2007 @ 13:57:
Veel korter dan die array kun je het niet krijgen. Wil je je waypoints onthouden dan zul je de waypoints moeten onthouden.

Nee, je moet alleen bijhouden wat de kortste afstand van a naar b is. Dat is een 2-dimensionale matrix. De kortste route kun je dan reconstrueren door steeds een aangrenzend punt te kiezen dat minimale afstand heeft. (Als je wil kan ik dit nader toelichten.)

Je hebt dus niet meer dan O(n²) geheugen nodig; oftewel 3000² keer het datatype wat je gebruikt; zou iets van 34 MB voor ints/floats of het dubbele voor doubles moeten zijn. Als je het reconstrueren van routes efficiënter wil maken, is het aan te raden om bovendien op te slaan welk volgende punt bij elke kortste afstand hoort. Dat verdubbelt het geheugengebruik, maar je kunt een pad van lengte N dan in precies N stappen vinden.

momania schreef op woensdag 10 januari 2007 @ 14:02:
Hoe zoek je nu in je LinkedList? Maak je wel gebruik van bv de binarySearch ?

Je kunt geen (efficïente) binary search doen in een LinkedList; voor binary search heb je een random access container nodig en dat is een LinkedList nu juist niet. Als je optimaliseert voor geheugen kun je sowieso het beste geen LinkedLists gebruiken, maar gewoon arrays (of desnoods ArrayLists).

[Janoz]

Soultaker schreef op woensdag 10 januari 2007 @ 16:21:
[...]

Nee, je moet alleen bijhouden wat de kortste afstand van a naar b is. Dat is een 2-dimensionale matrix. De kortste route kun je dan reconstrueren door steeds een aangrenzend punt te kiezen dat minimale afstand heeft. (Als je wil kan ik dit nader toelichten.)

Klopt, maar dan ben je alsnog weer de route aan het "berekenen"^[1] (hoewel deze berekening nog een stuk efficienter is dan Dijkstra). Maar goed, dat is natuurlijk maar net waar je de grens legt tussen opslaan en uitrekenen. Je hebt helemaal gelijk, maar ik vermoed dat de topic starter op zoek was naar het opslaan van een lijst zonder het geheugengebruik van een lijst.

Verder vermoed ik (vanwege de vreemde naamgeving) dat TS nog erg weinig weet over grafen algoritmiek.

[1]Ik bedoel eigenlijk meer eht verschil tussen zoeken en oplepelen. Efficientie is nog steeds iets van N*M waarbij N de lengte van de route is en M het gemiddeld aantal buren per node

[ Voor 10% gewijzigd door Janoz op 10-01-2007 17:01 ]

[Soultaker]

Janoz schreef op woensdag 10 januari 2007 @ 16:59:
[1]Ik bedoel eigenlijk meer eht verschil tussen zoeken en oplepelen. Efficientie is nog steeds iets van N*M waarbij N de lengte van de route is en M het gemiddeld aantal buren per node

Daarom suggereerde ik al dat het handig is om ook op te slaan welk buurpunt bij het kortste pad hoort; dan is het echt O(N). Als je alleen het kortste pad wil weten (en je hoeft niet te weten hoe lang dat precies is) kun je vervolgens de hele afstandenmatrix weggooien. Je hebt dan alleen een routetabel van de vorm R[i][j] = k <=> het korste pad van i naar j loopt via k.

Een ruimte/tijd-tradeoff precies wat hier de bedoeling is, dacht ik, aangezien alle routes opslaan blijkbaar te veel gevraagd was. (Maar als je het toch probeert, blijf ik erbij dat je veel beter arrays dan LinkedLists kunt gebruiken.)

Janoz schreef op woensdag 10 januari 2007 @ 17:09:
Scheelt weer de previous en next pointer .

Volgens mij hebben objecten in Java nog veel meer overhead; denk aan dingen als een class pointer, een monitor, en een referentie die de garbage collector naar het object heeft. Een array heeft dat allemaal niet (of nauwkeuriger: slechts één keer voor de hele array). Verder is het helemaal erg als je ints in een LinkedList gaat opslaan, want elke unieke int moet dan naar een apart Integer object geconverteerd worden...

Als ik uit ga van deze site is een linked list van unieke Integer objecten ongeveer zes keer zo groot als de corresponderende array van ints. (Het voordeel van de linked list is natuurlijk dat je 'm handig kunt bewerken.)

[ Voor 32% gewijzigd door Soultaker op 10-01-2007 17:31 ]

[Janoz]

Scheelt weer de previous en next pointer .