AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Projekte Delphi Laufzeitoptimierung, MandelbrodtJuliaZoom

Laufzeitoptimierung, MandelbrodtJuliaZoom

Ein Thema von Dipl Phys Ernst Winter · begonnen am 2. Mai 2009 · letzter Beitrag vom 9. Mai 2009
Antwort Antwort
Seite 3 von 3     123
Dipl Phys Ernst Winter
Registriert seit: 14. Apr 2009
Laufzeiteffektivität
Zeitkritisch wird ein Programm genannt, bei dem der Anwender darauf warten muß, daß das Programm seine Arbeit erledigt hat.
Es wird immer Probleme geben, für die der Computer zu langsam ist. Das sind numerisch komplexe Probleme, wie die des Handlungsreisenden, Probleme der pixelweisen Bildbearbeitung, wie die Erzeugung von Fraktalen, und Echtzeit-Probleme, die eine Lösung in kürzester Zeit erfordern, wie die Animation in einem Spiel.
Laufzeitoptimierung
Für zeitkrische Programme kommt der Laufzeitoptimierung hohe Priorität zu. Zur Zeit der 8-Bit Heimcomputer waren hier Assembleroutinen nahezu obligatorisch, aber wer kann heute noch einen Pentium in Assembler programmieren.
Ein konkretes Beispiel: MandelbrodtJulia Zoom
Die Zeit für die pixelweise Erzeugung eines Bildes der Mandelbrodt-Menge dauerte auf Grund des immensen Rechenaufwandes auf einem PC ohne Koprozessor Stunden. Auch mit Koprozessor ist die Erzeugung eines Mandelbrodt- bzw. Juliabildes ein Musterbeispiel für Laufzeitoptimierung geblieben. A. Schäpers widmet dem Thema in dem Buch Turbo PASCAL 6 Addinson-Wessley, 1991 einen eigenen Abschnitt.
Er beginnt mit der wichtigen Aussage, Zitat:
Bei jeder Optimierung sind die Eigenheiten des Problems zu berücksichtigen, bevor man beginnt das letzte aus dem Code herauszuholen.
um sich dann konsequent nicht daran zu halten.
1. Zunächst wird die einfachste Eigenschaft der Mandelbrodt-Menge ignoriert:
Die Mandelbrodt-Menge ist spiegelsymmetrisch zur reellen Achse Im=0
Das erfordert zur Wahrung der Richtigkeit, dass die reelle Achse mit einer Pixelzeile zusammenfällt. Da er nicht dafür sorgt, wird sein Programm Bilder erzeugen können, die nicht streng symmetrisch sind.
Die Symmetrie kann zur Verbesserung der Laufzeiteffektivität ausgenutzt werden: Bezeichnet man die Pixelzeile der reellen Achse mit y0, so braucht man (sofern y0 im Bildfenster liegt), nur die Punkte y≥y0 bzw. y≤y0zu iterieren und kann diese in den symmetrischen Bildteil kopieren. Beim Übersichtsbild spart man so die Hälfte der Iterationen.
Analog gilt für Julia-Mengen
Julia-Mengen sind zentral¬symmetrisch zum Koordinatenursprung.
Zur Wahrung der Richtigkeit, muss der Koordinatenurprung mit einem Pixel zusammenfallen. Auch hier braucht man kann zur Verbesserung der Laufzeiteffektivität nur Punkte mit y≥y0 bzw. y≤y0 zu iterieren und kann sie in den gegenüber liegenden Quadranten kopieren. Beim Übersichtsbild spart man so die Hälfte der Iterationen.
2. A. Schäpers beginnt die programmbezogene Optimierung mit dem inzwischen allgemeinen Wissen
Das Innere von Kopfkreis und Rumpfzykloide gehören zur Mandelbrodt-Menge.
Er folgt dann Werner Duranti, der in der Ausgabe 3/87 der Zeitschrift c’t zeigt, wie man die Iteration ihrer Punkte übergeht, indem man bei jedem Bildpixel zunächst testet, ob es einem Punkt in Kopfkreis oder Rumpfzykloide entspricht.
Dabei ist er jedoch vom Pferd auf den Esel gekommen! Die Rechenzeit für die Gesamtansicht geht infolge der eingesparten Iterationen trotz Testaufwand zwar auf ein Fünftel zurück, aber bei einem ganz außerhalb von Kopf und Rumpf liegendem Ausschnitt wird die Zeit zum Testen jedes Punktes unnütz hinterher geworfen.
Die Gesamtansicht ist jedoch keineswegs ‘Standardausschnitt’ im Sinne von häufig zu berechnen, sondern ein selten verwendeter Sonderfall. Standard sind Ausschnitte am Rande der Mandelbrodt-Menge, die oft keine inneren Punkte von Kopf und Rumpf enthalten.
Versuchen wir diese Optimierung zu retten: Nach einem einfachem Test, ob die Zeile den Kopf bzw. Körper überhaupt schneidet, sind die Schnittpunkte der Zeile mit Kopf und Körper zu bestimmen und die Iteration auf die äußeren Punkte zu beschränken. Das scheitert daran, dass sich Schnittpunkte der Zeile mit der Zykloide nicht berechnen lassen.
Aus den Formeln von W. Duranti erkennen wir jedoch, dass sich der Punkt der Zykloide für gegebenes x berechnen lässt. Wir organisieren den Bildaufbau daher spaltenweise, womit sich alles stark vereinfacht:
Ein einfacher Test ergibt, ob die Spalte Kopf bzw. Rumpf schneidet. Gegebenenfalls wird der Schnittpunkt der Spalte mit Kopfkreis oder Zykloide berechnet und die Iteration der Punkte bei diesem Wert begonnen. Der Zwickel unter dem Rumpf im Bereich Re = 0.25..0.38 ist gesondert zu behandeln.
Hinweis: Diese Optimierungen sind bei sehr starken Vergrößerungen, wenn der Wert für y0 den Wertebereich der Integerzahlen überschreitet, nicht mehr durchführbar. Das Bild wird dann über den ganzen Bildschirm zeilenweise aufgebaut.
3. Optimierung des Codes.
• Bei den Routinen zur Iteration helfen nur in Assembler geschriebene laufzeitoptimalen Prozeduren unter Verwendung des Arithmetikprozessors weiter. Die Funktionen ItMdl und ItJul (nach A. Schäpers) verlegen die gesamte Iteration in die Register des Koprozessors. Sie sind extrem schnell, da jeglicher Speicherzugriff während der Iteration vermieden wird.
• Das Setzen der Farbe eines Pixels mit der Canvas-Property Pixels wäre extrem langweilig und dem Programm nicht angepaßt, da die Farbe als Color und nicht als Farbindex übergeben wird.
Die Farbindices für die Bildpixel als Ergebnisse der Iteration werden daher in einem Byte-Array auf dem Heap gespeichert. Das ermöglicht eine optimal einfache Adressierung bei wahlfreier Folge, die infolge der Optimierung mit gespiegelten Punkte notwendig ist.
Zur Anzeige wird eine Bitmap mit 256 Farben verwendet, in der die Farbindices mit 1Byte/Pixel gespeichert sind. Das fertige Byte-Array kann blitzschnell über ein TFileStream Objekt in diese Bitmap-File kopiert werden.
Angehängte Dateien
Dateityp: exe mandelbrodtjuliazoom_131.exe (464,0 KB, 94x aufgerufen)
Autor: DP Ernst Winter
 
