AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Mandelbrot-Menge optimieren

Ein Thema von MrMooed · begonnen am 30. Sep 2012 · letzter Beitrag vom 1. Okt 2012
Antwort Antwort
Seite 1 von 3  1 23   
Benutzerbild von MrMooed
MrMooed

Registriert seit: 18. Feb 2012
101 Beiträge
 
Delphi 7 Enterprise
 
#1

Mandelbrot-Menge optimieren

  Alt 30. Sep 2012, 12:29
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 ?
  Mit Zitat antworten Zitat
Benutzerbild von Valle
Valle

Registriert seit: 26. Dez 2005
Ort: Karlsruhe
1.223 Beiträge
 
#2

AW: Mandelbrot-Menge optimieren

  Alt 30. Sep 2012, 13:09
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
Valentin Voigt
BOFH excuse #423: „It's not RFC-822 compliant.“
Mein total langweiliger Blog
  Mit Zitat antworten Zitat
Benutzerbild von MrMooed
MrMooed

Registriert seit: 18. Feb 2012
101 Beiträge
 
Delphi 7 Enterprise
 
#3

AW: Mandelbrot-Menge optimieren

  Alt 30. Sep 2012, 13:21
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

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

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
  Mit Zitat antworten Zitat
Benutzerbild von Valle
Valle

Registriert seit: 26. Dez 2005
Ort: Karlsruhe
1.223 Beiträge
 
#4

AW: Mandelbrot-Menge optimieren

  Alt 30. Sep 2012, 13:30
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.
Valentin Voigt
BOFH excuse #423: „It's not RFC-822 compliant.“
Mein total langweiliger Blog
  Mit Zitat antworten Zitat
Benutzerbild von MrMooed
MrMooed

Registriert seit: 18. Feb 2012
101 Beiträge
 
Delphi 7 Enterprise
 
#5

AW: Mandelbrot-Menge optimieren

  Alt 30. Sep 2012, 13:59
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.
  Mit Zitat antworten Zitat
Benutzerbild von Neutral General
Neutral General

Registriert seit: 16. Jan 2004
Ort: Bendorf
5.219 Beiträge
 
Delphi 10.2 Tokyo Professional
 
#6

AW: Mandelbrot-Menge optimieren

  Alt 30. Sep 2012, 15:29
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)
Michael
"Programmers talk about software development on weekends, vacations, and over meals not because they lack imagination,
but because their imagination reveals worlds that others cannot see."
  Mit Zitat antworten Zitat
Benutzerbild von MrMooed
MrMooed

Registriert seit: 18. Feb 2012
101 Beiträge
 
Delphi 7 Enterprise
 
#7

AW: Mandelbrot-Menge optimieren

  Alt 30. Sep 2012, 16:04
Eigentlich wollte ich Multithreading erst am Schluss machen, da ich sonst schlechten Code mit Hardware kompensiere

Nun gut .. ich würde es dann so machen, dass jeder Thread einen Streifen des Bildes rechnen muss. Also 'Fensterbreite / CPUKerne' dann muss ich ihm noch den ganzen Algorithmus und die Zeichenfunktion in den Thread packen oder ?
Somit muss dem Thread dann noch übergeben werden von welchem xMin - xMax er rechnen soll.
Aber auf meine Form kann der Thread nicht selber zeichnen - eine TBitMap als Rückgabe

Hatte vor langer Zeit mal einen Link zum multithreading gefunden, vllt kennt jemand etwas noch verständlicheres ?
Multithreading
  Mit Zitat antworten Zitat
Benutzerbild von Valle
Valle

Registriert seit: 26. Dez 2005
Ort: Karlsruhe
1.223 Beiträge
 
#8

AW: Mandelbrot-Menge optimieren

  Alt 30. Sep 2012, 16:11
Eigentlich wollte ich Multithreading erst am Schluss machen, da ich sonst schlechten Code mit Hardware kompensiere
Richtig so!

Vielleicht machst du es auch gleich in zwei Schritten. Erst die Threads alle Werte berechnen lassen und in einem Array zwischenspeichern. Und dann den Main-Thread alles zeichnen lassen. Letzteres lässt sich ja via Multithreading vermutlich sowieso nicht beschleunigen. Höchstens noch via OpenGL, aber das ist ... weit gegriffen.
Valentin Voigt
BOFH excuse #423: „It's not RFC-822 compliant.“
Mein total langweiliger Blog
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#9

AW: Mandelbrot-Menge optimieren

  Alt 30. Sep 2012, 16:24
Ich habe mal Mandelbrot programmiert, auch mit Multithreading. Ich habe einfach ein Bitmap genommen und dann jeden Thread jeweils die n-te, n+1-te, n+2-te usw. Scanline berechnen lassen. Also z.B. bei 4 Threads wäre der 1. Thread zuständig für die 0, 4, 8, ... Scanline, der 2. Thread für die 1, 5, 9, ..., der 3. für die 2, 6, 10, ..., und der 4. für die 3, 7, 11, ...

Das ist leicht zu implementieren und hat den Vorteil, dass die Threads alle in etwa gleich viel Arbeit verrichten müssen (wenn man das ganze Bild nur in 4 große Teile aufteilen würde, könnte es sein, dass auf 3 Teilen fast nichts zu berechnen ist und dann doch wieder nur ein Thread die ganze Arbeit macht).

Man sollte das Bild übrigens auf jeden Fall in Zeilen aufteilen, nicht in Spalten wie in #7 impliziert, da das Bild zeilenweise im Speicher liegt, d.h. man spart dadurch eine Menge TBitmap.Scanline-Aufrufe und außerdem reduziert man Cache-Misses.

Geändert von Namenloser (30. Sep 2012 um 16:26 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von sx2008
sx2008

Registriert seit: 16. Feb 2008
Ort: Baden-Württemberg
2.332 Beiträge
 
Delphi 2007 Professional
 
#10

AW: Mandelbrot-Menge optimieren

  Alt 30. Sep 2012, 16:35
Das Wurzelziehen mit SQRT() sollte man bei der Mandelbrotmenge unbedingt vermeiden, denn es kostet viel Zeit.
In der rekursiven Variante wird ja auf (A < 2) abgefragt.
Lässt man das Wurzelziehen weg, dann muss auch die Konstante quadriert werden (2*2=4):
Delphi-Quellcode:
if (nX*nX + nY*nY) >= 4.0 then
  exit;
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 3  1 23   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 22:05 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz