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

Dienstag 16. Dezember 2008, 16:19

Genau. Die Felder können auch weitere Zustände/Farben haben. Das ist z.B. hier erklärt: http://en.wikipedia.org/wiki/Langton%27 ... on.27s_ant
Außerdem kann meine Variante nicht nur auf einem Spielfeld mit quadratischen Zellen laufen, sondern auch mit sechseckigen Zellen. Da kennt der Automat dann auch nicht nur "dreh dich 90° nach links bzw. rechts", sondern er kann sich 60° und 120° in beide Richtungen drehen bevor er einen Schritt weiter geht.
Ferner können mehrere Automaten gleichzeitig rumlaufen und noch ein paar weitere Kleinigkeiten.

Wie meinst du das mit dem Merken? Ich habe momentan dieses Array oder verschachtelte Liste oder wie immer man das nennt:

Code: Alles auswählen

feldb = [[False for x in xrange(fsize)] for y in xrange(fsize)] #feld besucht(y/n)
Wenn das Feld x,y besucht wurde, wird es True. In der Hauptschleife:

Code: Alles auswählen

        if feldb[self.x][self.y] == False: 
            visited_count += 1     
            feldb[self.x][self.y] = True 
visited_count zählt global die besuchten Felder.

Wenn ich eine einfache Liste hätte mit den Koordinatenpaaren aller besuchten Felder, wäre zwar das Darstellen aller besuchten Felder schneller, aber dann müsse ich ja jedesmal wenn ein Feld betreten wird, die ganze Liste durchschauen, ob das aktuelle Feld schon drinsteht. Oder?
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Dienstag 16. Dezember 2008, 16:49

Ydope hat geschrieben:Wenn ich eine einfache Liste hätte mit den Koordinatenpaaren aller besuchten Felder, wäre zwar das Darstellen aller besuchten Felder schneller, aber dann müsse ich ja jedesmal wenn ein Feld betreten wird, die ganze Liste durchschauen, ob das aktuelle Feld schon drinsteht. Oder?
Nicht in dem Sinne, dass du die Liste durchlaufen müsstest - dafür gibt es den "in"-Operator. Ob es damit schneller geht als mit den beiden parallelen Listen könntest du ja ausprobieren.
Ydope
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Dienstag 16. Dezember 2008, 17:18

Da stehe ich etwas auf dem Schlauch und weiß ncht ob wir das gleiche meinen.
Meine eigentliche Schleife ohne die Darstellung soll möglichst schnell sein. Das ist die Hauptpriorität.
Und die ist doch sicher langsamer, wenn ich nach jedem Schritt mittels "in" nachschaue, ob das Feld schon in einer Liste von Koordinatenpaaren ist (und falls es das nicht ist, anhänge), als wenn ich nur schaue, ob das eine Feld in der 2-dimensionalen Liste feldb[x][y] True ist (und falls es False ist, auf True setze). Es können ja durchaus Hunderttausende Felder schon besucht worden sein.
Wenn du wirklich meinst, dass das sein kann, prüfe ich das aber mal.

Gruß
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Dienstag 16. Dezember 2008, 17:40

Ydope hat geschrieben:Wenn du wirklich meinst, dass das sein kann, prüfe ich das aber mal.
Nein, meine ich nicht. Ich *weiß* es schlicht nicht, aber da sich der Aufwand, es zu probieren, in Grenzen hält, würde ich es einfach mal ausprobieren. Im übrigen dürfte es mit einer Menge (set) statt einer Liste evtl. schneller laufen bei dieser Größenordnung (die mir nicht bewusst war). Aber auch das lässt sich ja einfach ausprobieren und testen ... :wink:
sea-live
User
Beiträge: 440
Registriert: Montag 18. Februar 2008, 12:24
Wohnort: RP

Dienstag 16. Dezember 2008, 19:30

ich glaube es wäre für dich sehr nützlich unter pygame mal das Arcade spiel crush roller zu analysieren wie dieser programmierer das ganze gelöst hat.
Benutzeravatar
Hyperion
Moderator
Beiträge: 7472
Registriert: Freitag 4. August 2006, 14:56
Wohnort: Hamburg
Kontaktdaten:

Dienstag 16. Dezember 2008, 20:16

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

Dienstag 16. Dezember 2008, 20:32

Ich glaube ich hatte schon einmal vorgeschlagen: Ein Dictionary. Da kann man dann auch gleich den Wert der besuchten Felder speichern.
Ydope
User
Beiträge: 19
Registriert: Freitag 12. Dezember 2008, 17:22

Dienstag 16. Dezember 2008, 20:49

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

Dienstag 16. Dezember 2008, 21:30

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

Dienstag 16. Dezember 2008, 21:54

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

Dienstag 16. Dezember 2008, 22:40

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
User
Beiträge: 2465
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

Dienstag 16. Dezember 2008, 22:42

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

Dienstag 16. Dezember 2008, 22:51

DasIch hat geschrieben:
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.
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.
Benutzeravatar
numerix
User
Beiträge: 2696
Registriert: Montag 11. Juni 2007, 15:09

Dienstag 16. Dezember 2008, 22:52

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)])
Benutzeravatar
str1442
User
Beiträge: 520
Registriert: Samstag 31. Mai 2008, 21:13

Dienstag 16. Dezember 2008, 23:02

Ydope:

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