Wie komme ich am schnellsten durch mein Array?
Ich glaube ich hatte schon einmal vorgeschlagen: Ein Dictionary. Da kann man dann auch gleich den Wert der besuchten Felder speichern.
Dumme Frage:
Wie mache ich das denn überhaupt mit einem Set?
Ich will doch immer Punktepaare speichern und die sind nicht sequenzierbar.
Ein Set für x-Werte und eines für y-Werte geht auch nicht, denn ich brauche ja die Paare.
Wie mache ich das denn überhaupt mit einem Set?
Ich will doch immer Punktepaare speichern und die sind nicht sequenzierbar.
Ein Set für x-Werte und eines für y-Werte geht auch nicht, denn ich brauche ja die Paare.
@Ydope: Was meinst Du mit "nicht sequenzierbar"? Man kann Tupel mit Zahlen drin in einem `set()` speichern bzw. als Schlüssel in Dictionaries verwenden.
Vergleich bisherige Variante <-> dictionary
Bei der dictionary-Variante wird die .has_key-Methode benutzt um zu prüfen, ob das Feld schon besucht wurde. Wenn nicht, wird der key gesetzt.
20 Mio. Schritte
1500x1500 Felder, mit Automat, der am Ende eine knappe Mio. Felder besucht hat:
bisherig: ~31s
dictionary: ~114s
90x90 Felder, mit Automat, der ca. 1500 Felder besucht:
bisherig: ~28,5s
dictionary: ~80s
@ BlackJack
hier in Kurzform mein Problem:
>>> set ([(1,2),(2,1)])
set([(1, 2), (2, 1)])
>>> set.add([(0, 1)])
TypeError: descriptor 'add' requires a 'set' object but received a 'list'
>>> set.add((0, 1))
TypeError: descriptor 'add' requires a 'set' object but received a 'tuple'
>>> set.add([0, 1])
TypeError: descriptor 'add' requires a 'set' object but received a 'list'
>>> set.add(0,1)
TypeError: descriptor 'add' requires a 'set' object but received a 'int'
Mit set.update passiert das gleiche. Wo ist der Fehler?
Bei der dictionary-Variante wird die .has_key-Methode benutzt um zu prüfen, ob das Feld schon besucht wurde. Wenn nicht, wird der key gesetzt.
20 Mio. Schritte
1500x1500 Felder, mit Automat, der am Ende eine knappe Mio. Felder besucht hat:
bisherig: ~31s
dictionary: ~114s
90x90 Felder, mit Automat, der ca. 1500 Felder besucht:
bisherig: ~28,5s
dictionary: ~80s
@ BlackJack
hier in Kurzform mein Problem:
>>> set ([(1,2),(2,1)])
set([(1, 2), (2, 1)])
>>> set.add([(0, 1)])
TypeError: descriptor 'add' requires a 'set' object but received a 'list'
>>> set.add((0, 1))
TypeError: descriptor 'add' requires a 'set' object but received a 'tuple'
>>> set.add([0, 1])
TypeError: descriptor 'add' requires a 'set' object but received a 'list'
>>> set.add(0,1)
TypeError: descriptor 'add' requires a 'set' object but received a 'int'
Mit set.update passiert das gleiche. Wo ist der Fehler?
Was willst du mir damit sagen?DasIch hat geschrieben:dicts _sind_ Container...Ydope hat geschrieben:Bei der dictionary-Variante wird die .has_key-Methode benutzt um zu prüfen, ob das Feld schon besucht wurde. Wenn nicht, wird der key gesetzt.
Ich wollte BlackJacks Vorschlag umsetzen und im Dictionary gleich den Wert der Zelle speichern. Der key ist das Koordinaten-Paar der Zelle. Wenn die Zelle noch nicht besucht wurde, gibt es den Key noch nicht.
Wenn ein Schritt gemacht wurde, muss daher doch geprüft werden, ob es den key gibt.
Code: Alles auswählen
In [8]: punkte = set([(1,2),(3,4),(5,6)])
In [9]: punkte.update([(7,8)])
In [10]: punkte
Out[10]: set([(1, 2), (5, 6), (3, 4), (7, 8)])
@Ydope: ``in`` ist schneller als `has_key()` aufzurufen, aber letztendlich brauchst Du das wahrscheinlich gar nicht, sondern eher die `get()`- oder die `setdefault()`-Methode. Eventuell auch ein `collections.defaultdict`.
Danke euch. Hab das mit dem Set endlich geschnallt.
Hier also der vollständige Benchmark:
20 Mio. Schritte ohne Bildschirmdarstellung
1500x1500 Felder, mit Automat, der am Ende eine knappe Mio. Felder besucht hat:
bisherig: ~31s
dictionary: ~114s
set: ~78s
90x90 Felder, mit Automat, der nur ca. verschiedene 1500 Felder besucht:
bisherig: ~28,5s
dictionary: ~80s
set: ~52s
Diese Varianten sind also deutlich langsamer.
Auch wenn damit evtl. eine leicht schnellere Bildschirmdarstellung möglich wäre, lohnt sich das nicht.
Hier also der vollständige Benchmark:
20 Mio. Schritte ohne Bildschirmdarstellung
1500x1500 Felder, mit Automat, der am Ende eine knappe Mio. Felder besucht hat:
bisherig: ~31s
dictionary: ~114s
set: ~78s
90x90 Felder, mit Automat, der nur ca. verschiedene 1500 Felder besucht:
bisherig: ~28,5s
dictionary: ~80s
set: ~52s
Diese Varianten sind also deutlich langsamer.
Auch wenn damit evtl. eine leicht schnellere Bildschirmdarstellung möglich wäre, lohnt sich das nicht.
OK dann werde ich das probieren und mich über diese Methoden informieren. Aber erst morgen. Will das jetzt nicht schon wieder umbauen und muss erstmal genau kapieren, was du meinst und ob das möglich ist.BlackJack hat geschrieben:@Ydope: ``in`` ist schneller als `has_key()` aufzurufen, aber letztendlich brauchst Du das wahrscheinlich gar nicht, sondern eher die `get()`- oder die `setdefault()`-Methode. Eventuell auch ein `collections.defaultdict`.
Letztendlich wirds trotzdem langsamer als der bisherige Weg sein
Gruß
- Hyperion
- Moderator
- Beiträge: 7478
- Registriert: Freitag 4. August 2006, 14:56
- Wohnort: Hamburg
- Kontaktdaten:
Also ich kann das nicht glauben! Die besuchten Felder müssen doch um ein vielfaches weniger sein, als das gesamte statische Spielfeld! Also muss doch eine Variante, in der man sich gezielt nur die benötigten Felder abarbeitet schneller sein (zumindest mal von den Algorithmus-Schritten).Ydope hat geschrieben: OK dann werde ich das probieren und mich über diese Methoden informieren. Aber erst morgen. Will das jetzt nicht schon wieder umbauen und muss erstmal genau kapieren, was du meinst und ob das möglich ist.
Letztendlich wirds trotzdem langsamer als der bisherige Weg sein
Kannst Du Deinen Code mal irgend wo pasten?
Desweiteren ist mir noch nicht klar, wieso man sich so viele Felder merken muss. Werden denn nicht nur die geändert, auf denen sich die Ameise gerade befindet? Das wäre ja eigentlich nur eines ... aber vermutlich kenne ich den Algo zu wenig. Zumindest beim Vorgehen des Wikipedia Artikels sollte das aber so sein.
OK hier der ganze Code auf eigene Gefahr:Hyperion hat geschrieben:Also ich kann das nicht glauben! Die besuchten Felder müssen doch um ein vielfaches weniger sein, als das gesamte statische Spielfeld! Also muss doch eine Variante, in der man sich gezielt nur die benötigten Felder abarbeitet schneller sein (zumindest mal von den Algorithmus-Schritten).Ydope hat geschrieben: OK dann werde ich das probieren und mich über diese Methoden informieren. Aber erst morgen. Will das jetzt nicht schon wieder umbauen und muss erstmal genau kapieren, was du meinst und ob das möglich ist.
Letztendlich wirds trotzdem langsamer als der bisherige Weg sein
Kannst Du Deinen Code mal irgend wo pasten?
Desweiteren ist mir noch nicht klar, wieso man sich so viele Felder merken muss. Werden denn nicht nur die geändert, auf denen sich die Ameise gerade befindet? Das wäre ja eigentlich nur eines ... aber vermutlich kenne ich den Algo zu wenig. Zumindest beim Vorgehen des Wikipedia Artikels sollte das aber so sein.
http://pastebin.com/m331663db
Die Hauptschleife ist in aufgehts()
Die ersten sechs Funktionen von def truchet bis def draw_bigant kannst du erstmal ignorieren.
Jeder Schritt läuft so ab, dass alle Ant-Instanzen nacheinander aufgerufen werden (default-mäßig bleibt das nur eine).
Dort dreht sich dann die Ameise, ändert den Zustand der Zelle, malt ggf. (siehe unten) die Zelle auf den Bildschirm, und geht eine Zelle weiter.
Dann kommt der nächste Schritt, usw.
Bei langsamer Geschwindigkeit (änderbar mit den links und rechts Tasten) wird jeder Schritt einzeln gemalt, innerhalb der "Ant"-Klasse.
Bei höheren wird alle 100.000 oder mehr Schritte screenupdatefull() ausgeführt und damit das komplette Fenster neu gezeichnet. Daher steht viel draw-Code letztendlich zweimal drin.
PS: Dinge, die diese dictionary-Sache betreffen, findest du in den Zeilen 163, 216 und 392. Ist jetzt aber erstmal alles wieder rausgeflogen und back-to-normal.
Gruß
Für meinen Geschmack viel zu viele ``if``/``elif``-Abfragen, die ich mit "Daten" im weitesten Sinne lösen würde. Bei allem was in anderen Sprachen mittels ``switch``/``case`` gelöst würde, sollte man schauen ob man ein Dictionary einsetzen kann.
`maxdirection` ist anscheinend statisch, wenn es Dir also *so* auf Geschwindigkeit ankommt, ist es recht unsinnig darauf zur Laufzeit ständig zu prüfen. An der Stelle könnte man zum Beispiel überlegen ob man Unterklassen von `Ant` bildet die mit verschiedenen Anzahlen von Richtungen klar kommen und einmal am Anfang ein Exemplar der passenden Ameisenunterart erzeugen.
Allerdings treibt Dein Geschwindigkeitswahn sowieso komische Blüten. Benutze einfach kein Python. Jedenfalls nicht wenn der Preis Klassen sind, in denen auf globale Variablen zurückgegriffen wird um Zeit zu sparen. Da kann man dann auch gleich Fortran nehmen.
`maxdirection` ist anscheinend statisch, wenn es Dir also *so* auf Geschwindigkeit ankommt, ist es recht unsinnig darauf zur Laufzeit ständig zu prüfen. An der Stelle könnte man zum Beispiel überlegen ob man Unterklassen von `Ant` bildet die mit verschiedenen Anzahlen von Richtungen klar kommen und einmal am Anfang ein Exemplar der passenden Ameisenunterart erzeugen.
Allerdings treibt Dein Geschwindigkeitswahn sowieso komische Blüten. Benutze einfach kein Python. Jedenfalls nicht wenn der Preis Klassen sind, in denen auf globale Variablen zurückgegriffen wird um Zeit zu sparen. Da kann man dann auch gleich Fortran nehmen.