Geschwindigkeitsproblem bei nem Algo

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

Geschwindigkeitsproblem bei nem Algo

Beitragvon DasPinsch » Sonntag 27. Februar 2005, 14:30

Bin dabei ein Spiel in Python zu programmieren und habe soeben den Wegfindungsalgorithmus implemeniert (A*).
Leider ist er nicht sonderlich schnell (viel zu langsam, längere Strecken brauchen schonmal schnell ne Sekunde oder länger), allerdings finde ich den "Flaschenhals" nicht... Hier der Code:

Code: Alles auswählen

    def astar(self, startPos, endPos):
        times = [0, 0, 0, 0]
        clock = pygame.time.Clock()

        start = (int(startPos[0] / 50), int(startPos[1] / 50))
        end = (int(endPos[0] / 50), int(endPos[1] / 50))
       
        def nodeKeyFunc(node): # Funktion zur Sortierung
            return node.getRating()

        def getNeighbours(node):
            def checkAndAdd(x, y, list):
                if x >= 0 and x <= 99 and y >= 0 and y <= 74:
                    # kontrolliert python die bedingungen automatisch von links nach rechts ?!
                    # wenn nicht, sorge dafuer, dass es keinen "Out-of-Range" error gibt
                    node = self.nodes[x][y]
                    if  node.passable and not node in closedList:
                        list.append(node)
            neighbours = []
            x, y = node.position
            checkAndAdd(x - 1, y - 1, neighbours)
            checkAndAdd(x, y - 1, neighbours)
            checkAndAdd(x + 1, y - 1, neighbours)
            checkAndAdd(x - 1, y, neighbours)
            checkAndAdd(x + 1, y, neighbours)           
            checkAndAdd(x - 1, y + 1, neighbours)
            checkAndAdd(x, y + 1, neighbours)
            checkAndAdd(x + 1, y + 1, neighbours)
            return neighbours

        def cost(node1, node2):
            if abs((node1.position[0] - node2.position[0]) * \
                         (node1.position[1] - node2.position[1])) == 1: # diagonal
                return 14 + node1.cost
            return 10 + node1.cost

        def manhatten(node1, node2):
            return (abs(node1.position[0] - node2.position[0]) + \
                   abs(node1.position[1] - node2.position[1])) * 10

        endNode = self.nodes[end[0]][end[1]]           
        startNode = self.nodes[start[0]][start[1]]
        startNode.cost = 0
        startNode.heuristic = manhatten(startNode, endNode)
        openList = [startNode]
        closedList = []
        pathFound = 0
        clock.tick()
        while not pathFound:
            if not len(openList):
                pathFound = 1
                continue
            currentNode = openList[0]
            for node in openList:
                if node.getRating() < currentNode.getRating():
                    currentNode = node
            openList.remove(currentNode)
#            openList.sort(key = nodeKeyFunc)
#            currentNode = openList.pop(0)
            closedList.append(currentNode)
            times[0] += clock.tick()
            neighbours = getNeighbours(currentNode)
            times[1] += clock.tick()           
            for neighbour in neighbours:
                if not neighbour in openList:
                    neighbour.previous = currentNode
                    if neighbour == endNode:
                        pathFound = 2
                    else:
                        neighbour.cost = cost(currentNode, neighbour)
                        neighbour.heuristic = manhatten(currentNode, endNode)
                        openList.append(neighbour)
                    times[2] += clock.tick()
                else:
                    tempCost = cost(currentNode, neighbour)
                    if tempCost < neighbour.cost:
                        neighbour.cost = tempCost
                        neighbour.previous = currentNode
                    times[3] += clock.tick() 
                if pathFound:
                    break


Vielleicht ist noch zu sagen, dass das Spielfeld (5000 * 3750 Px) in 50 * 50px große Nodes unterteilt ist!
An den Zeiten kann man erkennen, dass vor allem das Suchen der Nachbarn sehr Zeitaufwendig ist. Worin liegts?
[1] an mir
[2] an Python
[3] an Listen


MfG

Edit (Leonidas): Code in Python Tags gesetzt.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Sonntag 27. Februar 2005, 14:45

Hast du schon mal den Python Profiler versucht, insbesondere hotshot?

