Ruprecht Karls Universität Heidelberg

TippsAndTricks

From Informatik-Vorkurs
Jump to: navigation, search

Sortieren mit Rekursion

Der in der Übung implementierte Sortieralgorithmus ist nicht effizient: Bei einer Liste der GrĂ¶ĂŸe N steigt der Rechenaufwand (asymptotisch) quadratisch mit N. Eine bessere, konzeptionell einfache Methode ist es, die Liste zunĂ€chst in zwei HĂ€lften zu teilen, diese getrennt zu sortieren und die beiden HĂ€lften dann ineinander zu flechten. Die Methode arbeitet rekursiv, d.h. die geteilten Listen werden wieder geteilt u.s.w. bis triviale Listen aus nur einem Element entstehen, die gar nicht mehr sortiert werden mĂŒssen. Man bezeichnet dieses Verfahren als Mergesort. Hier ist eine primitive Implementierung zur Illustration gezeigt. Interessant ist die 'Sortiere'-Funktion, in der der rekursive Aufruf stattfindet. Das Vermengen der Listen ('Merge') wird hier mit einer Hilfsliste gemacht.

#include <iostream>

int number [] = {1,5,7,13,5,7,3,9,2,10};     // Schlecht: Globales Array
const unsigned int N = 10;                   // Auch nicht schön...    

void PrintArray (void)                       // Das Array ausgeben
{
  for (unsigned int i=0; i<N; i++)
    std::cout << number[i] << " ";
  std::cout << std::endl;
}

// Merge fĂŒgt die SORTIERTEN Teil-Listen, die sich bei den Indizes
//   istart ... imid  - 1
//   imid   ... istop - 1
// befinden, zusammen.
// Kopiere dazu das jeweils kleinere unterste Element in ein tmp[] array.
// Dann kopiere tmp[] zurĂŒck nach number[].

void Merge (int istart, int imid, int istop) // Obere Grenzen jeweils EXCLUSIVE!
{
  int tmp[N];                                // Vermische in diesen Zwischenspeicher
  int ilow  = istart;                        // Laufindex im 'unteren' Array
  int ihigh = imid;                          // .. und im 'oberen' Array
  for (int i=0; i<istop-istart; i++) {       // insgesamt istop-istart Elemente..
    if ( (ilow == imid) ||                   // Wenn untere Liste 'verbraucht'
        (number[ihigh] < number[ilow] ) )    // ODER (falls nicht) die obere Zahl kleiner als die untere:
      tmp[i] = number[ihigh++];              // Kopiere die obere Zahl (und erhöhe index)
    else                                     // Sonst:
      tmp[i] = number[ilow++];               // Nimm die untere Zahl
  }
  for (int i=0; i<istop-istart; i++)         // Kopiere zurĂŒck (ineffizient!!!)
    number[istart+i] = tmp[i];  
}

void Sortiere (int istart, int istop)        // Sortiere von istart bis istop-1 (!)
{
  if (istop - istart == 1) return;           // Abbruchbedingung: Liste aus einem Element ist trivial
  int imid = (istop + istart) / 2;           // Liste aufteilen (Teile sind nicht immer gleich!)
  Sortiere (istart, imid  );                 // Untere HĂ€lfte sortieren
  Sortiere (imid  , istop);                  // Obere HĂ€lfte sortieren
  Merge    (istart, imid, istop);            // 'Zusammenflechten'
}

int main (void)                              // Test: number[] ist schon gefĂŒllt (s.o.)
{
  PrintArray();
  Sortiere(0,N);
  PrintArray();
}

Bildschirmausgabe verbessern

Um die Ausgabe auf dem Textbildschirm etwas zu verbessern (fette Schrift, Farbe) kann man 'ANSI Escape Codes' benutzen. Das sind Steuerzeichen, die die Ausgabe in einen anderen Modus schalten. Eine gute Zusammenstellung der Codes gibt es z.B. unter [1]

Das folgende Programm gibt z.B. einen Text in blau bzw. in fetter Schrift aus und bewegt den Cursor auf dem Schirm nach oben:

#include <iostream>

const char * ToBlue   = "\x1b[34m";
const char * ToNormal = "\x1b[0m";
const char * ToBold   = "\x1b[1m";

void CursorUp(unsigned int n = 1)
{
  std::cout << "\x1b[" << n << "F" << std::endl;
}

int main(void)
{
  std::cout << "Escape Sequenzen:" << std::endl;
  std::cout << ToBold   << "Fetter Text";
  std::cout << ToBlue   << "in Blau";
  std::cout << ToNormal << std::endl;
  CursorUp(10);
  return 0;
}

AssemblerCode anschauen

Durch Parameter fĂŒr den Compiler kann man sich die temporĂ€ren Files mit den Assemblerbefehlen 'aufheben' und anschauen. Das File demo_assembler.cc

#include <iostream>
#include <iomanip>
 
int main (void)
{
  unsigned int start = 0;
  std::cin >> start;
  unsigned int sum = 0;
  for (unsigned int i = start; i<1234; i++)
    sum += i;
  std::cout << "Die Summe ist " << std::hex << sum << std::endl;
  return 0;
}

kann mit

g++ -fverbose-asm -S -O1 demo_assembler.cc

ĂŒbsersetzt werden. Die Ausgabe ist dann in demo_assembler.s. Der Inhalt ist sehr unĂŒbersichtlich und man muss etwas suchen, bis man den relevanten Teil findet. (Man kann z.B. nach 1234 suchen.) Der interessante Teil hier ist

...
    movl  28(%esp), %eax       # i mit Startwert fĂŒllen
    movl  $0, %ebx             # Summe auf Null setzen
    cmpl  $1233, %eax
    ja    .L7
.L13:
    addl  %eax, %ebx           # sum = sum + i
    addl  $1, %eax             # i = 1 + 1
    cmpl  $1234, %eax          # Vergleich
    jne  .L13
.L7:
...

FĂŒr den i-Wert der Schleife wird offenbar das Prozessorregister eax benutzt, fĂŒr die Summe ebx. Wenn Sie dies ausprobieren mĂŒssen Sie darauf achten, dass der Compiler sehr schnell unbenutzte Programmteile wegwirft. Daher ist es gut, eine Ein- und Ausgabe einzubauen.

Wie man die Anzahl gesetzter Bits in einem Wort findet

In der kompakten ScoreBoard Klasse wurden in (32 bit breiten) Worten einzelne Bits gesetzt. Am Ende musste die Anzahl der gesetzten Bits ermittelt werden. Der in der Musterlösung verwendte Code ist hierfĂŒr ĂŒberhaupt nicht effizient. Michael Ritzert hat mich auf ein paar Tricks hierzu hingewiesen. Diese sind auf den externen Seiten [2] oder auf [3] schön zusammengefasst.

Die Aufgabe ist es also, in einer 32 Bit Zahl unsigned int v die Anzahl gesetzte Bits c zu finden (z.B.: v=0x80000001 → c=2; v=0xFFFF00FF → c=24,...).

In den folgenden Codebeipielen wird fĂŒr eine kompakte 'elegante' Schreibweise ausgenutzt, dass in C++ jeder Wert außer 0 als true ausgewertet wird. Daher kann man if (x!=0) durch if (x) ersetzen.

Naheliegender Ansatz

Im folgenden (naheliegenden) Code werden alle 32 Bit angeschaut und c ggf. erhöht:

unsigned int c = 0;                               // ErgebniszÀhler
for (unsigned int ibit = 0; ibit < 32; ibit++) {  // immer 32 DurchlÀufe
  if (v & 1) c++;                                 // LSB prĂŒfen und ggf. c erhöhen
  v >>= 1;                                        // v schieben.
}

Die Zeile if (v & 1) c++ beinhaltet einen Sprung, der (je nach Architektur des verwendeten Prozessors) teurer sein kann als eine Addition. Daher ist die folgende Variante meist schneller, obwohl hier dauernd Nullen addiert werden:

unsigned int c = 0;                               // ErgebniszÀhler
for (unsigned int ibit = 0; ibit < 32; ibit++) {  // immer 32 DurchlÀufe
  c += v & 1;                                     // Funktion wie 'if'-Zeile oben, aber ohne Sprung
  v >>= 1;                                        // v schieben.
}

Anstelle v zu schieben kann man auch mit einer verÀnderlichen Maske arbeiten. Dies spart eine Instruktion pro Schleife und ersetzt die Addition von 1 zu ibit durch das (manchmal billigere) Schieben von mask.

 unsigned int c = 0;
 for (unsigned int mask = 0x1; mask; mask<<=1) {  // Wiederhole bis (mask == 0)
   if (v & mask) c++;
 }

Beide Routinen haben die großen Nachteil, dass die Schleife immer 32 Mal durchlaufen wird, selbst wenn v == 0!!!

Verbesserte Lösung

Hier bricht man ab, sobald v Null geworden ist. Man braucht also nur so viele DurchlĂ€ufe, wie die höchste gesetzte Stelle (v=0 → kein Durchlauf, v=0x1 → ein Druchlauf, v=0xF → 4 DurchlĂ€ufe, v=0x80000000 → 32 DurchlĂ€ufe).

unsigned int c;                                   // Initialisierung im Schleifenkopf
for (c = 0; v; v >>= 1) {                         // Schiebe v solange v!=0 
  c+= v & 1;                                      // Erhöhe c (s.o.)
}

SuperSchlaue Lösung

In dieser sehr schlauen Lösung ist die Idee, immer das niederwertigeste gesetzte Bit zu löschen. Dies kann man mit dem Befehl v &= v - 1; erreichen: Um das zu verstehen stellen wir v dar als v = ...xyz10...0 (die niedrigste gesetzte '1' ist gezeigt). Dann ist v-1 = ...xyz01...1 und das BITweise UND dieser beiden Werte ist ...xyz00...0!. Die folgende Schleife wird nur noch so oft durchlaufen, wie es Einsen in v gibt!

unsigned int c;
for (c = 0; v; c++) {                             // Wiederhole bis v == 0
 v &= v - 1;                                      // niedrigstes Bit löschen
}

SuperSuperSchlaue Lösung mit schlauer 'Bitklemptnerei'

Auch die bisherigen 'guten' Lösungen sind bei vielen gesetzten Bits noch 'teuer'. Es gibt einen sehr, sehr schlauen Ansatz, das Ergebnis in einem Schlag 'auszurechnen'. Dazu fasst man v zunĂ€chst als 16 Gruppen a 2 Bit (wir nennen sie mal 'ab') auf und 'zĂ€hlt' die Bits in den Zweiergruppen: Bei ab==00 hat man c=00 Einsen, bei ab==01 oder ab==10 sind es c=01 Einsen und bei ab==11 sind es c=10 Einsen. Man muss also in jeder Zweiergruppe aus den Möglichkeiten ab=00/01/10/11 die Ergebisse c=00/01/01/10 erreichen. Hier kommt der Trick: Man berechnet ab - a, was das gewĂŒnschte c ergibt, wie man leicht nachprĂŒfen kann. In Zeile 1 sieht man, dass man dazu v um eine Stelle nach rechts schiebt, so dass die a-s auf die rechte Stelle rutschen. Man muss dann aber noch alle b-s auf Null setzen, was durch bitweises UND mit 0x55555555 geht.

Die Berechnung geht dann damit weiter, dass die Zweiergruppen zu Vierergruppen zusammengefasst werden. Dazu greift man sich die eine HĂ€lfte der (16) Zweiergruppen heraus, indem man die anderen Bits auf Null maskiert. Die andere HĂ€lfte bekommt man genauso nach Schieben um 2 Stellen. Diese zwei Muster kann man auf einen Schlag addieren, da eine einzelne Zweiergruppe ('c' oben) ja maximal den Wert 2 hat, die Summe also maximal 4 sein kann, was gut in die zur VerfĂŒgung stehenden 4 Bit passt (es gibt also keinen 'Übertrag' in eine höhere Gruppe).

Anschließend werden (Zeile 3) entsprechend die Vierergruppen zusammengefasst. Hier muss man erst einmal nichts maskieren, da das vierte 'freie' Bit in den Gruppen reicht... Die 'ĂŒberflĂŒssigen' Bits werden erst danach wegmaskiert (Zeile 4), das spart eine Instruktion...

Am Ende werden die vier verbleibenden Gruppen (die jeweils maximal den Wert 8 haben können) addiert, was auch wieder mit einem Trick (Zeile 5) gemacht wird: Wir können v = ABCD schreiben, wobei in den 16 Bit Teilen A,B,C,D die jeweils oberen 8 Bit Null sind (durch Zeile 4). Dann ist v * 0x01010101 = D000 + CD00 + BCD0 + ABCD. Da es keine ÜbertrĂ€ge zwischen den Summanden gibt, ist die oberste Stelle einfach D+C+B+A! Diese schiebt man dann zur Einerstelle zurĂŒck.

v = v - ((v >> 1) & 0x55555555);                  // ZĂ€hle Bits in Zweiergruppen
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);   // Addiere Werte in Zweiergruppen -> 4er 
v = (v + (v >> 4));                               // Addiere Werte in Vierergruppen -> 8er
v &= 0x0F0F0F0F;                                  // Lösche unnĂŒtze Bits
c = (v * 0x01010101) >> 24;                       // Addiere die 4 Achtergruppen

Diese Methode zĂ€hlt die Bits also in konstanter Zeit, unabhĂ€ngig vom Eingangswert. Bei vielen gesetzten Bits ist sie deutlich schneller als die anderen AnsĂ€tze. Auf [4] gibt es einen Vergleich der Geschwindigkeiten fĂŒr unterschiedliche CPUs und interschiedlichen Input! Dort ist die Methode auch sehr schön erklĂ€rt.

Optimierungen fĂŒr das Spiel des Lebens

In einer der Übungen sollten Sie das Game of Life von J.H.Conway implementieren. An dieser Aufgabe kann man schön zeigen, wie man durch unterschiedliche Algorithmen unterschiedlich effiziente Versionen erzeugen kann. Betrachten wir zunĂ€chst eine sehr einfache Lösung (etwas anders als die Musterlösung):

Einfache Version

// Game of Life: Einfache Version
// ==============================

#include <iostream>

const int NX = 10, NY = 8;      // Zur Vereinfachung zunĂ€chst: FESTE FeldgrĂ¶ĂŸe

class T_life {
public:
       T_life (void);           // Konstruktor
  void print  (void);           // Ausgabe
  void set    (int, int);       // ein Feld setzen
  inline unsigned int neighbors (int, int);  // Berechne Nachbarschaft
  void iterate(void);           // einmal iterieren
  void iterate(int);            // n mal iterieren
private:
  bool world[NX][NY];           // Wie gesagt: ZunĂ€chst feste GrĂ¶ĂŸe
};

T_life::T_life (void)           // Konstruktor: lösche die Welt
{
  for (int iy = 0; iy < NY; iy++)
    for (int ix = 0; ix < NX; ix++)
      world[ix][iy] = false;
}

void T_life::print(void)        // Ausgabe
{
  for (int iy = 0; iy < NY; iy++) {
    for (int ix = 0; ix < NX; ix++)
      std::cout << (world[ix][iy] ? '*' : '.');
    std::cout << std::endl;
  }
  std::cout << std::endl;
}

void T_life::set(int ix, int iy)   // Ein Feld setzten
{
  world[(ix+NX)%NX][(iy+NY)%NY] = true; 
}

