Wie komme ich am schnellsten durch mein Array?

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 » Dienstag 16. Dezember 2008, 23:09

@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
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Beitragvon Ydope » Dienstag 16. Dezember 2008, 23:14

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
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Beitragvon Ydope » Dienstag 16. Dezember 2008, 23:19

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


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

Gruß :wink:
Benutzeravatar
Hyperion
Moderator
Beiträge: 7471
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Beitragvon Hyperion » Dienstag 16. Dezember 2008, 23:27

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

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
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Beitragvon Ydope » Mittwoch 17. Dezember 2008, 00:04

Hyperion hat geschrieben:
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 :roll:

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

Beitragvon BlackJack » Mittwoch 17. Dezember 2008, 00:42

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. :?

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder