Mandelbrot-Menge optimieren

[MrMooed]

Hallo DP ich bin es mal wieder.


Ich bin vor ein Paar Tagen von meiner Informatiklehrerin auf das Apfelmännchen aufmerksam gemacht worden. Als ich es das erste mal gesehen habe, dachte ich einfach nur 'wow! so geil kann Mathe aussehen ?' Habe den relativ simplen Algorithmus auch umgesetzt und dargestellt.

Nun wollte ich das ganze noch etwas schneller rechnen lassen. Zunächst habe ich über Multithreading nachgedacht, aber dann wurde mir bewusst, dass ich damit nicht mein eigentliches Problem löse sondern nur auf die Prozesorkerne auslagere
Nun wollte ich hier mal nachfragen ob evtl. jemand Tipps hat was ich an meiner Berechnung schneller machen (bzw. optimieren) kann.

Delphi-Quellcode:

function Mandelbrot.rechne(X_Ko, Y_Ko, X, Y, A: double; i: Integer): Integer;
var
  nX, nY, nA: double;
begin
  if (i < 50) and (A < 2)
    then begin
           nX := (X*X) - (Y*Y) + X_Ko;
           nY := 2*X*Y + Y_Ko;
           nA := SQRT(nX*nX + nY*nY);
           result := rechne(X_Ko, Y_Ko, nX, nY, nA, i+1);
         end;
end;

Erklärung:
der Rückgabewert wird später zur Darstellung der Farben benutzt.
i ist die Anzahl der Iterationen. Je höher desto genauer das Bild.
(X_Ko | Y_Ko) sollen mit dem Punkt (X | Y) verglichen werden. (normalerweise ist dies der Ursprung (0 | 0)
A bzw. nA sind der Abstand zu (X | Y) - Satz des Pythagoras, wenn ich das nicht falsch verstanden habe

Aufruf:
Aufrufen tue ich die Funktion mit einer case .. of Anweisung.

Delphi-Quellcode:

case rechne(x, y, 0, 0, 0, 0) of
          0..10:  Bild.Canvas.Pixels[x,y] := clBlack;
          11..20: Bild.Canvas.Pixels[x,y] := clOlive;
          21..30: Bild.Canvas.Pixels[x,y] := clYellow;
          31..40: Bild.Canvas.Pixels[x,y] := clLime;
          41..50: Bild.Canvas.Pixels[x,y] := clGreen;
          else    Bild.Canvas.Pixels[x,y] := $000000;

Und bei einem hohen 'i' hat mein Rechner dann ein bisschen viel zu rechnen..

Danke im Voraus schonmal.

Was ist ein Apfelmännchen ?

[Valle]

Hallo,

dein Problem ist nicht die Berechnung der Menge, sondern die grafische Darstellung. Pixels ist sehr langsam. Du solltest dir hier etwas anderes suchen. Es könnte zum Beispiel helfen, ein TBitmap zu erstellen, dieses zu befüllen und erst anschließend darzustellen. (das nennt man Buffer) Außerdem gibt es eine wesentlich schnellere Alternative zu Pixels, die nennt sich Scanline. Mit Google und Co. wirst du dazu sicher einiges finden.

Wenn du dann noch die Berechnung optimieren willst, solltest du erstmal schauen, ob die iterative Variante des Algorithmus eventuell schneller ist.

Liebe Grüße,
Valentin

[MrMooed]

Zitat von Valle:

Hallo,

dein Problem ist nicht die Berechnung der Menge, sondern die grafische Darstellung. Pixels ist sehr langsam. Du solltest dir hier etwas anderes suchen. Es könnte zum Beispiel helfen, ein TBitmap zu erstellen, dieses zu befüllen und erst anschließend darzustellen.

Habe wohl vergessen zu erwähnen, dass 'Bild' eine TBitMap ist die anschließend auf die Form gemalt wird

Zitat von Valle:

Außerdem gibt es eine wesentlich schnellere Alternative zu Pixels, die nennt sich Scanline. Mit Google und Co. wirst du dazu sicher einiges finden.

Ok werde ich mir direkt mal ansehen

Zitat von Valle:

Wenn du dann noch die Berechnung optimieren willst, solltest du erstmal schauen, ob die iterative Variante des Algorithmus eventuell schneller ist.

Prinzipiell sollten Iterative und Rekursive Algorithmen doch gleichschnell sein oder ?
So etwas wird einem leider in der Schule nicht vermittelt und habe mir das "Wissen" selbst angeeignet, kann sein dass ich mich da total irre

[Valle]

Beim Aufruf einer Funktion müssen alle zu übergebenden Variablen auf den Stack geschoben werden. Das allein kostet schon Zeit. Die Frage sollte also sein, ob der iterative Overhead das ausgleichen kann. Es gibt hier aber sicher einige mit abgeschlossenem Informatikstudium, die dir das besser erklären können als ich. Des Weiteren hat man bei Rekursion das Problem, dass es eine maximale Rekursionstiefe hat, die die Menge an verschachtelten Aufrufen stark beschränkt.

Rekursive Lösungen sind meist viel lesbarer und "schöner" als ihre iterativen Pendanten.

Ob das in der Praxis bei deinem Beispiel wirklich viel Unterschied macht kann ich dir nicht sagen. Aber wenn es dich interessiert kannst du es natürlich herausfinden. Es gibt Möglichkeiten, die Zeit einer Berechnung zu messen. Das kannst du für beide Verfahren durchführen, wenn du magst. Theoretisch meinte selbst der Prof an der FH, an der ich ein Semester lang ein Frühstudium abgelegt habe, dass die rekursive Variante unschlagbar toll wäre. Praktisch hatte er aber öfter mal Unrecht.

[MrMooed]

Tatsache
Nach meinen Messungen beträgt die Mittlere Zeit um 20 mal das Selbe Bild zu rechnen:

Rekursiv: 423,55ms
Iterativ: 412,65ms

kleiner aber feiner Unterschied Werde das ganze nachher nochmal testen wenn ich auf ScanLine umgestellt habe.

[Neutral General]

Hi,

Scanline wird dir einen großen Geschwindigkeitsschub geben.
Mit Multithreading lässt sich das auch beschleunigen.
Du teilst das bild einfach unter den Kernen auf und jeder Kern berechnet einen Teil des Bildes.
Im Hauptthread fügst du die Teile zusammen und zeichnest (Das Zeichnen ist normalerweise leider nicht threadsafe)

[Delphi-Laie]

Zitat von MrMooed:

Nun wollte ich hier mal nachfragen ob evtl. jemand Tipps hat was ich an meiner Berechnung schneller machen (bzw. optimieren) kann.

Wollte? Willst du es jetzt nicht mehr?

Tue es doch einfach!

Ehe du es tust, um es abzukürzen: Ein gewaltiges Beschleunigungspotential ergibt sich dadurch, daß man (mehr oder weniger) kleine (rechteckige, am besten quadratische) Flächen gleich komplett färbt: Sind ihre 4 Eckpunkte, die man als erstes berechnet, gleichfarbig, so ist es mit großer Wahrscheinlichkeit das gesamte von ihnenn eingehüllte Viereck. Um Irrtümer anzahlig zu reduzieren, kann man ja auch rekursiv vorgehen und in größeren Vierecken kleinere auf gleiche Weise prüfen und ggf. füllen. Dagegen sind Scanline und Threads läppisch, obwohl beide natürlich auch ihre Berechtigung und Vorteile haben.

[Namenloser]

Zitat von Delphi-Laie:

Ehe du es tust, um es abzukürzen: Ein gewaltiges Beschleunigungspotential ergibt sich dadurch, daß man (mehr oder weniger) kleine (rechteckige, am besten quadratische) Flächen gleich komplett färbt: Sind ihre 4 Eckpunkte, die man als erstes berechnet, gleichfarbig, so ist es mit großer Wahrscheinlichkeit das gesamte von ihnenn eingehüllte Viereck. Um Irrtümer anzahlig zu reduzieren, kann man ja auch rekursiv vorgehen und in größeren Vierecken kleinere auf gleiche Weise prüfen und ggf. füllen.

Und was genau sollte daran schneller sein? Bei einem Fraktal muss sowieso der Wert für jeden Pixel einzeln berechnet werden, und die Anzahl der zu füllenden Pixel wird so auch nicht reduziert.

[Delphi-Laie]

Zitat von NamenLozer:

Und was genau sollte daran schneller sein?

Die oft fehlenden Iterationen.

Zitat von NamenLozer:

Bei einem Fraktal muss sowieso der Wert für jeden Pixel einzeln berechnet werden,

"Muss" muß gar nicht. Es gibt in vielen Flächenfraktalen, so auch dem Apfelmännchen, viele (ziemlich) einfarbige Gebiete, bei denen man mit hoher Treffsicherheit eben annehmen (neupseudodeutsch "davon ausgehen") kann, daß 4 gleichfarbige Eckpunkte ein komplett gleichfarbiges Gebiet umschließen.

Fällt nun der Groschen?

Ausgedacht habe ich mir das nicht, sondern schon vor ca. 20 Jahren (!) in einem DOS-Fraktalprgramm wahrgenommen.

Zitat von NamenLozer:

und die Anzahl der zu füllenden Pixel wird so auch nicht reduziert.

Wer behauptet denn anderes?

[Namenloser]

Ich kann mir nur schwer vorstellen, dass dabei keine Artefakte auftreten...