inline unsigned int T_life::neighbors (int ix, int iy)
{
  unsigned int sum = 0;
  for (int iiy = iy-1; iiy <= iy+1; iiy++)  {     // 3x3 Felder abarbeiten
    for (int iix = ix-1; iix <= ix+1; iix++) {
      if ((iix == ix) && (iiy == iy)) continue;   // das mittlere Feld auslassen
      if (world[(iix+NX)%NX][(iiy+NY)%NY]) sum++; // zÀhlen.
                                                  // NB: '+NX' ist nötig, da -1%NX leider -1!
    }
  }
  return sum;
}

void T_life::iterate(void)
{
  bool world2[NX][NY];                          // Speichere die 'neue Welt'
  for (int iy = 0; iy < NY; iy++)               // alle Felder abklappern
    for (int ix = 0; ix < NX; ix++) {
      unsigned int sum = neighbors(ix, iy);
      world2[ix][iy] = (sum==3) || (world[ix][iy] && (sum==2));
  }    
 
  for (int iy = 0; iy < NY; iy++)               // Jetzt kopiere world2 -> world
    for (int ix = 0; ix < NX; ix++)
      world[ix][iy] = world2[ix][iy]; 
}

void T_life::iterate(int n)
{
  for (int i=0; i<n; i++) {
    std::cout << "Iteration " << i << ":\n";
    iterate();
    print();
  }
}

int main ()
{
  T_life game;
  game.set(1,1); game.set(2,1); game.set(3,1);  // Linie
  game.set(4,4); game.set(5,4); game.set(6,4); game.set(6,5); game.set(5,6); // Glider
  game.print();
  game.iterate(8);
  return 0;
}

Zur Vereinfachung ist hier alles (Klassendefinition, Implementierung, und main()) in einem File untergebracht. Diese Version geht in jeder Iteration alle NX * NY Felder durch und berechnet fĂŒr jedes Feld die Umgebungssumme, was je 8 Zugriffe ins Array kostet, so dass wir insgesamt 8*NX*NY Zugriffe pro Iteration brauchen. Dieser Aufwand ist unabhĂ€ngig vom Inhalt der Welt, was ineffizient ist, da sich in der Praxis doch eigentlich nur sehr wenig pro Iteration Ă€ndert. Der neue Wert des Feldes fĂŒr die nĂ€chste Generation kann nicht sofort nach world[i][iy] geschrieben werden, da dann die Berechnungen der Nachbarn schon diesen neuen Wert nehmen wĂŒrden. Wir speichern daher die Werte fĂŒr die nĂ€chste Iteration in einer zweiten Welt (world2[][]) ab. Diese mĂŒssen wir dann wieder in die erste Welt zurĂŒckkopieren.

Das Umkopieren ist zwar nicht der dominierende Zeitaufwand, ist aber sehr unelegant. In der folgenden zweiten Version ist gezeigt, wie man das elegant lösen kann:

Vermeidung des Umkopierens mit Zeigern

// Game of Life: Pingpong Version:
// ====================================
// Benutze zwei (dynamisch angelegte) Arrays.
// Vertausche die Arrays nach einer Iteration durch 'Verbiegen' der Zeiger

#include <iostream>

class T_life {
public:
       T_life (int, int);       //NEU! Konstruktor bekommt jetzt die x-y-GrĂ¶ĂŸe
  void print  (void);           // Ausgabe
  ...
private:
  unsigned int NX, NY;          //NEU!
  bool ** world;                //NEU! Ein 'pointer' auf die aktive Welt
  bool ** world2;               //NEU! und auf die iterierte Welt.
                                //     Achtung: 2-dim arrays sind Pointers auf Pointers...
};

T_life::T_life (int nx, int ny)              // NEU! (der ganze Konstruktor)
{
  NX = nx; NY = ny;

  world  = new bool * [NX];                  // Arrays erschaffen
  for (unsigned int ix=0; ix<NX; ix++)
    world[ix] = new bool [NY];

  world2  = new bool * [NX];
  for (unsigned int ix=0; ix<NX; ix++)
    world2[ix] = new bool [NY];

  for (unsigned int iy = 0; iy < NY; iy++)   // Welt löschen
    for (unsigned int ix = 0; ix < NX; ix++)
      world[ix][iy] = false;
}

void T_life::iterate(void)
{
  for (unsigned int iy = 0; iy < NY; iy++)   // hier ist alles wie vorher!
    ...
  }    
  bool ** tmp = world2;                      // NEU!
  world2     = world;                        // Jetzt die Pointer vertauschen
  world      = tmp;                          // KEIN Umkopieren nötig!!!
}

int main ()
{
  T_life game(10,8);                         // einziger Unterschied in main(): GrĂ¶ĂŸe festlegen
  ...
}

Hier sind nun nur die verÀnderten Teile gezeigt! Anstelle mit festen Arrays arbeiten wir mit Zeigern auf Arrays (... world und world2 sind ja schon Zeiger!) und 'verbiegen' einfach die Zeiger am Ende von 'iterate(). Cool!

Wir haben außerdem die Arrays jetzt dynamisch angelegt. In der Klasse sind also nur die zwei Zeiger world und world2 definiert, im Konstruktor werden die Arrays dynamisch erschaffen. Im Detail ist das etwas tricky, da ein zweidimensionales Array ein Array von Arrays ist. Und da ein Array letztlich ein Zeiger auf den Anfang des Speicherbereichs ist, ist ein zweidimensionales Array ein Zeiger auf ein Array von Zeigern...

Der dominante Aufwand liegt aber offensichtlich nach wie vor im Abklappern aller Felder in JEDER Generation. Eine kleine Verbesserung wurde in der Aufgabenstellung der Übung genannt: Anstelle jedes Mal alle 8 Nachbarschaftsfelder anzuschauen, kann man sich auch ein Mal die Nachbarschaftssummen in einem weiteren (int) Array vorberechnen. In jeder Iteration muss man dann nur nachschauen, ob z.B. bei einem gesetzten Feld diese Summe <2 || >3 ist. Wenn ein Individuum stirbt oder geboren wird, muss man die Nachbarschaftsinformation der 8 Nachbarn korrigieren. Diese Methode spart also i.W. den Faktor '8'! Der Code ist hier nicht gezeigt.

Effiziente Version mit einer Liste von Änderungen

Wir Ă€ndern stattdessen unsere Herangehensweise grundsĂ€tzlich und ĂŒberlegen, dass sich in der Welt ja nur in der Umgebung von Individuen etwas Ă€ndern kann. Wir prĂŒfen also nur dort nach, ob Änderungen notwendig sind. Wenn es Änderungen in der Welt gibt, so merken wir uns die Koordinaten und schauen in der nĂ€chsten Generation nur dort nach etc... Der Aufwand ist dadurch völlig unabhĂ€ngig von der GrĂ¶ĂŸe der Welt, und hĂ€ngt nur von der 'AktivitĂ€t' ab. Statische Konfigurationen werden ĂŒberhaupt nicht mehr neu berechnet. Ein möglicher (schnell 'gehackter') Code sieht so aus:

// Game of Life - Mit einer 'TaskList':
// ====================================
// Lege zunÀchst eine Liste an, in der alle VerÀnderungen (Position, setzte/lösche) stehen.
// FĂŒhre dann diese VerĂ€nderungen (im gleichen Array) durch.
//
// Nutze bei den nĂ€chsten Iterationen aus, dass sich nur in der Umgebung der Änderungen
//   etwas Àndern kann!!!
// Damit diese Liste nicht unnötig (redundant) wĂ€chst, muss vor dem Eintrag geprĂŒft werden,
//   ob dieser Punkt schon bearbeitet wurde.
// Beachte: Wir bekommen so mehr EintrĂ€ge in der Taskliste als es wirklich Änderungen in der
//   Welt gibt, da wir ja alle 8 Felder um die geÀnderten Felder anschauen, und so ein
//   Feld mehrfach dran kommen kann. Bei der AusfĂŒhrung der Tasks werden die Dubletten dann
//   eliminiert. 

#include <iostream>
#include <vector>
using namespace std;

