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.
BlackJack

Beitragvon BlackJack » Mittwoch 28. Januar 2009, 08:25

@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

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

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

Beitragvon cofi » Mittwoch 28. Januar 2009, 10:35

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

Beitragvon meh11 » Mittwoch 28. Januar 2009, 11:48

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

Beitragvon meh11 » Sonntag 15. März 2009, 12:11

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.

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]