Wieso ist meine A-Star Implementation so langsam?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

Der Threadtitel sagt eigentlich schon alles: Ich habe den A* implementiert unter Verwendung von heapq und dicts, aber das ganze ist dennoch viel zu langsam, und mir sind die Ideen ausgegangen was ich noch verbessern könnte.
Das ganze braucht auf einem 160*116 Feld schon mal gut und gerne 1-2 Sekunden, wenn kein Weg verfügbar ist, was viel zu viel ist.

Ich habe hier einfach mal die Implementation rausgerissen, und das komplette ausführbare Projekt zusätzlich angehängt. (Macht euch nicht die Mühe auf die Knöpfe der anderen Algorithmen ausser A* zu klicken, die gehen alle noch nicht.)

Code: Alles auswählen

def useAstar(self, start, goal):
        self.path = []
        currList = (start.HCost,0,Edge(None,start,0))
        self.openList = [currList]
        self.openHash = {}
        self.openHash[id(start)] = currList
        print self.openList
        self.closedList ={}
        print self.closedList
        while self.openList != []:
            currList = heappop(self.openList)
            nodeID = id(currList[2].terminalNode)
            if nodeID in self.closedList:
                continue
            self.closedList[nodeID] = currList
            del self.openHash[nodeID]
            if currList[2].terminalNode is goal:
                self.internalAstar_reconstructPath(start, goal)
                return self.path
            for edge in currList[2].terminalNode.outgoingEdges:
                self.internalAstar_checkEdge(edge, currList, goal)
            
    def internalAstar_reconstructPath(self,start,goal):
        print "found goal"
        node = goal
        while node != None:
            self.path.append(node)
            list = self.closedList[id(node)]
            node = list[2].initialNode
        self.path.reverse()
        return self.path

    def internalAstar_checkEdge(self, edge, currList, goal):
        nodeID = id(edge.terminalNode)
        if nodeID in self.closedList:
            closed = self.closedList[nodeID]
            if edge.weight + currList[1] < closed[1]:
                del self.closedList[nodeID]
                edge.terminalNode.checkInheritedHCost(edge)
                self.internalAstar_insert(edge, currList, nodeID)
            return
        if nodeID in self.openHash:
            opened = self.openHash[nodeID]
            if edge.weight + currList[1] < opened[1]:
                self.internalAstar_insert(edge, currList, nodeID)
            return
        edge.terminalNode.computeHCost(goal, edge)
        self.internalAstar_insert(edge, currList, nodeID)

    def internalAstar_insert(self, edge, currList, nodeID):
        gcost = currList[1]+edge.weight
        currList = (gcost+edge.terminalNode.HCost, gcost, edge)
        heappush(self.openList, currList)
        self.openHash[nodeID] = currList
Problematisch scheint die Methode internalAstar_checkEdge zu sein.

Ich wäre euch wirklich sehr dankbar für Ideen, wie man das noch beschleunigen könnte, oder Anregungen, was ich bei dieser Implementation falsch gemacht habe, denn ich weiß wirklich nicht mehr weiter.

Dass die Demo nicht gut ist, ist mir klar (zb dass direkt alle Suchknoten erstellt werden), oder dass man das beschleunigen kann indem man eine andere Representation für den Suchraum benutzt, aber die Implementation von dem Algorithmus als solche scheint ja schon nicht in Ordnung zu sein, und um den geht es mir hier.


http://fileload.us/49885320-demo.rar
Zuletzt geändert von meh11 am Mittwoch 24. Dezember 2008, 12:18, insgesamt 1-mal geändert.
bremer
User
Beiträge: 109
Registriert: Sonntag 25. Mai 2008, 00:13

Füge Pythoncode besser auch als Pythoncode ein.
BlackJack

@meh11: Mach Dich doch mal mit dem Profiler `cProfile` vertraut, da kannst Du Dir anschauen welche Funktion wie oft aufgerufen wird, und wo am meisten Zeit verbraucht wird.

Hat nichts mit der Geschwindigkeit zu tun, aber mit Lesbar- und Wartbarkeit: (konkrete) Datentypen gehören nicht in Namen. An das Attribut `currList` immer nur Tupel zu binden ist zum Beispiel sehr verwirrend.

`path` sollte kein Attribut sein. Und es ist kein so guter Stil ausserhalb von einer `__init__()`-Methode neue Attribute einzuführen.

