sinnvolles Speichern/Suchen von Objekten



  • Hallo,
    ich suche fachmännischen Rat.
    Ich implementiere im Moment den A*-Algorithmus. Er funktioniert auch wunderbar.
    Da er funktioniert würde ich nun gerne ein bisschen optimieren. Mein erster Gedanke ging an die Speicherung der "bekannten"-Kanten und der "Kanten mit bekannter kürzester Route".

    Da ihr euch nicht zwingend mit dem A* auskennen müsst um mir zu helfen, erkläre ich kurz was ich habe und was ich will:
    Im Moment speichere ich in einem Vector Objekte der Klasse Edge. Diese Edges haben intern unter anderem den Identifier gespeichert, der eine Kante eindeutig kennzeichnet, das Gewicht (z.B. die Länge in km).
    Die Anzahl der Edge-Objekte im Vektor kann sehr hoch werden.

    Es wird sehr oft im Vektor nach bestimmten Einträgen gesucht. Zum einen nach der Kante mit dem kleinsten Gewicht, zum anderen nach einer bestimmten Kante, falls vorhanden.

    Im Moment habe ich nur eine Methode, die von vorn nach hinten durch den Vektor iteriert, den entsprechenden Wert vergleicht und falls der Eintrag gefunden wurde diesen zurück gibt.

    Der Algorithmus ist nicht wirklich toll, da es eine Laufzeit von O(Anzahl der vorhandenen Kanten) hat.

    Ich denke das es für die Optimierung gut ist, hier anzufangen, da die Suche im Vektor die meiste Zeit einnimmt (denke ich zumindest). Es wird deutlich öfters nach einem existierenden Objekt gesucht wie nach dem kürzesten, weshalb ich diese Suche optimieren will - das durchiterieren bei der Suche nach dem kürzesten ist, bzw. muss dann verschmerzbar sein.

    Als erstes dachte ich daran, die ID zu hashen. Aber da ich nicht weiß wie viel Kanten kommen, müsste ich ein dynamisches Hashing machen.
    Oder ich baue mir einen Baum auf. Wenn da, welchen? B-Baum?
    Oder ich füge die Edges sortiert nach der ID in den Vektor ein. Damit hätte ich eine logarithmische Laufzeit beim Suchen.

    Würde gerne eure Meinung und eure Erfahrung hören, was ich am besten machen würde.
    Da die Ideen nur Gedanken sind und ich hier nur theoretisches Wissen habe, würde ich zwar versuchen das ganze dann best möglichst umzusetzen aber da ich nicht der erste bin, der sowas macht, wurde auch bei der Implementierung sicher schon viel Erfahrung gesammelt. Wenn ihr noch Umsetzung tipps hat, würde ich mich auch freuen.

    Vielen lieben Dank

    PS: Falls sich wer wundert wieso ich nicht mit Vertex arbeite sondern mit Edges: Mein A* ist bei mir Kanten basiert und nicht Knoten basiert wie üblich.



  • Ich würde - falls ich die Problemstellung richtig verstanden habe - den Vektor fertig befüllen, ihn dann nach ID's sortieren. Dann kannst Du für die Suche nach einem bestimmten anhand der ID identifizierbaren Element eine binäre Suche verwenden.
    Das Element mit der 'Kante mit dem kleinsten Gewicht' ist doch genau eines in dem ganzen Vektor, wenn ich das richtig verstehe. Das würde ich mir beim Befüllen des Vektors merken, also wenn ein Element hinzugefügt wird, prüfen, ob das Kantengewicht kleiner als das zuletzt gefundenen kleinste Kantengewicht ist, und ggf. die ID speichern.
    Wenn der Vektor befüllt ist, kann man dann einmal nach dieser ID suchen und von da an den Index speichern - das Element mit dem kleinsten Kantengewicht ist dann praktisch ständig verfügbar, die Suche nach einem Element kann binär erfolgen.



  • das mit der zusätzlichen Speicherung des kleinsten Elementes ist im Prinzip eine gute Idee. Aber dies wird auch immer wieder heraus gelöscht, weshalb danach eh wieder alle durchsucht werden müssen, um den aktuell kleinsten zu bekommen.

    Es läuft ungefähr so ab (Pseudo-Code mit Speicherung in nem Vektor):

    //Zum initialisieren:
    Es werden x-Kanten im Vektor gespeichert//eigentlich nie mehr wie 5
    
    while(noch nicht fertig)
    {
    	cheapestEdge = Kante mit dem kleinsten Gewicht die im Vektor gespeichert ist
    	löschen von cheapestEdge aus Vektor
    	for(alle Anschlusskanten von cheapestEdge) //eigentlich mehr wie 5
    	{
    		überprüfen ob Anschlusskante im Vektor vorhanden
    		if(nicht vorhanden)
    			Anschlusskante dem Vektor hinzufügen
    	}
    }
    

    (habe für den A* wichtige Schritte weggelassen aber die sind für das Speicherungsproblem irrelevant)



  • ups fehler.
    bei for(alle Anschlusskanten von cheapestEdge) natürlich auch meist NICHT mehr wie 5



  • Xenya schrieb:

    das mit der zusätzlichen Speicherung des kleinsten Elementes ist im Prinzip eine gute Idee. Aber dies wird auch immer wieder heraus gelöscht, weshalb danach eh wieder alle durchsucht werden müssen, um den aktuell kleinsten zu bekommen.

    Also wenn in dem Vektor dauernd Elemente gelöscht und andere wieder hinzugefügt werden müssen, ist grundsätzlich erst mal zu überlegen, ob nicht eine Liste besser wäre - Elemente löschen in einem Vektor ist relativ teuer.

    Ansonsten kann man natürlich statt nur das kleinste Element zu speichern, einen zweiten Vektor vector<int> aufbauen, der die Indexe des ursprünglichen Vektors speichert, aber in einer anderen Sortierreihenfolge, etwa so:

    vector<Edge> - sortiert nach ID
    1. Elem {ID 3, Kantengewicht 25}
    2. Elem {ID 6, Kantengewicht 23}
    3. Elem {ID 12, Kantengewicht 2}
    4. Elem {ID 31, Kantengewicht 28}

    vector<int> - sortiert nach Kantengewicht
    1. Elem {3}
    2. Elem {2}
    3. Elem {1}
    4. Elem {4}

    aber so wird das Löschen im int - Vektor teuer, weil immer erst das richtige Element gesucht werden muss - es sei denn, Du löschst tatsächlich immer nur das Element mit dem kleinsten Kantengewicht, denn das ist ja hier immer das erste.
    Andernfalls geht es möglicherweise mit einem anderen Container performanter, das ist mir jetzt so auf die Schnelle aber etwas zu komplex ...
    Vielleicht kannst Du ja mit diesen Ansätzen etwas anfangen.



  • wenn ich deinen Beitrag nun richtig verstehe, würdest du anstelle zu hashen oder Bäume zu verwenden, zu sortieren Vectoren/Listen tendieren? Und dann mit binärer Suche nach den Elementen suchen?

    Hm, ist das bessere Löschverhalten von Listen so gut, dass ich das schlechter Such-Verhalten davon hinnehmen soll?



  • Xenya schrieb:

    wenn ich deinen Beitrag nun richtig verstehe, würdest du anstelle zu hashen oder Bäume zu verwenden, zu sortieren Vectoren/Listen tendieren? Und dann mit binärer Suche nach den Elementen suchen?

    Vermutlich würde ich dazu tendieren, aber Du steckst tiefer in Deiner Problematik, Du musst wissen, um welche Datenmengen es geht, und auch

    Xenya schrieb:

    Hm, ist das bessere Löschverhalten von Listen so gut, dass ich das schlechter Such-Verhalten davon hinnehmen soll?

    welche Operationen wie häufig vorkommen, denn die Auswahl des passenden Containers hängt wohl davon ab.
    Wenn häufig mittendrin eingefügt und gelöscht werden soll, kann es sehr gut sein, dass ein Vektor langsamer ist, als eine Liste.
    Es kommt halt immer drauf an ... und wenn Du den Vektor aus welchem Grund auch immer eher durchiterierst als direkt auf Elemente via Index zuzugreifen, dann geht ein wesentlicher Vorteil des Vektors verloren und eine Liste dürfte auch nicht langsamer sein.
    Es gibt für den aus Programmierersicht direkten Zugriff ja auch noch die Map, vielleicht eignet sich die auch ... keine Ahnung - ich denke wie gesagt, es hängt von der Datenmenge und den benötigten Operationen darauf ab, was die beste Vorgehensweise ist - aber wenn man eine große Datenmenge hat und die häufig durchsuchen muss, dann sollte man nach Möglichkeiten Ausschau halten, nicht jedes Mal von einem Ende zum anderen durchzunudeln.


Log in to reply