Laufzeitoptimierung, MandelbrodtJuliaZoom

[Dipl Phys Ernst Winter]

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.

[Dipl Phys Ernst Winter]

"Stoxx"

Zitat:

Ich kenn mich ja zu wenig damit aus, aber würden sich damit auch Zeitreihenprognosen erstellen lassen, denen man chaotisches Verhalten unterstellen möchte?

Nein. Das ist Thema der Quadratischen Iterators

[himitsu]

Joar, das hab ich mich auch schon immer mal wieder gefragt ... also wozu man sowas eigentlich verwenden kann.

Außer daß man in die Corona "unendlich" reinzoomen kann und sich da ein Muster ewig in sich wiederholt und daß es sich schwer berechnen läßt ist doch für nix verwendbar, oder?
OK, außer um Laufzeitoptimierungen auszuprobieren

[Dipl Phys Ernst Winter]

[quote="isilive"]

Zitat:

Warum Backspace oder Delete in einem Edit problematisch sein sollten verstehe ich auch nicht. Es ist wichtig um eine normale Bedienbarkeit des Programms zu erhalten. Eventuelle Falscheingaben sollten sich problemlos abfangen lassen.

Ausserdem wenn ich 1.05 eingebe kommt eine Fehlermeldung "Ungültiger Wert". Bis ich 1.050000000000 eingebe.

Du gibst die Antwort selbst.

Die Parameter werden angezeigt und können zur Editiom mit anderen Ziffern überschrieben werden, demit der Inhalt des Feldes Konvertierbar bleibt fordert die Maske eine Ziffer an allen Positionen.
Mit '1.0500 000000' würde das Program sich mit einer Fehlermeldung 'Konvertierungsfehler' beim StrToFloat() verabschieden.

Was ist unter normaler Bedienbarkeit zu verstehen? Ich halte die Edition einer im Feld stehenden Zahl durch Überschreiben durchaus für normal, auch ohne Delete und Backspace.

[Dipl Phys Ernst Winter]

"Daniel G"

Zitat:

Delete und Backspace sind bewußt unterdrückt, da sie zu einem nicht konvertierbaren String führen würden
Inwiefern?

StrToFloat('1.050 00000') würde einen Konvertierungsfehler erzeugen, daher fordert die Maske eine Ziffer an allen Stellen. Damit der Anwenden nicht mit der Fehlemeldung 'Ungültiger Wert' konfrontiert wird (für ihn nicht nachvollziehbar, da er die Maske nicht kennt) wurden Delete und Backspace unterdrückt.

Zitat:

Es wurde doch 'Weiter mit OldBild' empfohlen

OldBild findet sich im Menü Bild

[Dipl Phys Ernst Winter]

"himitsu" fragt

Zitat:

Joar, das hab ich mich auch schon immer mal wieder gefragt ... also wozu man sowas eigentlich verwenden kann.

Da musst Du mal bei den Mathematikern nachfragen. z.B. Mandelbrodt: Die Fraktale Geometrie der Natur.
Speziell mit realen Anwendungen in Biologie, Ökologie, Geologie befassen sich
H.M. Hastings/G. Sugihara in Fraktale Ein Leitfaden für Anwender Spektrum Academischer Verlag 1996.

[guidok]

Zitat von Dipl Phys Ernst Winter:

Was ist unter normaler Bedienbarkeit zu verstehen? Ich halte die Edition einer im Feld stehenden Zahl durch Überschreiben durchaus für normal, auch ohne Delete und Backspace.

Das stimmt, das Überschreiben ist durchaus normal, allerdings auch das Backspace und Delete. Also im Regelfall ist es so:

Ich klicke in eine Editierfeld und der gesamte Inhalt wird zum Überschreiben markiert. Ich klicke noch einmal, dann wird wieder deselektiert und ich befinde mich im Einfügemodus. Oder ich markiere jetzt gezielt ein oder mehrere Zeichen und kann wieder überschreiben. Oder ich verwende Pos1 oder Backspace oder Delete.

Nachdem ich "früher" auch gerne zu kreativen Methoden der Bearbeitung und der GUI gegriffen habe, bin ich nun doch der Meinung das man sich (auch wenn man Microsoft nicht mag) an das allgemeine "Look and Feel" halten sollte.

Das bedeutet allerdings nicht, dass man nicht für spezielle Aufgaben auch spezielle Eingabemethoden einsetzen darf.

[himitsu]

Im Notfall kann man Backspace und Delete auch ganz einfach in Maskedits implementieren
und (führende/folgende) Leerstellen würde ich einfach als 0 behandeln, oder vor der Umwandlung wegschneiden (Trim).

[Medium]

Was die Eingabe betrifft: Es hat sich als Quasi-Standard etabliert die Eingabe ungültiger Zeichen in entsprechende Edits abzufangen. Ein Leerzeichendruck fällt bei Zahleneingaben ebenso darunter wie Buchstaben, Steuertasten hingegen nicht. Die Prüfung muss Eingaben die "im Werdegang" sind berücksichtigen, z.B. kann ein '-.', dass ja an sich ungültig ist durchaus noch ein '-9.5' werden.
Daher: Sollte es ein User dann dennoch schaffen einen nicht konvertierbaren Wert einzugeben, so sollte man dies abprüfen, und dem Benutzer eine aussagekräftige Fehelrmeldung in Form eines MessageDialogs präsentieren, der aussagt was wo falsch ist. Das wäre der übliche Weg.

Vormaskierte Eingaben mit invarianter Stellenanzahl sind nicht mehr üblich, und muten jedem "normalen" Windows User sehr fremd an. In einigen wenigen sehr zpeziellen Fällen kann das natürlich vermutlich sinnvoll eingesetzt werden, wenn es den "Bedienflow" erhöht, jedoch habe ich gerade nicht einmal ein treffendes Beispiel parat. Im vorliegenden Fall empfinde ich es als eher hinderlich.

Was die "Hilfe lesen" Sache angeht:
Man muss davon ausgehen, dass rund 99% aller PC User eine Hilfe wenn überhaupt bei speziellen Problemen anschaut. Wenn ich schon zum Verständnis der reinen Bedienung mit den ansonsten duraus standardmäßig aussehenden Controls eine Hilfe konsultieren muss, dann liegt das Problem nicht bei mir als User. Dann ist die GUI nämlich nach ergonomischen Gesichtspunkten ein Fehlschlag. Nicht umsonst beschäftigen größere Unternehmen ganze Abteilungen damit die Bedienbarkeit zu verbessern, und bei diesem kleinen Programm wäre es doch ein Leichtes eine sehr intuitive Bedienung zu schaffen, die auf dem Standardverhalten der Standardcontrols basiert.

[guidok]

Zitat von himitsu:

Im Notfall kann man Backspace und Delete auch ganz einfach in Maskedits implementieren
und (führende/folgende) Leerstellen würde ich einfach als 0 behandeln, oder vor der Umwandlung wegschneiden (Trim).

oder direkt bei der Eingabe prüfen, ob das eingegebene Zeichen zu einer gültigen Zahl führt

Delphi-Quellcode:

procedure TForm1.Edit1KeyPress(Sender: TObject; var Key: Char);
var DummyOut: Single;
begin
  if not TryStrToFloat(Edit1.Text + Key, DummyOut) then begin
    Key := #0;
  end;
end;

[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