enum   Command {SET, CLEAR};    // Zur Lesbarkeit. Wird in struct Change benutzt
struct Pos     {int x,y;};      // Zur Lesbarkeit
struct Change  {                // Eintrag in der 'Task' Liste: Setze/Lösche and Position p
  Pos     p;
  Command cmd; 
};

class T_life {
public:
  T_life (int, int); 
  ...
  void CheckField (int ix, int iy); // PrĂŒfe ein Feld uns trage ggf. in Taskliste ein
private:
  unsigned int iter;              // ZĂ€hle Iteration, um ERSTE Iteration zu erkennen
  unsigned int NX, NY;            // Merke hier die GrĂ¶ĂŸe der Welt
  bool ** world;                  // Pointer auf die aktive Welt 
  std::vector <Change> Task;      // Liste von notwendigen Änderungen
  std::vector <Change> ChangePos; // Liste von tatsÀchlich verÀnderten Feldern.
                                  // Benutzt 'Change' Objekte, eigentlich reicht Pos!
};

T_life::T_life (int nx, int ny)
{
  NX = nx; NY = ny;
  world  = new bool * [NX]; ...              // Array erschaffen
  for ... world[ix][iy] = false;             // Welt löschen
 
  iter = 0;                                  // benötigt, damit wir die erste Iteration kennen
}

void T_life::CheckField (int ix, int iy)  // PrĂŒfe ein Feld uns trage ggf. in Taskliste ein
{
  unsigned int sum = neighbors(ix, iy);

  if (!world[ix][iy] && (sum==3)) {         // Geburt
    Change c; c.p.x = ix, c.p.y = iy; c.cmd = SET;
    Task.push_back(c);                      // Eine Geburt in die Taskliste eintragen
  }

  if ( world[ix][iy] && ( (sum<2) || (sum>3)) ) {
    Change c; c.p.x = ix, c.p.y = iy; c.cmd = CLEAR;
    Task.push_back(c);                      // Einen Todesfall eintragen
  }
}

void T_life::iterate(void)
{
  Task.clear();                                   // Liste mit Tasks leeren
  if (iter++ == 0) {                              // NUR bei ERSTER Iteration:
    for (unsigned int iy = 0; iy < NY; iy++)      // Alle Felder wie vorher abklappern
      for (unsigned int ix = 0; ix < NX; ix++)
        CheckField (ix, iy);
  } else {  // SONST: nur die Umgebungen der VORHER geÀnderten Punkte anschauen (aus ChangePos)
    for (vector<Change>::iterator it=ChangePos.begin(); it!=ChangePos.end(); it++)
      for (int ix = it->p.x-1; ix <= it->p.x+1; ix++)
        for (int iy = it->p.y-1; iy <= it->p.y+1; iy++)
           CheckField(ix, iy);
  }

 // Jetzt die Änderungen ausfĂŒhren.
 // Bei einer VerĂ€nderung der Welt, dies (fĂŒr die nĂ€chste Iteration) in ChangePos merken

  ChangePos.clear();
  for (vector<Change>::iterator it=Task.begin(); it!=Task.end(); it++) {
    bool worldstatus = world[it->p.x][it->p.y];
    bool newvalue    = it->cmd == SET;
    if (worldstatus != newvalue) {              // WICHTIG: PrĂŒfe, ob etwas zu tun ist
                                                // (das Feld wurd evtl. schon verÀndert!)     
      world[it->p.x][it->p.y] = newvalue;       // Wenn ja: Àndere die Welt
      ChangePos.push_back(*it);                 // und merke, dass sich bei p was geÀndert hat...
    }
  }
}

Auch hier sind wieder die unverĂ€nderten Teile weggelassen. Die Listen wurden hier in <vector> Strukturen aus der stl-Lib abgespeichert, da man bei vectors mit geringem Aufwand hinten anfĂŒgen kann (push_back()). Das Programm ist nicht lĂ€nger als vorher, ist aber vieeel schneller, insbesondere, wenn in einer großen Welt wenig passiert!

Personal tools