Tipps und Tricks
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(); }
Sortieren mit Algorithmen der Standardbibliothek
Natürlich wurden sortieralgorithmen schon unzälige mlae implementiert und auch die Standardbibliothek bietet für alle möglichen Containertypen Sortier-, Akkumulations- und noch weitere Algorithmen an.Eine Liste findet ihr auf der cpp standard seite: www.cplusplus.com/reference unter den punkten algorithm und numeric.
Im Allgemeinen gilt es wenn möglich immer die fertigen Algorithmen der standardbibliothek zu benutzen. Man kann davon ausgehen dass diese besonders optimiert wurden und schneller laufen als man selbst das implementieren könnte. Eine Implementierung würde dann folgendermaßen aussehen:
// sort algorithm example #include <iostream> // std::cout #include <algorithm> // std::sort #include <vector> // std::vector // Hier wird eine eigene Vergleichs-Funktion definiert die dem Sortier-Algorithmus übergeben wird -> *. bool myfunction (int i,int j) { return (i < j); } int main () { int myints[] = {32,71,12,45,26,80,53,33}; std::vector< int> myvector (myints, myints+8); // 32 71 12 45 26 80 53 33 // using default comparison (operator <): std::sort (myvector.begin(), myvector.begin()+4); // (12 32 45 71)26 80 53 33 // * using function as comp std::sort (myvector.begin()+4, myvector.end(), myfunction); // 12 32 45 71(26 33 53 80) std::sort (myvector.begin(), myvector.end(); // (12 32 45 71 26 33 53 80) // print out content: std::cout << "myvector contains:"; for (std::vector< int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) std::cout << ' ' << *it; std::cout << '\n'; return 0; }
Output: myvector contains: 12 26 32 33 45 53 71 80
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 [http://en.wikipedia.org/wiki/ANSI_escape_code] 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.kann mit#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; }
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 http://graphics.stanford.edu/~seander/bithacks.html oder auf http://bits.stephan-brumme.com/countBits.html 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!! ist.
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 "http://bits.stephan-brumme.com/countBits.html" 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
