Wieso ist meine A-Star Implementation so langsam?

[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]

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?

[cofi]

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]

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

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]

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.