[Mittelschwer] Tutorial: Komplexitätsanalyse

Moin,

Ich weiß leider nicht genau in welche Schwierigkeitsklasse man dieses Tutorial stecken kann, daher habe ich es mal [Mittelschwer] getauft
Hier wird nicht auf Insertionsort, Mergesort oder Quicksort eingegangen, das macht man heutzutage ja schon in der Schule.

1.1. Was ist Komplexität ?
Im Allgemeinen benötigt eine Funktion abhängig von ihren Eingaben eine gewisse Ausführungszeit. Die Komplexität bietet eine Möglichkeit zu berechnen (oder eher abzuschätzen) wie lange eine Funktion zur Ausführung benötigt wenn die Eingabelänge einen bekannten Wert hat. Angenommen eine Funktion akzeptiert einen String und benötigt pro Zeichen im String die konstante Zeit c, dann wird die Funktion zum Verarbeiten eines Strings der Länge 100 die Zeit 100*c benötigen.

Komplexitätsklassen:

• Konstant: Die Ausführungszeit ist immer konstant, egal wie groß oder klein die Eingabe ist. (Beispiel Addition mit Zahlen <2^31 in einem x86 Prozessor, ob der Prozessor 1+1 rechnet oder 10000+1234567 macht keinen Unterschied, die benötigte Zeit ist 1 Takt.)
• Linear: Die Ausführungszeit wächst linear mit der Größe der Eingabe an. (Beispiel: Alle Elemente eines 1D Arrays Summieren, Jedes Element wird 1x abgefragt, also verdoppelt sich die Rechenzeit wenn sich die Arraygröße verdoppelt)
• Quadratisch: Verdoppelt sich die Eingabegröße, so vervierfacht sich die Ausführungszeit.
• uvm.

1.2. Wo taucht sowas in meinem Programm auf ?
Wir stellen uns etwas ganz einfaches vor:

• Es gibt eine Anzahl von $n Rechtecken.
• Jedes Rechteck besitzt eine Nummer.
• Es soll herausgefunden werden über welchem Rechteck sich der Mauszeiger befindet.

Im beiliegenden Skript ist der Tooltip in Zeile 35 auskommentiert, damit die Ergebnisse weniger verfälscht sind.

Beim Ausführen sollte in der Konsole eine Anzahl in Millieskunden ausgegeben werden die der Funktionsaufruf durchschnittlich benötigt. Diese Zeit notiert man sich in Bezug auf das Gewählte $n in Zeile 5.

Ein paar Werte von mir:

010 - 0.048
020 - 0.099
050 - 0.254
100 - 0.446
120 - 0.509
150 - 0.647
[[010, 0.048], [020, 0.099], [050, 0.254], [100, 0.446],  [120, 0.509], [150, 0.647]]

Die letzte Zeile geben wir bei WolframAlphaein, et voilá - Eine (wunderschöne) Gerade !
Wir haben gezeigt dass die Komlexität der Funktion linear ist, eine doppelte Anzahl Rechtecke verursacht also eine (etwa) doppelte Laufzeit.

1.3. Wie hilft mir diese Erkenntniss ?
Man kann so eine Obergrenze für die Anzahl Rechtecke abschätzen die das Programm in einer vorgegebenen Zeit verarbeiten kann. Beispielsweise in einem Spiel mit 60 FPS hat man pro Frame ca. 16.6 Millisekunden Zeit. Mit unseren Werten kommen wir auf eine Maximale Anzahl Rechtecke von ca. 3800. (Ein kleiner Test mit dem Programm zeigt: für 3800 Rechtecke werden im Schnitt ca. 16.2ms benötigt)

1.4. Gibt es eine Lösung für dieses Problem ?
In unserem speziellen Fall gibt es selbstverständlich eine Lösung (sonst hätte ich das Thema nicht ausgesucht). Es ist im Allgemeinen oft, aber nicht immer möglich die Komplexität einer Funktion durch einige Tricks zu verringern. Wie immer in der Informatik gilt: Viele Wege führen nach Rom !
Als GDI+ Liebhaber benutze ich folgenden Ansatz:

• Es gibt ein festgelegtes Gebiet in welchem die Rechtecke vorkommen (Bitmap32 via Scan0)
• Dieses Gebiet enthält ausschließlich Integerkoordinaten (sonst wird die Analogie zu einer Bitmap hinfällig)
• Die Rechtecke werden auf die Bitmap gezeichnet
• In der Farbinformation wird die ID der Rechtecke untergebracht (also z.B. Rechteck 1 hat die Farbe 0xFF000001, das gibt uns die Freiheit bis zu 16.7Mio Rechtecke zu verwenden)
• Zum Auslesen verwenden wir GetPixel an der Mauszeigerposition (GetPixel läuft mit konstanter Geschwindigkeit, es ist also egal ob ich 10, oder 10.000 Rechtecke habe)