Edit: Also dein Code ist schon etwas seltsam... vor allem habe ich grade keine Ahnung wie ich ihn überhaupt testen soll.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
DasPinsch

Beitragvon DasPinsch » Sonntag 27. Februar 2005, 15:30

So, konnte durch das Entfernen der meisten Listenfunktionen die Sache schon erheblich optimieren.. =)
der Code ist natürlich auch nur ein kleiner Teil des ganzen und ist von dem Rest losgelöst auch nicht ausführbar.
DasPinsch

Beitragvon DasPinsch » Dienstag 1. März 2005, 18:48

Code: Alles auswählen

import math
import Numeric as N

class Path:
    def __init__(self, collisionMap):
        self.map = collisionMap
        self.openListVar = 0
        self.openList = N.zeros((100 * 75))
        self.onList = N.zeros((100, 75))
        self.openX = N.zeros((100 * 75))
        self.openY = N.zeros((100 * 75))
        self.parentX = N.zeros((100, 75))
        self.parentY = N.zeros((100, 75))
        self.cost = N.zeros((100, 75))
        self.heuristic = N.zeros((100 * 75))
        self.rating = N.zeros((100 * 75))

    def astar(self, startPos, endPos):
        startX = startPos[0] / 50
        startY = startPos[1] / 50
        endX = endPos[0] / 50
        endY = endPos[1] / 50

        if self.openListVar > 1000000000: # alle 500 000 000 aufrufe wird die liste erneuert
            self.openListVar = 0
            for y in self.onList:
                for x in y:
                    x = 0
        self.openListVar += 2
        closedListVar = self.openListVar - 1

        openListID = 1
        nOpenItems = 1
        self.openList[0] = 0
        self.openX[0] = startX
        self.openY[0] = startY

        while True:
            if nOpenItems >= 1:
                parentX = int(self.openX[self.openList[0]])
                parentY = int(self.openY[self.openList[0]])
                self.onList[parentX][parentY] = closedListVar

                nOpenItems -= 1
                self.openList[0] = self.openList[nOpenItems]
               
                v = 1
                while True:
                    u = v
                    if 2 * u + 1 <= nOpenItems:
                        if self.rating[self.openList[u - 1]] >= self.rating[self.openList[2 * u - 1]]:
                            v = 2 * u
                        if self.rating[self.openList[v - 1]] >= self.rating[self.openList[2 * u]]:
                            v = 2 * u + 1
                    elif 2 * u <= nOpenItems:
                        if self.rating[self.openList[u - 1]] >= self.rating[self.openList[2 * u -1]]:
                            v = 2 * u
                    if not u == v:
                        temp = self.openList[u - 1]
                        self.openList[u - 1] = self.openList[v - 1]
                        self.openList[v - 1] = temp
                    else:
                        break

                for x in range(parentX - 1, parentX + 2):
                    for y in range(parentY - 1, parentY +2):
                        if not (x == parentX and y == parentY) and x >= 0 and x < 100 and y >= 0 and y < 75:
                            if not self.onList[x][y] == closedListVar and not self.map[x][y]:
                                if not self.onList[x][y] == self.openListVar:
                                    nOpenItems += 1
                                    m = nOpenItems
                                    self.openList[m - 1] = openListID
                                    self.openX[openListID] = x
                                    self.openY[openListID] = y
                                    openListID += 1
                                    if (x - parentX) and (y - parentY):
                                        self.cost[x][y] = self.cost[parentX][parentY] + 14
                                    else:
                                        self.cost[x][y] = self.cost[parentX][parentY] + 10
                                    self.heuristic[self.openList[m - 1]] = 10 * (abs(x - parentX) + abs(y - parentY))
                                    self.rating[self.openList[m - 1]] = self.cost[x][y] + self.heuristic[self.openList[m - 1]]
                                    self.parentX[x][y] = parentX
                                    self.parentY[x][y] = parentY
                                    while m > 1:
                                        if self.rating[self.openList[m - 1]] < self.rating[self.openList[m / 2 - 1]]:
                                            temp = self.openList[m / 2 - 1]
                                            self.openList[m / 2 - 1] = self.openList[m - 1]
                                            self.openList[m - 1] = temp
                                            m /= 2
                                        else:
                                            break
                                    self.onList[x][y] = self.openListVar
                                else:
                                    if (x - parentX) and (y - parentY):
                                        tempCost = self.cost[parentX][parentY] + 14
                                    else:
                                        tempCost = self.cost[parentX][parentY] + 10
                                    if tempCost < self.cost[x][y]:
                                        self.parentX[x][y] = parentX
                                        self.parentY[x][y] = parentY
                                        self.cost[x][y] = tempCost
                                        for i in range(nOpenItems):
                                            if self.openX[self.openList[i]] == x and self.openY[self.openList[i]] == y:
                                                self.rating[self.openList[i]] = self.cost[x][y] + self.heuristic[self.openList[i]]
                                                m = i + 1
                                                while m > 1:
                                                    if self.rating[self.openList[m - 1]] < self.rating[self.openList[m / 2 - 1]]:
                                                        temp = self.openList[m / 2 - 1]
                                                        self.openList[m / 2 - 1] = self.openList[m - 1]
                                                        self.openList[m - 1] = temp
                                                        m = m / 2
                                                    else:
                                                        break
                                                break
            else:
                print "kein weg"
                return []
            if self.onList[endX][endY] == closedListVar:
                print "weg gefunden"
                break


        return []                                   


