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.
meh11
User
Beiträge: 11
Registriert: Montag 24. November 2008, 16:27

Wieso ist meine A-Star Implementation so langsam?

Beitragvon meh11 » Mittwoch 24. Dezember 2008, 05:33

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

Beitragvon bremer » Mittwoch 24. Dezember 2008, 09:05

Füge Pythoncode besser auch als Pythoncode ein.
BlackJack

Beitragvon BlackJack » Mittwoch 24. Dezember 2008, 10:35

@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

Beitragvon meh11 » Mittwoch 24. Dezember 2008, 12:35

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

Beitragvon __marcus__ » Mittwoch 24. Dezember 2008, 13:08

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

Beitragvon meh11 » Samstag 27. Dezember 2008, 14:21

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

Beitragvon __marcus__ » Samstag 27. Dezember 2008, 14:51

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

Beitragvon meh11 » Donnerstag 22. Januar 2009, 15:25

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

Beitragvon audax » Donnerstag 22. Januar 2009, 15:48

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

Beitragvon helduel » Donnerstag 22. Januar 2009, 16:29

@__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

Beitragvon __marcus__ » Donnerstag 22. Januar 2009, 21:01

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

Beitragvon meh11 » Dienstag 27. Januar 2009, 21:10

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
Moderator
Beiträge: 4432
Registriert: Sonntag 30. März 2008, 04:16
Wohnort: RGFybXN0YWR0

Beitragvon cofi » Dienstag 27. Januar 2009, 21:45

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

Beitragvon derdon » Dienstag 27. Januar 2009, 21:52

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

Beitragvon meh11 » Mittwoch 28. Januar 2009, 07:49

Stimmt. :blush:

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]