Kleine Optimierungen unter Freunden, Teil II

Das ehemalige Nachrichtenmagazin, um einmal Fefe zu zitieren, hatte dieses Wochenende eine kleine Knobelaufgabe der Art „Was folgt als nächstes?“ im Programm.

Conway Aufgabe

Das Rätsels Lösung versteckte sich in einer Conway-Folge: Die jeweils nachfolgende Reihe beschreibt, wie oft die nachfolgende Ziffer in der vorigen Zeile an der jeweiligen Stelle vorhanden ist, also, von der 2. Zeile an: 1*1, 2*1, 1*2+1*1, 1*1+1*2+2*1 usw.

Prima Vorgabe für eine kleine Programmier-Fingerübung, und darüberhinaus eine gute Vorlage, um sich einmal wieder der Optimierung zu widmen. Also dann: Xojo angeworfen und mitgetippt!

Das alles wird bei mir wieder ein Desktop-Projekt mit recht überschaubarem Inventar: Eine Listbox, ein Progressbar und ein Button – so wie hier abgebildet:

ConwayWindow

Die Progressbar setze ich auf unsichtbar, weil ich’s hübscher finde, wenn sie nur während der Bearbeitung sichtbar ist. Außerdem ziehe ich noch einen Thread und einen Timer in das Layout, dessen Klasse ich aus purer Vorliebe auf Xojo.Core.Timer setze.

Ausnahmsweise verzichte ich ansonsten auf die Benutzung des Xojo-Frameworks, da es hier (das merken Sie schon bald) auf Geschwindigkeit ankommt und ich mir die Konvertierungen von und zu Text und Konsorten sparen möchte. Das Fenster bekommt noch drei Properties:

  • Conway As String mit dem Vorgabewert „1“
  • Pos As Integer
  • StopConway As Boolean

Der String Conway wird entsprechend später die Ziffernkolonne aufnehmen, immer Zeile für Zeile. Die erste, „1“, steht als Vorgabewert schon drin. Pos ist der Positionszeiger innerhalb der gerade in Arbeit befindlichen Conway-Zeile, und StopConway wird benötigt, um die Berechnung zu stoppen. Das ganze soll in einem Thread berechnet werden, weil sich sonst alles in einer zu engen Programmschleife drehen würde, die eine Aktualisierung der Listbox und ein zeitnahes Reagieren auf Benutzeraktionen unmöglich machen würde.

Das ist schon das ganze Layout. Nun also

auf zum Code:

Der Button hat, wie im Bild sichtbar, die Caption „Start“ erhalten. Sein Action-Eventhandler wird der folgende:

Sub Action() Handles Action
 If Me.Caption = "Start" Then
  ProgressBar1.Visible = True
  Listbox1.DeleteAllRows
  StopConway = False
  Me.Caption = "Stop"
  Conway = "1"
  timer1.mode = xojo.core.timer.Modes.Multiple
  doConway
 Else
  stopConway = True
  timer1.mode = xojo.core.timer.Modes.off
  Me.Caption = "Start"
  ProgressBar1.Visible = false
 End If
End Sub

Da muss ich nicht viel zu erklären, oder? Beim ersten Klick ändert sich die Beschriftung des Buttons auf „Stop“, die Listbox wird gelöscht, der Timer angeworfen und dann vor allem die Methode doConway aufgerufen, die bald folgt. Bei Stop-Klick geht alles den umgekehrten Weg.

Dann der Timer: Dessen Properties setze ich in der IDE auf Mode.Off und wähle einen halbwegs plausiblen Period-Wert für die Aktualisierung des Progressbars – dafür ist der Timer gedacht. Also irgendwas zwischen 100 und 500, um zehn- oder auch nur zweimal pro Sekunde tätig zu werden. Geschmackssache!

Der Action-Eventhandler des Timers wird sehr übersichtlich:

Sub Action() Handles Action
 Progressbar1.value = pos
End Sub

Bevor es an die eigentliche Arbeit geht, erhält das Fenster noch die erwähnte Methode:

Public Sub doConway()
 Listbox1.AddRow(left(conway, min(512, conway.len)))
 ProgressBar1.value = 0
 ProgressBar1.Maximum = conway.len
 pos = 1
 if not StopConway then thread1.Run
End Sub

Auch nicht viele Besonderheiten: Zunächst wird der String Conway in die Listbox ausgegeben. Da er irgendwann sehr groß werden kann (gar nicht mal so irgendwann; das geht recht schnell) und die Listbox das dann nicht mehr mitmacht, begrenze ich die Ausgabe auf die ersten 512 Zeichen oder die Länge von Conway, was immer kleiner ist. Wer gerne alles in voller Schönheit sieht, kann die Ausgabe z.B. gerne noch in eine Datei umlenken.

Der Maximalwert der Progressbar wird auf die Länge von Conway gesetzt. Somit spare ich mir Prozentumrechnungen oder ähnliches, und das erklärt dann auch die Kürze des Timer-Events.