Den Präfix `internal*` würde ich durch einen einzelnen Unterstrich ersetzen. Die Namen werden kürzer, sagen aber immer noch das gleiche aus.
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

Danke für den Pythoncode Tipp, war gestern anscheinend zu müde um diesen Button im Forum zu sehen. Bis in die Puppen dran gebastelt, und als letzten Verzweiflungsakt hier um Hilfe gebeten. :wink:


Ich habe das ganze bereits mit profile untersucht, wie man in der Demo sehen kann (da ist eine Funktion profileAstar, deren Aufruf in handleInput auskommentiert ist).
Wo ist der Unterschied zu cProfile? Ich werds jedenfalls jetzt nochmal mit cProfile testen.
Aber wie im ersten Post geschrieben, profile hat mir angezeigt, dass checkEdge langsam zu sein scheint, aber ich weiss nicht wie ich das noch schneller bekommen kann.

Zur Lesbarkeit: Hast Recht, das ganze kam so zu Stande, weil ichs zich mal überarbeitet habe. :oops: Ich hoffe das hindert keinen daran zu entziffern was ich da zusammengeschrieben hab.
Vielen Dank jedenfalls für die Hinweise, ich werd alles vermutlich noch öfter umschreiben, und dann dabei auch auf die Lesbarkeit achten. :)


Wie auch immer, ich würde mich wirklich freuen, wenn jemand weiss wie ich die A* Implementation schneller machen kann.
Vielen Dank im Voraus.
__marcus__
User
Beiträge: 92
Registriert: Mittwoch 10. September 2008, 22:10
Wohnort: Hamburg

Ich hab vor kurzem das hier

http://paste.pocoo.org/show/96617/

geschrieben.

Vielleicht bringt dich das ja weiter.
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

Hi,

danke für den Link, ich bin allerdings nach reichlicher Überlegung zum Schluss gekommen, dass ich ohne Hilfe nicht verstehe warum deine Implementation schneller ist als meine. :oops:

So wie ich das sehe, müsste es doch schneller sein, wenn man ausnutzt, dass die Liste mit geöffnete Knoten bereits sortiert ist, zb in Form eines Heaps, anstatt jedesmal einen Sortieralgorithmus drüberlaufen zu lassen, oder?

Und ich verstehe auch nicht, warum ein einfaches Array mit geschlossenen Knoten, was meinem Verständnis nach eine Abfragezeit von O(n) hat, schneller ist als ein Hash..?

Und es gibt doch auch noch den Fall beim Verwenden einer Heuristik, dass Knoten von der geschlossenen Liste wieder in die geöffnete Liste kommen? Ich kann da keine Abfrage für sehen. :?


