Design, game of life

Hallo, ich möchte conway's spiel des lebens umsetzen. Ich brauch ja wohl 2 arrays oder vektoren mit zellen (temp für neue Generation). Würdet ihr ein array mit booleans oder mit struct/ class von zellen füllen. Ich hab angst vor geschwindigkeitsverlust bei etwas wie:

class Cell{;;}; 
Cell cells[300][300];

90000 bools oder cells?

pumuckl

conway schrieb:

Hallo, ich möchte conway's spiel des lebens umsetzen. Ich brauch ja wohl 2 arrays oder vektoren mit zellen (temp für neue Generation).

Brauchst du? Das was du geschrieben hast sind aber nicht 2 Arrays sonder ein zweidimensionales Array.

Würdet ihr ein array mit booleans oder mit struct/ class von zellen füllen.

Falls das eine Frage ist: kommt drauf an. Ist eine Designfrage, hängt also davon ab was ich umsetzen will und wie. Vermutlich würde ich aber nicht auf ein Array sondern auf einen der Standardcontainer zurückgreifen.

Ich hab angst vor geschwindigkeitsverlust bei etwas wie:
class Cell{;;}; Cell cells[300][300];
90000 bools oder cells?

Die Größe hat an sich erstmal nichts mit Geschwindigkeit sondern mit Speicherplatz zu tun. Bei ungünstigen Algorithmen kann sich das natürlich auf die Geschwindigkeit auswirken. Allerdings sollte man sich grundsätzlich erstmal einen gut skalierenden Algorithmus überlegen und sich danach dann KEINE Gedanken über Geschwindigkeiten machen, bis einem die Tests und der Profiler erzählen, dass es genau an der Stelle Probleme gibt.

Ich brauch 2 2d arrays. Das erste ist aktuell. Das 2te die nächste generation. Also 180k einträge die auch noch geswapt werden

drakon

conway schrieb:

Ich brauch 2 2d arrays. Das erste ist aktuell. Das 2te die nächste generation. Also 180k einträge die auch noch geswapt werden

Wie gesagt hat das etwas mit Speicherplatz zu tun, aber auch das ist da nicht wirklich ein Problem. Für die Geschwindigkeit spielt es kaum eine Rolle, ob du da jetzt Cells, oder bools hast. (Ausser der Zugriff stellt sich schlussendlich als der Flaschenhals heraus). Aber wie gesagt mach dir da mal keine Gedanken. Programmiers und dann schau am Schluss, ob es wirklich etwas ausmacht. So am Anfang kann man das schwer sagen.

Hey, danke für die schnellen antworten. Der speicherplatz für klasseninstanzen müsste reichen. Mal ausrechnen

pumuckl

wenn ich mich recht erinnere gehts beim Spiel des Lebens darum, dass eine Zelle ihren neuen Zustand aus den alten Zuständen der 4 unmittelbaren Nachbarzellen berechnet. Ich würde da eine einzelne Datenstruktur nehmen, in dem Fall vermutlich sogar tatsächlich ein Array:

size_t width = 300, height = 300;
Cell* cells = new Cell[2][width][height];

for (int i = 0; i < width; ++i)
for (int j = 0; j < height; ++j)
{
  //fülle cells[0][i][j] mit Initialwerten
}

for (size_t n = 0; n <= (num_steps/2)+1; ++n)
{
  for (int i = 0; i < width; ++i)
  for (int j = 0; j < height; ++j)
  {
    //berechne cells[1][i][j] aus cells[0][i-1][j], cells[0][i][j+1] usw.
  }
  draw(cells[1]);

  if (num_steps % 2) break; 

  for (int i = 0; i < width; ++i)
  for (int j = 0; j < height; ++j)
  {
    //berechne cells[0][i][j] aus cells[1][i-1][j], cells[1][i][j+1] usw.
  }
  draw(cells[0]);
}

delete[] cells;

Das Ganze ist übrigens eine nette Aufgabe für Parallelisierung

pumuckl schrieb:

wenn ich mich recht erinnere gehts beim Spiel des Lebens darum, dass eine Zelle ihren neuen Zustand aus den alten Zuständen der 4 unmittelbaren Nachbarzellen berechnet.

Sogar alle 8 nachbarn sind entscheidend. Btw danke, aber deinen code kann ich auf dem handy zzt schwer entziffern. Bin mal gespannt.
Erste kopfrechnungen ergeben: array bool ca 180 KB, mit etwa 100B instanzen ~18 mb, hui

drakon

Erste kopfrechnungen ergeben: array bool ca 180 KB, mit etwa 100B instanzen ~18 mb, hui

Warum soll eine Instanz 100 B(yte?) gross sein?! Oder verstehe ich deine Aussage falsch? Wenn du nicht schon direkt bool Arrays benutzt, dann wirst du eh nicht viel speichern müssen. Das sollte also nicht soo viel ausmachen..

Fellhuhn

Kannst natürlich um Speicher zu sparen mit std::vector<bool> oder std::bitset<90000> arbeiten.

drakon schrieb:

Warum soll eine Instanz 100 B(yte?) gross sein?!

Hast Recht, war ein bissel viel.

pumuckl schrieb:

Das Ganze ist übrigens eine nette Aufgabe für Parallelisierung

Meinst Du das allgemein oder um Performance zu sparen?

Denn hiersteht:

Der Hauptgedanke des Spieles besteht darin, daß Leben und Tod gleichzeitig und nicht nacheinander auftreten. Die Regeln werden auf die gegebene Spielsituation angewandt, indem man nacheinander alle Felder untersucht und diese als Überlebende, als Opfer oder als Geburt kennzeichnet. Auf einen Schlag ergeben sich alle Veränderungen, und eine neue Generation entsteht.

Ich habe ein Javaprogramm gesehen wo threads "lediglich" zur performancesteigerung genutzt werden. Da wird das spielfeld durch 2,4 oder 8 (etc) geteilt. Die einzelnen Felder werden vom Nachbarn geweckt wenn sie veränderungen haben. die steuerung machen dann threads

pumuckl

conway schrieb:

pumuckl schrieb:

Das Ganze ist übrigens eine nette Aufgabe für Parallelisierung

Meinst Du das allgemein oder um Performance zu sparen?

Sowohl als auch. Derartige Berechnungen, wo wie hier alle Elemente einer Matrix quasi gleichzeitig berechnet werden lassen sich relativ einfach parallelisieren und sind daher häufig als Beispiel und/oder Übungsaufgabe in den entsprechenden Büchern und Vorlesungen anzutreffen. Natürlich macht in einer "echten" Anwendung parallelisierung nur dann Sinn wenn das Programm dann wirklich performanter läuft.

pumuckl schrieb:

Sowohl als auch. Derartige Berechnungen, wo wie hier alle Elemente einer Matrix quasi gleichzeitig berechnet werden lassen sich relativ einfach parallelisieren.

das werde ich im hinterkopf behalten.

Danke an alle.
Ich habe das grundgerüst des spiels in knapp 1 stunde aufgebaut.
2 array's waren überflüssig. In der klasse gibts dafürn bool act und bool next.

Wie kann ich diesen Thread als gelöst markieren?

pumuckl

conway schrieb:

Wie kann ich diesen Thread als gelöst markieren?

indem du deinen ersten Betrag editierst und den Titel entsprechend änderst