Nach Rücksetzen von Pos auf 0 dann endlich die eigentliche Action: Der Thread wird gestartet. Und dieser sieht so aus – zunächst –:

Sub Run() Handles Run
 Dim result, part, part2 As string
  Do
   part = Mid(conway, pos, 1)
   Do
    If pos < conway.Len Then
     part2 = Mid(conway, pos+1, 1)
     If part2 = Left(part, 1) Then
      part = part + part2
      pos = pos + 1
     End If
    End If
   Loop Until pos = conway.len Or part2 <> Left(part, 1)
  result = result + part.Len.ToText+Right(part, 1)
  pos = pos + 1
 Loop Until pos > conway.len
 conway = result
 xojo.core.timer.CallLater 0, AddressOf doconway
End Sub

Dazu jetzt ein paar Worte mehr:

Zunächst wird der Variable part das erste Zeichen von Conway gegeben. (Nebenbei: Das ist einer der Gründe, warum ich das Xojo-Framework bevorzuge: Mid(String) fängt in der Zählung bei 1 an. Damit verhaspele ich mich jedesmal. Im Xojo-Framework gilt immer die 0 als erster Index, ganz egal, mit welchen Datentypen man hantiert.)

Sind wir damit noch nicht am Ende von Conway angelangt, gelangt das nächste Zeichen in die Variante part2. Ist dieses identisch mit dem ersten, wird es an part herangehängt und das Spiel wiederholt sich; entweder, bis wir am Ende der Zeichenkette sind, oder bis wir eine andere Ziffer haben.

result ist der Zwischenspeicher fürs Endergebnis. Und dieses wird für jeden Durchlauf durch die erste DoLoop-Schleife aus der Länge von part und dessen letzten Zeichen gebildet – so, wie es die Conway-Reihe vorgibt.

Dann geht es weiter mit dem nächsten Zeichen, ggf. wiederholt, bis wir die ganze Zeichenkette abgearbeitet haben. Zum Schluss wird das Ergebnis an Conway übergeben und über den Xojo.Core.Timer.Calllater-Aufruf wiederum doConway gestartet – auf geht’s in die nächste Runde!

Nachvollziehbar? Prima! Dann lassen Sie das Ganze mal laufen!

Nicht nachvollziehbar? Schade! Aber für den Fall gibt es conway0 zum Download.

Ist alles richtig, sollte sich jetzt eine Liste sehr ähnlich der ersten Abbildung aufbauen – bzw. auch deren Fortführung.

Nach der ersten Freude kommt aber vermutlich bald die Ernüchterung. Das Programm fängt recht flink an, aber schon nach ein paar Zeilen wird es deutlich langsamer. Das kann doch nicht alles sein, oder? An der schnell anwachsenden Zeilenlänge ist zu sehen, dass der Conway-String exponentiell größer wird. Aber trotz alledem: Vom Hocker haut einen die Performance nicht.

Flaschenhalssuche

Strings – und auch Text – sind zwar sehr praktische Datentypen, aber das Verknüpfen mehrerer ist sehr zeitaufwendig. Für einen Befehl der Art String1 = String1 + String2 wird neuer Speicher in der Größe beider Strings reserviert und deren Inhalt dorthin kopiert. Eliminieren wir mal einen Teil, der, da in einer Schleife steckend, sehr häufig aufgerufen wird:

Sub Run() Handles Run
 Dim result, part, part2 As String
 Dim PartLen as Integer
 Do
  PartLen = 1
  part = Mid(conway, pos, 1)
  Do
   If pos < conway.Len Then
    part2 = Mid(conway, pos+1, 1)
    If part2 = part Then
     partlen = partlen + 1
     pos = pos + 1
    End If
   End If
  Loop Until pos = conway.Len Or part2 <> part
  result = result + partLen.ToText + part
  pos = pos + 1
 Loop Until pos > conway.Len
 conway = result
 xojo.core.timer.CallLater 0, AddressOf doconway
End Sub

(Für Tippfaule: conway1). Für alle anderen die geänderten Zeilen in Fettdruck.

Statt part bei Gleichheit mit part2 zu verlängern, wird also einfach nur ein Zähler erhöht. Das bringt … so gut wie gar nichts. Vielleicht etwas mehr Geschwindigkeit am Anfang, aber es wird ja nach wie vor result zusammengeschraubt, und dieser String wird schnell riesig groß – also auch viel Hin- und Herkopiererei.

Wenn Sie aufmerksamer Leser dieses Blogs sind, wissen Sie, dass die Join-Funktion, ob nun für Strings oder Texte, ein Zusammenfügen eines Arrays sehr viel schneller erledigt als das wiederholte Zusammenfügen der Einzeldatentypen. Versuchen wir das mal:

Sub Run() Handles Run
 Dim result(), part, part2 As String
 Dim PartLen as Integer
 Do
  PartLen = 1
  part = Mid(conway, pos, 1)
  Do
   If pos < conway.Len Then
    part2 = Mid(conway, pos+1, 1)
    If part2 = part Then
     partlen = partlen + 1
     pos = pos + 1
    End If
   End If
  Loop Until pos = conway.Len Or part2 <> part
  result.append partLen.ToText+part
  pos = pos + 1
 Loop Until pos > conway.Len
 conway = join(result, "")
 xojo.core.timer.CallLater 0, AddressOf doconway
End Sub

(Sie ahnen es schon: conway2)

Und? Auch nicht wirklich der Brüller, oder? Aber warum?

Lassen Sie das Programm mal eine Minute oder so laufen und beobachten Sie die Fortschrittsanzeige. Mit jeder neuen Zeile fängt sie frischen Mutes an, aber mitten auf der Strecke geht ihr die Puste aus. Wir haben es hier immer noch mit einer dynamischen Speicherverwaltung zu tun – jeder Append reserviert neuen Speicher, und der Verwaltungsaufwand dafür steigt mit zunehmender Größe des Arrays.

Also den Speicher vorher reservieren und das Element direkt beschreiben?

Sub Run() Handles Run
 Dim result(), part, part2 As String
 redim result(conway.Len* 1.6)
 Dim PartLen, resultIndex as Integer
 Do
  PartLen = 1
  part = Mid(conway, pos, 1)
  Do
   If pos < conway.Len Then
    part2 = Mid(conway, pos+1, 1)
    If part2 = part Then
     partlen = partlen + 1
     pos = pos + 1
    End If
   End If
  Loop Until pos = conway.Len Or part2 <> part
  result(resultindex)= partLen.ToText+part
  resultIndex = resultIndex + 1
  pos = pos + 1
 Loop Until pos > conway.Len
 conway = join(result, "")
 xojo.core.timer.CallLater 0, AddressOf doconway
End Sub

(Das ist natürlich conway3)

Oh je! Ende der Fahnenstange, ohne wirklich recht viel gewonnen zu haben? Die Verlangsamung ist immer noch bemerkbar – so ein Array ist zwar ganz schön flink im Vergleich, aber bei so großen Datenmengen, wie hier schnell zusammenkommen, liegt der Zeitgewinn eher im homöopathischen Rahmen, falls er überhaupt groß messbar ist.

Wenn das eine Sache der Indexierung und komplexen Speicherverwaltung ist: Wie wäre es dann, die Sache selbst in die Hand zu nehmen?

Der rettende MemoryBlock

Ein MemoryBlock, wie es der Name ja auch schon sagt, ist einfach ein Stück zusammenhängender Arbeitsspeicher. Was man dort reinschreibt, ist ganz beliebig: Zahlen, Strings … halt alles, was sich in Daten darstellen lässt. Die Verwaltung bleibt einem selbst überlassen. Und gegenüber der Array-Methode entfällt auch das abschließende Zusammensetzen des Ergebnisses – das wird ja direkt geschrieben. Schauen wir uns das mal an:

Sub Run() Handles Run
 Dim part, part2 As String
 Dim mb As New MemoryBlock(conway.Len * 2)
 Dim PartLen, resultIndex as Integer
 Do
  PartLen = 1
  part = Mid(conway, pos, 1)
  Do
   If pos < conway.Len Then
    part2 = Mid(conway, pos+1, 1)
    If part2 = part Then
     partlen = partlen + 1
     pos = pos + 1
    End If
   End If
  Loop Until pos = conway.Len Or part2 <> part
  mb.StringValue( resultindex, 2) = partLen.ToText+part
  resultIndex = resultIndex + 2
  pos = pos + 1
 Loop Until pos > conway.Len
 conway = mb.StringValue(0, resultindex)
 xojo.core.timer.CallLater 0, AddressOf doconway
End Sub

(Ja, genau: conway4)

Und? Ein ganzes Stück flotter jetzt, und vor allem: Keine Verlangsamung während einer Zeile mehr. Sicher, spätere Zeilen brauchen nach wie vor Ihre Zeit. Man darf aber nicht vergessen, dass Conway sehr schnell in den Bereich von 100.000 und viel mehr Bytes gerät. Aber wenn Sie mal Projekt0 gegen Projekt4 antreten lassen, hat sich der Aufwand gelohnt, oder?

Haben Sie weitere Ideen zur Optimierung? Schreiben Sie mir! Mich würde interessieren, was sich noch herauskitzeln lässt. Für ein ordentliches Programm, nebenbei gesagt, sollte der Thread auch besser bei „Stop“ gekillt werden, damit ein neuer Start, während der Thread im Hintergrund noch die Zeile abarbeitet, nicht zum Absturz führt.

Auf dass Ihre Projekte nicht an nachlassendem CPU-Enthusiasmus leiden …

Ach, und Teil 1 der kleinen Optimierungsreihe finden sie hier.

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s