Seite 1 von 2
Geschwindigkeitsproblem bei nem Algo
Verfasst: Sonntag 27. Februar 2005, 14:30
von DasPinsch
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.
Verfasst: Sonntag 27. Februar 2005, 14:45
von Leonidas
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.
Verfasst: Sonntag 27. Februar 2005, 15:30
von DasPinsch
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.
Verfasst: Dienstag 1. März 2005, 18:48
von DasPinsch
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
Verfasst: Dienstag 1. März 2005, 19:09
von Leonidas
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.
Verfasst: Dienstag 1. März 2005, 19:40
von fs111
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
Verfasst: Dienstag 1. März 2005, 19:48
von Leonidas
Klar! Ich könnte dich an jemanden verweisen, der sowas recht gut gemacht hat, dem Autor von
Schiffbruch.
Verfasst: Dienstag 1. März 2005, 20:01
von DasPinsch
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!
Verfasst: Dienstag 1. März 2005, 22:18
von DasPinsch
Was ich noch fragen wollte: gibt es ein Programm, dass Python Quelltext in C(++) Code umwandelt?
Verfasst: Dienstag 1. März 2005, 22:56
von BlackJack
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:
Schreibt man in Python so:
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.
Verfasst: Mittwoch 2. März 2005, 16:04
von DasPinsch
Ok danke, suchte eigentlich eher ein Programm, dass Python Quellcode in C(++) umwandelt, den ich dann mit einem C-Compilere compilieren kann!
Verfasst: Mittwoch 2. März 2005, 16:20
von Leonidas
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.
Verfasst: Mittwoch 2. März 2005, 19:02
von DasPinsch
Noch ne andere Frage, was ist denn an dem Primzahlen Code c++ - style?
Mfg
Verfasst: Mittwoch 2. März 2005, 19:34
von Leonidas
Das ist Python Style. Du kannst ja mal die Zeit messen, wenn du Lust hast.
Verfasst: Mittwoch 2. März 2005, 20:39
von DasPinsch
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?
Verfasst: Mittwoch 2. März 2005, 20:53
von Leonidas
DasPinsch hat geschrieben: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?!)
Mein Code ist lesbarer
Davon abgesehen würde ich den inzwischen mit yield machen.
DasPinsch hat geschrieben:Zwei Sache ist mir noch aufgefallen, du schreibst immer:
x = x + 1
anstatt
x += 1, ist das 2. nicht schneller?
Sie sind gleich schnell, denn die Schreibweisen sind äquivalent. Aber ältere Pythonversionen kennen kein "Augmented Assign". Das wäre noch zu ändern, ich werde mal die aktuelle Version in die Codesnippets posten.
DasPinsch hat geschrieben:Zudem benutzt du bei Zaheln so weit ich das gesehen habe den "is" Operator anstatt dem "=="! Ist "is" schneller?
Nein, das war ein Fehler meinserseits (der Code an sich ist älter als 1. 2004), wie weiter im Thread geschreiben wird.
Verfasst: Mittwoch 2. März 2005, 21:06
von DasPinsch
Stimmt, dein Code ist deutlich lesbarer, würde mich aber auch nicht wagen sowas in C++ zu schreiben
hatte zuerst eine übersichtliche Funktion, hab diese dann aber versucht noch weiter zu optimieren und gleichzeitig alle variablennamen gekürzt
gleich noch ne Frage:
ist
for i in xrange(1000):
bla
schneller oder langsamer als
i = 0
while i < 1000:
bla
i += 1
?
irgendwie habe ich Angst, dass das Erstellen einer Liste viel Zeit in Anspruch nehmen könnte
Verfasst: Mittwoch 2. März 2005, 21:31
von Leonidas
Wenn es dir um absolute Performance geht, muss du in python Module auslagern.
Guck dir mal das
timeit Modul an, damit kannst du die Geschwindigkeit selbst herusfinden.
Ich würde die for Schleife nehmen, nicht weil sie schneller ist (das vermutlich nicht), sondern weil der Code eleganter ist, und darauf kommt es in Python oft an.
Zur Optimierung
hier mal ein interessanter Text. Pytho sieht man es nicht an, wie lange etwas dauert, man muss es einfach testen.
Verfasst: Donnerstag 3. März 2005, 07:03
von jens
Leonidas hat geschrieben:Ich würde die for Schleife nehmen, nicht weil sie schneller ist (das vermutlich nicht)...
Nep! While ist langsamer:
Code: Alles auswählen
import time
loops = 10000000
start = time.time()
for i in xrange( loops ): pass
end = time.time()
time1 = end - start
print "for: %.3fs" % time1
start = time.time()
i = 0
while i < loops: i += 1
end = time.time()
time2 = end-start
print "while: %.3fs" % time2
print "diff: %.3fs" % (time2 - time1)
Ergebnis:
Aber das war doch auch zu erwarten... Bei der while schleife wird einfach mehr gemacht, erst ein Vergleich, dann manuell die Variable i um eins hochgesetzt... (Das liegt auch nicht daran, das in den Schleifen nicht's gemacht wird... Wenn man bei beiden ein sinnloses a=str(i) macht, bleibt der Unterschied)
Verfasst: Donnerstag 3. März 2005, 13:35
von Leonidas
Hast recht, hier nochmal der Benchmark mit dem dediziiertem timeit Modul:
Code: Alles auswählen
#!/usr/bin/env python
# -*- encoding: latin-1 -*-
whilecode = """i = 0
while i < 10:
i += 1
"""
forcode = """for i in xrange(10):
pass
"""
def testit(times=10000):
from timeit import Timer
t = Timer(whilecode)
whiletook = t.timeit(number=times)
t = Timer(forcode)
fortook = t.timeit(number=times)
print "While vs. For: %i loops" % times
print
print "%.3f sec/all \tWhile" % whiletook
print "%.3f sec/all \tFor" % fortook
print "%.2f usec/pass While" % (1000000 * (whiletook/times))
print "%.2f usec/pass For" % (1000000 * (fortook/times))
if __name__ == '__main__':
testit()