Der Tooltip (dieses Mal in Zeile 44) ist wieder auskommentiert worden, man darf ihn selbstverständlich auch mal benutzen

Die Lange Ladezeit zu Beginn beruht auf der Benutzung der GUICtrl Funktionen, kommentiert man diese aus läd das Programm in einem Augenblick. Führt man dieses Programm aus sollte die Rechenzeit unabhängig von der Anzahl verwendeter Rechtecke sein. Bei mir dauert es z.B. 0.021 Millisekunden.

1.5. Fazit:
Bei der Kollisionskontrolle zwischen einer unbeweglichen Rechteckverteilung und einem beweglichen Punkt gibt es eine Lösung die in konstanter Rechenzeit ein Ergebnis liefert. Wenn man es richtig anstellt hat das "nachrüsten" keine sichtbaren Veränderungen zur Folge. In unserem Fall ist z.B. die Bitmap nur im RAM hinterlegt, sämtliche Zugriffe sind also prinzipiell "unsichtbar". Die Komplexität wurde von Linear auf Konstant herabgestuft. Eine Anwendung wäre z.B. jedes Programm welches eine große Anzahl anklickbarer Elemente enthält (siehe Minesweeper).

Vorteile:

• (in unserem Fall) Wesentlich schneller als die lineare Lösung
• Allgemein ermöglicht die Reduktion auf konstante Rechenzeit beliebige Skalierbarkeit des Problems ohne die Lösungsdauer zu beeinflussen.
• Der Einfache Fall der Reduktion von Linear auf Konstant kann in Verkettungen oft verwendet werden um z.B. Quadratisch auf Linear zu Reduzieren.
• Unser Fall lässt sich auf allgemeine Polygone ausweiten, für die es keine effiziente Mathematische Methode gibt um herauszufinden ob sich ein Punkt im Polygon befindet.

Nachteile:

• Es wird in einigen Fällen ziemlich viel Code benötigt. (In unserem Fall war der Aufwand überschaubar)
• Die Konstante Lösung deckt nicht alle Anwendungsgebiete der Linearen Lösung ab. (Es können z.B. keine Rechtecke außerhalb des festgelegten Gebietes gefunden werden)
• Die Lösung liegt oft in einer unüblichen Betrachtungsweise des Problems. (Rechtecke mathematisch überprüfen VS Rechtecke zeichnerisch überprüfen, normalerweise asoziiert man mit einer zeichnerischen Lösung hohen Aufwand und Ungenauigkeit)
• Es gibt nicht immer eine Lösung (viele Probleme lassen sich in ihrer Komplexität nur sehr schwer oder garnicht reduzieren)

2.1. Einfaches Erkennen der Komplexitätsklasse
Zum Einschätzen der Komplexität einer Funktion gehört das Wissen über die Komplexität der Teilfunktionen. Man weiß z.B. dass eine (grundlegende) Rechenoperation in AutoIt unabhängig von den beteiligten Werten (in etwa) in konstanter Geschwindigkeit abläuft. Eine Verkettung dieser Operationen läuft demnach ebenfalls in einer Konstanten Zeit ab.

Konstant: Beispiel für eine Verkettung von Rechenoperationen und Zuweisungen die in konstanter Zeit ablaufen.

Func Funktion($a, $b, $c, $d)
$a += $b
$a /= ($c + Cos($d))
$a = $a - $c / $b
Return $a + $b + $c + $d
EndFunc ; Konstante Rechenzeit

Linear: Hier schauen wir uns der Einfachheit halber die Funktion ArraySum an.

Func Funktion($aArray) ; Ausführungsgeschwindigkeit
If Not IsArray($aArray) Then Return $aArray ; Konstant
Local $Sum = $aArray[0] ; Konstant
For $i = 1 To UBound($aArray) - 1 Step 1 ; Linear (Ist das Array doppelt so groß läuft die Schleife doppelt so oft)
$Sum += $aArray[$i] ; Schleifeninhalt - Konstant
Next ; Konstant
Return $Sum ; Konstant
EndFunc ; Lineare + Konstante Rechenzeit

Die Funktion besteht aus einigen Konstanten Teilen (die Summe aller Konstanten Rechenzeiten nennen wir einfach mal c) und einem Linearen Teil (nennen wir l) der mit der Arraygröße skaliert (Alles in der Schleife befindliche inklusive des Schleifenkopfes selbst). Für (allgemeine) Lineare Funktionen gilt F(x) = ax + b. In unserem Fall gilt daher T(UBound) = lx + c. Wie bei allen Linearen Funktionen überwiegt für kleine x der Konstante Teil und für große x der Lineare. Für sehr große Arrays ist der konstante Teil vernachlässigbar, da meistens nur die Grenzwerte ausschlaggebend sind.

Ich hoffe ich konnte euch damit ein paar Kleinigkeiten näherbringen, Fragen, Anregungen, usw sind gerne gesehen
Edit: Das Tutorial wird ggf noch erweitert.

lg
Mars