so, das ist mein Code bis jetzt. Allerdings ist er immer noch so langsam, dass eine Wegsuche schonmal locker eine halbe Sekunden in Anspruch nimmt... Auch Compilieren mit py2exe bringt nichts :/ das kann doch nich sein, dass Python wirklich so langsam ist? Ein vergleichbarer c Code ist mindestens 100 Mal so schnell ?!
Das gleiche Problem hab ich bei folgendem Primzahlenprogramm:

Code: Alles auswählen

def sieb(n):
    n = (n - 1) / 2
    l = N.ones(n)
    x = 0
    p = []
    while x < n:
        if l[x]:
            i = 2 * x + 3
            y = x + i
            while True:
                if y >= n:
                    break
                l[y] = 0
                y += i
            p.append(i)
        x += 1
    print p
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Dienstag 1. März 2005, 19:09

DasPinsch hat geschrieben:so, das ist mein Code bis jetzt. Allerdings ist er immer noch so langsam, dass eine Wegsuche schonmal locker eine halbe Sekunden in Anspruch nimmt... Auch Compilieren mit py2exe bringt nichts :/

py2exe ist ja auch kein Compiler und es wurde mich nicht wundern wenn py2exe Programme in allem noch langsamer wären. Guck dir doch Psyco und die aktuellsten Python Versionen an.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
fs111
User
Beiträge: 170
Registriert: Samstag 15. November 2003, 11:42
Kontaktdaten:

Beitragvon fs111 » Dienstag 1. März 2005, 19:40

Leonidas hat geschrieben:
DasPinsch hat geschrieben:so, das ist mein Code bis jetzt. Allerdings ist er immer noch so langsam, dass eine Wegsuche schonmal locker eine halbe Sekunden in Anspruch nimmt... Auch Compilieren mit py2exe bringt nichts :/

py2exe ist ja auch kein Compiler und es wurde mich nicht wundern wenn py2exe Programme in allem noch langsamer wären. Guck dir doch Psyco und die aktuellsten Python Versionen an.



Bevor man psyco benutz, sollte man lieber noch mal über den Algo nachdenken.

Des weiteren solltest Du xrange anstatt range verwenden, das erzeugt die Werte erst, wenn sie benötigt werden.

fs111
Pydoc-Integration in vim - Feedback willkommen: http://www.vim.org/scripts/script.php?script_id=910
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Dienstag 1. März 2005, 19:48

Klar! Ich könnte dich an jemanden verweisen, der sowas recht gut gemacht hat, dem Autor von Schiffbruch.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
DasPinsch

Beitragvon DasPinsch » Dienstag 1. März 2005, 20:01

