Auf ein neues! Game of Life 2D

Code-Stücke können hier veröffentlicht werden.
Antworten
Kaffee
User
Beiträge: 3
Registriert: Mittwoch 9. Mai 2007, 20:44

Mittwoch 9. Mai 2007, 21:09

Hi all!

Erstmal ein hallo an die Python gemeinde hier :)

Hab die Tage mal in Python und dieses Forum hier reingeschnuppert.
Durch dieses Forum hier bin auch auf das "Game of Life" gestoßen und dachte mir: "Hey, ein super Projekt um bissel mit Python zu spielen!"

Gesagt - Getan! Also hier ist mein erstes Python Projekt :)
Wäre froh, wenn ihr mal eure Meinung und evtl. Verbesserungen äußert!
Vielleicht hab ich ja irgendwelche Features von Python übersehen und es mir umständlich gemacht oder ähnliches.

Gruß, Kaffee

Quellcode: http://paste.pocoo.org/show/1485/
BlackJack

Mittwoch 9. Mai 2007, 23:00

Herzlich willkommen. Und nun gleich die gnadenlose Kritik. :-)

Einige Zeilen sind länger als 80 Zeichen. Die Namen richten sich nach den wxPython-Namen, also nicht nach den Namenskonventionen im Python Style Guide.

`_MySort()` könnte eine Funktion sein, da `self` gar nicht benutzt wird. Es wird in der inneren Funktion `cmp()` nachprogrammiert. Das ginge auch so:

Code: Alles auswählen

    def _MySort(self, index):
        def sort(x, y):
            return cmp(x[index], y[index])
        return sort
Wobei man beim sortieren aber nach Möglichkeit das `key`-Argument anstelle von `cmp` benutzen sollte. Die `cmp`-Funktion wird bei jedem Vergleich aufgerufen, die `key`-Funktion nur einmal für jedes Element. Mit `operator.itemgetter()` gibt's auch schon eine passende Funktion die Du benutzen kannst.

Anstelle von `range()` sollte man `xrange()` verwenden, weil `range()` eine Liste mit Zahlen erzeugt, die meistens gar nicht gebraucht wird.

Das Testen, ob die zweielementige Liste in `self._aliveArray` enthalten ist, hat lineare Laufzeit. Der Test ob ein Tupel in einem `set` enthalten ist, ist schneller. Das wäre ein Beispiel, warum die Datenstruktur nicht unbedingt in der Namensgebung auftauchen sollte. Wenn man auf ein `set` umstellt, passt der Name `_aliveArray` nicht mehr. `_aliveCells` passt in beiden Fällen und würde auch noch passen wenn man statt `list` oder `set` einen binären Suchbaum dafür benutzt.

Allerdings verstehe ich den Test nicht so ganz: Wenn die Koordinaten in `_aliveArray` sind, dann braucht man den anschliessenden Test ob da eine 1 steht nicht. Und wenn man diesen Test macht, hätte man vorher nicht in `_aliveArray` nachsehen müssen. Letztendlich würde es doch genügen einfach alle Nachbarzellen von Zelle (x, y) in `n` aufzuaddieren ohne überhaupt irgend etwas zu testen. Tote Nachbarn gehen mit 0 in diese Summe ein und lebende mit 1.

Das Spielfeld kann man mit einer "list comprehension" kompakter initialisieren.

Code: Alles auswählen

    def SetSize(self, size):    
        self._aliveArray = []
        self._size = size
        self._array = [[0] * size for dummy in xrange(size)]
Attribute sollten nur in der `__init__()` neu eingeführt werden. Das ist übersichtlicher und sicherer.

Getter und Setter sind in Python nicht üblich, das regelt man üblicherweise über Properties. Siehe Doku zur `property()`-Funktion.

Ein einfaches ``return`` hätte genügt um `NextGen()` vorzeitig zu verlassen.

Das sortieren ist ziemlicher Overkill um die "bounding box" der lebenden Zellen zu ermitteln. Um das letzte Element einer Liste anzusprechen kann man den Index ``-1`` benutzen. Mit `imap()` aus `itertools` und `itemgetter()` aus `operator` wäre es etwas übersichtlicher zu lösen:

Code: Alles auswählen

        minY = min(imap(itemgetter(0), self._aliveArray))
        maxY = max(imap(itemgetter(0), self._aliveArray))
        minX = min(imap(itemgetter(1), self._aliveArray))
        maxX = max(imap(itemgetter(1), self._aliveArray))
Aber ich würde es in eine Funktion auslagern:

Code: Alles auswählen

def bounding_box(cells):
    min_y = max_y = min_y = max_x = None
    for y, x in cells:
        min_y = min(min_y, y)
        max_y = max(max_y, y)
        min_x = min(min_x, x)
        max_x = max(max_x, x)
    return (min_y, max_y, min_x, max_x)
Aufruf mit:

Code: Alles auswählen

       min_y, max_y, min_x, max_x = bounding_box(self._aliveArray)
Diese Indexanpassungen haben mich total durcheinandergebracht. Indexe fangen bei den meisten Programmiersprachen bei 0 an. Das sollte man nicht künstlich ändern wollen. Es ist verwirrend und fehleranfällig.