Benutzerbild von Mithrandir
Mithrandir
 
#21
  Alt 5. Mai 2009, 11:05
Zitat von Dipl Phys Ernst Winter:
Zitat:
Es wurde doch 'Weiter mit OldBild' empfohlen
OldBild findet sich im Menü Bild
Das Menü ist doch aber ausgegraut. Warum vollziehen Sie den Fehler nicht einfach nach, dann sehen Sie das doch selbst? Er ist definitiv reproduzierbar.
米斯蘭迪爾
  Mit Zitat antworten Zitat
guidok
 
#22
  Alt 5. Mai 2009, 11:09
Zitat von himitsu:
direkt bei der Eingabe ist blöd

will ich "-1" eingeben, dann ist das "-" alleine keine gültige Zahl,
also erst im OnExit des Edits oder vor Verwendung der Zahl
Naja, das einzelne "-" würde sich auch bei der direkten Eingabeprüfung noch prüfen lassen. Gültig wäre dann entweder ein einzelnes Minus oder eine gültige Zahl...
  Mit Zitat antworten Zitat
generic

 
Delphi XE5 Professional
 
#23
  Alt 5. Mai 2009, 11:12
Kennt ihr FractInt ?
http://www.nahee.com/spanky/www/fractint/fractint.html

Das war von der Bedienung brauchbar.
  Mit Zitat antworten Zitat
Benutzerbild von stoxx
stoxx
 
#24
  Alt 5. Mai 2009, 11:57
Zitat von Dipl Phys Ernst Winter:
Nein. Das ist Thema der Quadratischen Iterators
was ist ein Quadratischer Iterator? Kennst Du Dich damit näher aus?
  Mit Zitat antworten Zitat
Dipl Phys Ernst Winter

 
Delphi 3 Professional
 
#25
  Alt 6. Mai 2009, 10:05
"Daniel G"
Zitat:
Ich hab mal das Bild der hängenden Anwendung angehängt. Die Meldung 'Weiter mit OldBild' ist für mich in diesem Falle nicht wirklich aussagekräftig...
Da hast Du recht!
Die Abschaltung der Menüs Ausschnitt, Bild und Drucken wurde irgendwann hinzugefügt ohne zu Beachten, dass sie beim Abbruch der Bilderzeugung noch gebraucht werden.

Ich habe den Abbruch der Bilderzeugung nochmals Bearbeitet, er führt jetzt ohne Mitwirkung des Anwenders zum OldBild.
Anbei der neue Code.
Herzlichen Dank!
Angehängte Dateien
Dateityp: exe mandelbrodtjuliazoom_192.exe (266,9 KB, 19x aufgerufen)
  Mit Zitat antworten Zitat
Dipl Phys Ernst Winter

 
Delphi 3 Professional
 
#26
  Alt 9. Mai 2009, 19:59
"himitsu" hat geschrieben
Zitat:
(führende/folgende) Leerstellen würde ich einfach als 0 behandeln, oder vor der Umwandlung wegschneiden (Trim).
Es geht aber um die in der Zahl entstehenden Leerstellen. Gewiss kann man die auch entfernen, aber den Aufwand wollte ich mir ersparen bei einem Feld, das ohnehin nur selten und an wenigen Stellen editiert wird.
  Mit Zitat antworten Zitat
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 01:28 Uhr.
Powered by vBulletin® Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf