Wie komme ich am schnellsten durch mein Array?

[Hyperion]

Wieso nimmst Du nicht ein set für die bereits besuchten Felder? Da müßtest Du ja nicht gucken, ob es bereits enthalten ist, oder?

[BlackJack]

Ich glaube ich hatte schon einmal vorgeschlagen: Ein Dictionary. Da kann man dann auch gleich den Wert der besuchten Felder speichern.

[Ydope]

Ok ich werde einen Benchmark machen mit der momentanen Variante, mit Set und mit Dictionary.

@ sea-live: ich finde dort das Spiel "crush roller" leider nicht.

[Ydope]

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.

[BlackJack]

@Ydope: Was meinst Du mit "nicht sequenzierbar"? Man kann Tupel mit Zahlen drin in einem `set()` speichern bzw. als Schlüssel in Dictionaries verwenden.

[Ydope]

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?

[DasIch]

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.

dicts _sind_ Container...

[Ydope]

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.

dicts _sind_ Container...

Was willst du mir damit sagen?
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.

[numerix]

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

[str1442]

Ydope:

Du schmeißt das neue set() weg, und versucht die Add methode der *Klasse* set ohne Instanz aufzurufen.

[BlackJack]

@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`.

[Ydope]

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.

[Ydope]

@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`.

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

Gruß

[Hyperion]

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

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

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.

[Ydope]

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

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

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:
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ß

[BlackJack]

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.