Zusammengefasst einfach nur: Warum ist deins schneller als meins? Ich verstehs nicht. :(
__marcus__
User
Beiträge: 92
Registriert: Mittwoch 10. September 2008, 22:10
Wohnort: Hamburg

Ich hab mir Dein Skript gar nicht genauer angeschaut!

Aber ich hab halt vor kurzem PyRoute genommen neu geschrieben und danach war es bis zu 30* mal schneller.

Und die Karte von Hamburg hat mit Sicherheit mehr als 160*120 Nodes.

Ob Du damit etwas anfangen ist eine ganz andere Frage.
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

Gibts wirklich keinen der mir helfen kann? :(
audax
User
Beiträge: 830
Registriert: Mittwoch 19. Dezember 2007, 10:38

schau dir doch mal Pyroute an...
Benutzeravatar
helduel
User
Beiträge: 300
Registriert: Montag 23. Juli 2007, 14:05
Wohnort: Laupheim

@__marcus__: Bist du/Warst du Perl-Coder? :lol:

Code: Alles auswählen

name = data['ways'][data['routes'][node][result[index+1]]['wayid']]['tags'].get('n', 'No name')
__marcus__
User
Beiträge: 92
Registriert: Mittwoch 10. September 2008, 22:10
Wohnort: Hamburg

helduel hat geschrieben:@__marcus__: Bist du/Warst du Perl-Coder? :lol:

Code: Alles auswählen

name = data['ways'][data['routes'][node][result[index+1]]['wayid']]['tags'].get('n', 'No name')
Ich bräuchte auf jeden Fall ein paar Minuten um wieder zu verstehen.

---

Mit was für Daten arbeitest Du denn?
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

So hab den A* nochmal neu implementiert, und beim schrittweise optimieren wieder zu Heap und Hash für die geöffneten Knoten gegriffen, denn das ständige Sortieren eines Arrays war bei mir immer sehr viel langsamer.
Das Hash mit den geschlossenen Knoten habe ich mit dem Hash der geöffneten Knoten vereint und masterDict genannt.
Als Schlüssel für den Hash haben sich die IDs der Knoten als schneller rausgestellt als die Knoten selber.
Ebenso hat sich gezeigt, dass heappush und insbesondere heappop schneller sind, wenn ich die IDs der Knoten einfüge anstelle der Knoten selber. Dank des Hashs kann ich ja mithilfe dieser IDs auf die Knoten zugreifen.
Der id() Aufruf hat sich auch als langsam rausgestellt und ich konnte das ganze beschleunigen indem ich den Knoten ihre IDs als Attribut mitgegeben habe.

Um zu sehen wie sich der A* bei vielen geöffneten Knoten verhält habe ich die Heuristik auf 1 gestellt, sodass der A* sich wie Dijkstra verhält, und auf einer Karte von 200*200 Knoten bei gleichen Kantengewichten den Startknoten links oben gewählt und den Zielknoten rechts unten.

Die Ergebnisse:
Die neue Implementation:

Code: Alles auswählen

         129489 function calls in 1.533 CPU seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    1.533    1.533 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000 Edge2.py:2(__init__)
    39999    0.088    0.000    0.088    0.000 Node2.py:8(heurFunc)
        1    0.000    0.000    0.000    0.000 Search7.py:5(__init__)
        1    1.127    1.127    1.514    1.514 Search7.py:8(useAstar)
        1    0.019    0.019    1.533    1.533 astar2test.py:43(lol)
    44642    0.190    0.000    0.190    0.000 {_heapq.heappop}
    44641    0.109    0.000    0.109    0.000 {_heapq.heappush}
      200    0.000    0.000    0.000    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
        1    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}
Im Vergleich dazu hat die alte Implemenatition so lange gebraucht:

Code: Alles auswählen

         934205 function calls (934091 primitive calls) in 6.328 CPU seconds
Der Code der neuen Implementation:

Code: Alles auswählen

from Edge2 import Edge
from heapq import heappush, heappop

class Search():
    def __init__(self):
        pass
    
    def useAstar(self, start, goal):
        nID = start.id  # precomputed ids are faster
        openHeap = [(0, 0, nID)]
        masterDict = {nID:(0, 0, Edge(None, start, 0))} # using ID's instead
        while openHeap != []:                       # edges as key is faster
            o = heappop(openHeap)
            currID = o[2]
            curr = masterDict[currID]
            if o[0] > curr[0]:  # *can* be faster, if the same open nodes occurs
                continue    # then his children tests will be skipped... remove?
            if curr[2].terminalNode is goal:
                #reconstruct path
                path = []
                n = goal
                while n is not None:
                    path.append(n)
                    n = masterDict[n.id][2].initialNode
                path.reverse()
                return path
            # add children to openHeap
            for edge in curr[2].terminalNode.outgoingEdges:
                g = curr[0]-curr[1]+edge.weight # f-h+w
                nID = edge.terminalNode.id
                if nID in masterDict:
                    openItem = masterDict[nID]
                    if g >= openItem[0]-openItem[1]:
                        continue
                    h = openItem[1]
                else:
                    h = edge.terminalNode.heurFunc(goal)
                f = g+h
                masterDict[nID] = (f, h, edge)
                heappush(openHeap, (f, h, nID)) # pushing ids instead of edges
        return []                           # into the heap makes heappop faster

Und das ganze ausführbar als Download:
http://fileload.us/zytzvap5c7yx


Die Frage: Wie bekomm ichs schneller? Nach wie vor kann ich mir keinen Reim daraus machen warum meine Implementationen so langsam sind.
Ich habe mir sowohl Pyroute und auch __marcus__ Implementation angesehen, aber ich versteh ohne Erklärung nicht was ich falsch mache. :(

Bitte helft mir.
Benutzeravatar
cofi
Python-Forum Veteran
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Sag mal warum benutzt du denn da eine Klasse? Du benutzt weder Instanzattribute, noch Klassenattribute und missbrauchst das nur als Namespace oO
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Und eine __init__, die nichts macht, ist überflüssig. Inline-Kommentare sind auch doof.
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

Stimmt. :blush:
BlackJack

@meh11: Und noch ein bisschen Kritik: `masterDict` ist ein schlechter Name. Der sagt nichts darüber aus, *was* da drin gespeichert wird. So etwas wie `open_nodes` oder `known_nodes` wäre da besser. `openHeap` würde ich auch umbenennen, damit der Name der Datenstruktur aus dem Namen verschwindet.

Da Tupel nicht so "selbstbeschreibend" sind, wäre ein Kommantar was in `openHeap` und `masterDict` eigentlich gespeichert wird, ganz nett.

Die ``while``-Schleife ist vielleicht einen Tick schneller wenn Du einfach ``while openHeap:`` schreibst.

Auf Abkürzungen sollte man verzichten. Betrifft zum Beispiel `o` und `curr`. Von letzterem werden im weiteren Verlauf anscheinend alle Elemente verwendet, da könnte man auch alle an Namen binden und das Programm damit verständlicher machen.
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

Habs masterDict genannt, weil in Game Programming Gems 1 etwas von einer masterNodeList oder so stand... Aber knownNodes hört sich gut an, ich benenne den Kram mal um und ändere die Kommentare.

Zur while Schleife:
Bei 9000 Aufrufen auf einem 6*5 Feld war deine Version schneller. Wenn ich das richtig interpretiere dann wird durch mein != [] bei jedem Aufruf von useAstar() ein unnötiges leeres Array erzeugt, richtig?
Benutzeravatar
cofi
Python-Forum Veteran
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Da du dich gegen die pythonische Bennenung sträubst, lies doch mal [wiki]PEP 8 (Übersetzung)[/wiki];) oder das Orginal http://www.python.org/dev/peps/pep-0008/
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

Tatsächlich habe ich schonmal Guido Rossums Style Guide gelesen, aber es ist vermutlich keine schlechte Idee das ganze mal aufzufrischen. :oops:

Ich hoffe das hier ist besser:

Code: Alles auswählen

from Edge2 import Edge 
from heapq import heappush, heappop 

def useAStar(start, goal):
    """ A*: -Uses a Hash knownNodes for fast access to edges with smallest
                    cost to their nodes
                -knownNodes is used as closed list and provides fast access to
                        opened nodes, using nodes' ids as key
                -Uses a Heap openNodes as fast priority queue
                -openNodes is sorted by F and H
                -openNodes is slow when edges are inserted, so instead it
                    makes use of the nodes' ids and knownNodes to retain edges
                -Nodes' ids are precomputed for sake of speed
    """
    nID = start.id
    openNodes = [(0, 0, nID)] # heap holds (f, h, terminalNode's id)
    knownNodes = {nID:(0, 0, Edge(None, start, 0))} # hash holds (f, h, edge)
    while openNodes:
        popped = heappop(openNodes)
        openID = popped[2]
        openF, openH, openEdge = knownNodes[openID]
        if popped[0] > openF:  # *can* be faster, if the same open nodes occurs 
            continue    # then his children tests will be skipped... remove? 
        # if goal found -> reconstruct path 
        if openEdge.terminalNode is goal:
            path = []
            n = goal
            while n is not None:
                path.append(n)
                n = knownNodes[n.id][2].initialNode
            path.reverse()
            return path
        # add children to openHeap 
        for edge in openEdge.terminalNode.outgoingEdges:
            g = openF - openH + edge.weight
            nID = edge.terminalNode.id
            if nID in knownNodes:
                knownItem = knownNodes[nID]
                if g >= knownItem[0] - knownItem[1]:
                    continue
                h = knownItem[1]
            else:
                h = edge.terminalNode.heurFunc(goal) 
            f = g + h 
            knownNodes[nID] = (f, h, edge) 
            heappush(openNodes, (f, h, nID))
    return []
Weitere Ideen wie mans schneller bekommt oder Erklärungen warum meins langsamer ist als andere Implemenationen sind willkommen. :)
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

Okay, eine Kleinigkeit ist mir eingefallen: Wenn ich vom Ziel zum Start hin suche, dann spar ich mir das path.reverse() beim Rekonstruieren des Weges.
Antworten