![[ICO]](/icons/blank.gif){kind=icon}
![[DIR]](/icons/back.gif){kind=icon}
![[ ]](/icons/unknown.gif){kind=icon}
![[TXT]](/icons/text.gif){kind=icon}
![[ ]](/icons/layout.gif){kind=icon}
![[ ]](/icons/compressed.gif){kind=icon}
Auszug aus dem Wikipedia-Artikel:
The Game of Life is a cellular automaton devised by the British mathematician John Horton Conway in 1970. It is the best-known example of a cellular automaton.
The "game" is actually a zero-player game meaning that its evolution is determined by its initial state needing no input from human players. One interacts with the Game of Life by creating an initial configuration and observing how it evolves.
Nachdem die Startkonfiguration festgelegt wurde läuft jeder Schritt (oder "Tick") nach diesen Regeln ab:
Als "Nachbarn" gelten dabei die acht umliegenden Zellen. Es existieren auch viele Variationen mit anderen Zahlen dies ist jedoch die bekannteste und originale Version.
Gegeben war ein naiv implementiertes Programm das vom Standardinput eine Konfiguration einlas und von dieser ausgehend eine per Parameter spezifizierte spätere Konfiguration berechnete und ausgab.
Ziel war es nun dieses Programm durch allgemeine Optimierung effizienter und damit auch benutzbar zu machen. Dabei gab es keine genaueren Vorgaben außer dass die Funktionalität und Korrektheit erhalten bleiben mussten.
Der Originalalgorithmus speicherte alle lebenden Zellen in einer einfach verketteten Liste die für jeden Tick neu erzeugt wurde.
In jeder Generation wurden nun alle Zellen der Reihe nach durchgegangen und überprüft ob diese überleben. Dann wurde für jede Nachbarzelle überprüft ob sie zum Leben erwacht was insgesamt für jede lebende Zelle mehrere zig Suchen in einer unsortierten Liste zur Folge hatte.
Die Frage war nun wie man diesen offensichtlich grauenvollen Algorithmus verbessern sollte. Wir kamen hier auf den Gedanken dass die gesamten Suchen in der Liste bloß nach Zellen im unmittelbaren Umfeld der gerade betrachteten Zelle waren. Daher gab es hier eine sehr große Lokalität die man ausnutzen musste.
Dazu behielten wir den Grundgedanken die lebenden Zellen in einer Liste zu speichern bei. Um allerdings die Suchen zu beschleunigen änderten wir die Liste in eine doppelt verkettete ab und führten eine neue redundante Zelleigenschaft "xy" (= x + y) ein nach der wir die Liste sortierten.
Dadurch mussten wir beim Suchen nun nur mehr die Zellen mit xy-Werten betrachten die sich um höchstens 4 von dem der derzeitigen Zelle unterschieden was eine enorme Lokalität bedeutete. Insgesamt machte alleine diese Verbesserung das Programm um den Faktor 157 schneller.
Die weiteren Optimierungen bauen auf dieser auf sind aber nebensächlicher als diese weswegen wir sie hier nicht anführen. Sie werden aber in der Präsentation ausführlich erklärt. Dort findet sich auch eine gute Veranschaulichung des eben beschriebenen Verfahrens.
Das Programm wird in folgender Weise ausgeführt:
life #generations < f0.l
Die Ausgabe ist eine Liste aller lebenden Zellen nach #generations Generationen im Eingabeformat.
Das Programm wurde mit gegebenem Input (Datei "f0.l" mit 315 Zellen Berechnung von 3000 Generationen) mit Hilfe des Programms "papiex" sowohl im Originalzustand als auch in den einzelnen Verbesserungsschritten gemessen. Die Werte einzelner Schritte finden sich in der Präsentation hier werden nur kurz die Endergebnisse präsentiert.
Die Vermessung des Originalprogramms ergab laut Angabe:
Die Performance unseres Endprogramms war wie folgt:
Das Programm wurde geschrieben von Torsten Gerfertz Christian Pernegger und Thomas Seidl.
| Name | Last modified | Size | Description |
|---|---|---|---|---|
| Parent Directory | - | ||
| Makefile | 19-Jan-2008 00:46 | 311 | |
| f0.l | 26-Nov-2007 13:46 | 2.5K | |
| life1.h | 08-Dec-2007 13:23 | 299 | |
| life4.c | 11-Dec-2007 20:46 | 15K | |
| life5.c | 11-Dec-2007 20:41 | 16K | |
| papiex_output.txt | 10-Dec-2007 22:57 | 201 | |
| praesentation.pdf | 11-Dec-2007 14:47 | 100K | |
| programm.zip | 19-Jan-2008 00:51 | 8.0K | |
| readlife1.y | 03-Dec-2007 16:39 | 956 | |