In `IsAlive()` wird wieder der lineare Test auf enthaltensein in `self._aliveArray` gemacht. Es wäre schneller, einfach in `self._array` nachzuschauen. Ausserdem ist das Ergebnis des `in`-Operators schon `True` oder `False`, dass hätte man also kürzer schreiben können.

`ChangeStatus()` macht in beiden Zweigen der ``if``-Anweisung relativ ähnliche Sachen, die man da herausziehen kann:

Code: Alles auswählen

    def ChangeStatus(self, x, y):
        tmpX, tmpY = x - 1, y - 1
        # 
        # Zustand einer Zelle "umdrehen".
        # 
        new_value = self._array[tmpY][tmpX] = abs(self._array[tmpY][tmpX] - 1)
        self._updateCallback(x, y, new_value)
        if new_value:
            self._aliveArray.remove([tmpY, tmpX])
        else:
            self._aliveArray.append([tmpY, tmpX])
Hier sind/waren wieder mehr Kosten in Form von Laufzeit mit der Liste beim Enthaltensein-Test und `remove()` vorhanden, als das bei einem `set` der Fall wäre.

Insgesamt bezweifle ich ob `_aliveArray` überhaupt etwas bringt, oder ob das Programm nicht schneller wäre ohne diese "Optimierung". Auch bei einem `set` kostet das wahrscheinlich mehr Laufzeit als die Bereichseinschränkung einbringt.

Die Kommetare zu den Methoden wären ideale Kandidaten für "Docstrings".
Kaffee
User
Beiträge: 3
Registriert: Mittwoch 9. Mai 2007, 20:44

Donnerstag 10. Mai 2007, 01:25

Hi BlackJack!

Danke für deine Kritik!
Viele Sachen waren mit neu und ich hab auch öfters das wiki und google fragen müssen aber hey, ich habs soweit alles Verstanden und mal umgesetzt 8)

Hab den Quellcode auch nochmal überdacht und dabei das Spielfeld um das Attribut `_array` komplett erleichtert. Wenn ich mir schon merke an welchen Positionen leben steckt hab ich doch schon alle infos :roll:

Das `_aliveArray` (jetzt übrigens `_cells`) und die Boundingbox machen schon ne menge an speed. Ohne die Box müsste ich ja jedes Feld prüfen, auch wenn dort faktisch kein Leben entstehen kann!

Wäre nett, wenn du dir meine Überarbeitet Version mal angucken würdest.

Gruß, Kaffee

Quellcode: http://paste.pocoo.org/show/1488/

/Edit:

WOW! Die Änderungen haben es echt gebracht :)
Bei 1225 zu prüfenden Zellen (Spielfeldgröße 35) brauch V0.1 ~0,14 sek und V0.2 ~0.02 sek... Nüsch schlecht 8)
BlackJack

Donnerstag 10. Mai 2007, 08:51

Die Abfrage der Regeln zum (wieder)beleben enhalten alle den gleichen Code, das könnte man in einer ``if``-Abfrage zusammenfassen. Wenn ich mich nicht irre, müsste es so gehen:

Code: Alles auswählen

                if ((not living and neighbours == 3)
                    or (living and neighbours not in (2, 3))):
                    changes.add((x, y))
Wie schon gesagt gibt der ``in``-Operator `True` oder `False` zurück:

Code: Alles auswählen

    def is_alive(self, x, y):
        """ Prüft ob eine Position im Array am leben ist """
        return (x, y) in self._cells
Die "bounding box" bringt einen richtigen Vorteil solange die äusseren Grenzen klein bleiben. Wenn man "Floater" hat, die in gegensätzliche Richtungen wandern, testet man trotzdem ziemlich viele leere Zellen. Wenn man ein sehr grosses Feld hat, vielleicht sogar ein "unendlich" grosses, das `set` verbraucht ja nur Speicher für lebende Zellen, macht es Sinn sich nur die Zellen rund um lebende Zellen anzuschauen. Denn nur dort kann im nächsten Schritt neues Leben entstehen.

Ich hatte das letztes Jahr übrigens auch mal implementiert: http://www.python-forum.de/topic-5754.html
Kaffee
User
Beiträge: 3
Registriert: Mittwoch 9. Mai 2007, 20:44

Donnerstag 10. Mai 2007, 10:40

BlackJack hat geschrieben: Die "bounding box" bringt einen richtigen Vorteil solange die äusseren Grenzen klein bleiben. Wenn man "Floater" hat, die in gegensätzliche Richtungen wandern, testet man trotzdem ziemlich viele leere Zellen. Wenn man ein sehr grosses Feld hat, vielleicht sogar ein "unendlich" grosses, das `set` verbraucht ja nur Speicher für lebende Zellen, macht es Sinn sich nur die Zellen rund um lebende Zellen anzuschauen. Denn nur dort kann im nächsten Schritt neues Leben entstehen.
Ab und zu könnt ich mich selbst schlagen. Ja, klar. Hast recht.
War aber gestern auch schon spät :oops: :lol: 8)

Vielen Dank nochmal für deine mühe mit meinem Gedankenwust ^^

Gruß, Kaffee
Antworten