Danke schonmal, pysco hat ca. 100% performance gebracht, allerdings ist es immer noch recht langsam...
xrange dürfte doch auch nur helfen wenn nicht unbedingt alle elemente durchlaufen werden, oder? also nur bei der "innersten" range funtkion. einen merklichen geschwindigkeitswachstum konnte ich dadurch jedoch nicht bemerken (hatte ich ehrlich gesagt auch nicht erwartet)...
Zu dem Algo: eigentlich sollte der sehr gut sein! Allerdings überlege ich gerade, dass sehr große Gebiete auf meiner Karte leer sind... bin gerade auch dabei einen linienalgo zu implementieren, so dass der A* algo nur für hindernisse die umgangen werden eingesetzt werden muss, allerdings ist das ja nicht gerade der Sinn des A*.. mir kommt gerade die Idee, dass man dann ja noch einen viel effizienteren Algorithmus einsetzen könnte (Karte ist komplett offen, nur Berge und Seeen können "im Weg" sein, man könnte also - wenn man auf ein Hinderniss stößt - einfach testen ob man besser links oder rechts daran vorbeigehen könnte!
DasPinsch

Beitragvon DasPinsch » Dienstag 1. März 2005, 22:18

Was ich noch fragen wollte: gibt es ein Programm, dass Python Quelltext in C(++) Code umwandelt?
BlackJack

Beitragvon BlackJack » Dienstag 1. März 2005, 22:56

Deine beiden Beispiele, sowohl Deine Suche nach dem Weg, als auch das Primzahlensieb sehen verdammt nach C(++) Code aus, der einfach nach Python übertragen wurde. Das gibt oft "langsamen" Code. Zum Beispiel würde ein C-Compiler eine Menge wegoptimieren. Python führt ziemlich genau das aus, was Du angibst. In der ersten Schleife kommt oft ``2 * u`` vor -- das wird jedesmal berechnet wenn es ausgeführt wird!

Und dann so Kleinigkeiten wie Inhalte von Variablen tauschen:

Code: Alles auswählen

tmp = a
a = b
b = tmp


Schreibt man in Python so:

Code: Alles auswählen

b, a = a, b


Das wird den Code jetzt nicht plötzlich 100mal schneller machen, aber solche Kleinigkeiten summieren sich.

Ich kenne A* nicht und weiss daher nicht ob folgender Tip verwendbar ist, aber eine "Sparse Matrix" kann man auch ganz gut mit einem Dictionary implementieren bei dem als Schlüssel einfach ein Tupel mit den Koordinaten dient. Als Beispiel das "Game Of Life" hier: http://python.sandtner.org/viewtopic.php?t=2840

Zu Deiner letzten Frage: Es gibt PyRex. Das erlaubt es eingeschränktes Python mit C-Datentypen zu versehen und daraus Python-Erweiterungen zu übersetzen. Auf der Startseite ist auch gleich ein kleines Beispiel für Primzahlen, das Deinem nicht unähnlich ist.

Ansonsten kann man Python-Erweiterungen in C oder C++ schreiben. In der Python-Doku sollte eine Einführung zu dem Thema vorhanden sein.
DasPinsch

Beitragvon DasPinsch » Mittwoch 2. März 2005, 16:04

Ok danke, suchte eigentlich eher ein Programm, dass Python Quellcode in C(++) umwandelt, den ich dann mit einem C-Compilere compilieren kann!
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 2. März 2005, 16:20

DasPinsch hat geschrieben:Ok danke, suchte eigentlich eher ein Programm, dass Python Quellcode in C(++) umwandelt, den ich dann mit einem C-Compilere compilieren kann!

Es gab mal Python2C (p2c), aber das ist tot. Aber du kannst sowas wie freeze versuchen. Aber guck doch in den neuen FAQ.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
DasPinsch

Beitragvon DasPinsch » Mittwoch 2. März 2005, 19:02

Noch ne andere Frage, was ist denn an dem Primzahlen Code c++ - style?
Mfg
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Mittwoch 2. März 2005, 19:34

Das ist Python Style. Du kannst ja mal die Zeit messen, wenn du Lust hast.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
DasPinsch

Beitragvon DasPinsch » Mittwoch 2. März 2005, 20:39

Ehrlich gesagt sehe ich nicht wirklich den Unterschied (natürlich arbeitest du nach einem anderen Verfahren und hast direkt mehrere Funktionen mit einigem drumherum, aber die Funktionen als solche sind doch vom Stil nicht sehr anders?!)
Zwei Sache ist mir noch aufgefallen, du schreibst immer:
x = x + 1
anstatt
x += 1, ist das 2. nicht schneller?

Zudem benutzt du bei Zaheln so weit ich das gesehen habe den "is" Operator anstatt dem "=="! Ist "is" schneller?

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]