[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.

    &quot;Lineare Rechenzeit&quot;
    [autoit]

    Opt('GUIOnEventMode', 1)
    Opt('MouseCoordMode', 2)

    [/autoit] [autoit][/autoit] [autoit]

    ; Anzahl Rechtecke
    Global Const $n = 10

    [/autoit] [autoit][/autoit] [autoit]

    ; Zeug
    Global $aPos, $hGUI, $aRect[$n], $aTimer[3]
    $hGUI = GUICreate('Test', 512, 512)
    GUISetOnEvent(-3, '_Exit')
    For $i = 0 To $n - 1 Step 1
    $aRect[$i] = Rect($i + 1, Random(0, 462, 1), Random(0, 462, 1), 50, 50)
    Next
    GUISetState()

    [/autoit] [autoit][/autoit] [autoit]

    ; Hauptschleife
    While True
    $aPos = MouseGetPos()

    [/autoit] [autoit][/autoit] [autoit]

    $aTimer[0] = TimerInit()
    CheckRects($aPos)
    $aTimer[1] += TimerDiff($aTimer[0])
    $aTimer[2] += 1

    [/autoit] [autoit][/autoit] [autoit]

    If IsInt($aTimer[2]/(50000/$n)) Then ConsoleWrite(Round($aTimer[1]/$aTimer[2], 3) & ' ms' & @CRLF)

    [/autoit] [autoit][/autoit] [autoit]

    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    ; Unsere Funktion mit linearer Komplexität
    Func CheckRects($aPos)
    Local $iNr = -1
    For $i = 0 To $n - 1
    If IsInRect($aPos, $aRect[$i]) Then $iNr = $i
    Next
    ;~ If $iNr > -1 Then ToolTip('Du bist in Rechteck Nr. ' & ($aRect[$iNr])[0])
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    ; True, wenn der Punkt im Rechteck liegt
    Func IsInRect($aPos, $aRect)
    Return ($aPos[0] > $aRect[1] And $aPos[1] > $aRect[2] And $aPos[0] < $aRect[1] + $aRect[3] And $aPos[1] < $aRect[2] + $aRect[4])
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    ; Erzeugt ein Rechteck
    Func Rect($ID, $iX, $iY, $iW, $iH)
    Local $a[5] = [$ID, $iX, $iY, $iW, $iH]
    GUICtrlCreateLabel('', $iX, $iY, $iW, $iH)
    GUICtrlSetBkColor(-1, '0x' & Hex(Int(Random(110, 146, 1)),2) & Hex(Int(Random(110, 146, 1)),2) & Hex(Int(Random(110, 146, 1)),2))
    Return $a
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    Func _Exit()
    Exit
    EndFunc

    [/autoit]

    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:

    Code
    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 ;)

    Konstante Rechenzeit
    [autoit]

    #include <GDIPlus.au3>
    Opt('GUIOnEventMode', 1)
    Opt('MouseCoordMode', 2)

    [/autoit] [autoit][/autoit] [autoit]

    ; Anzahl Rechtecke
    Global Const $n = 3000

    [/autoit] [autoit][/autoit] [autoit]

    ; ##################################################
    _GDIPlus_Startup()
    Global $hBmp, $hGfx, $hBru
    $hBmp = _GDIPlus_BitmapCreateFromScan0(512, 512)
    $hBru = _GDIPlus_BrushCreateSolid()
    $hGfx = _GDIPlus_ImageGetGraphicsContext($hBmp)
    OnAutoItExitRegister('_Freigeben')
    ; ##################################################

    [/autoit] [autoit][/autoit] [autoit]

    ; Zeug
    Global $aPos, $hGUI, $aRect[$n], $aTimer[3]
    $hGUI = GUICreate('Test', 512, 512)
    GUISetOnEvent(-3, '_Exit')
    For $i = 0 To $n - 1 Step 1
    $aRect[$i] = Rect($i + 1, Random(0, 490, 1), Random(0, 490, 1), 22, 22)
    Next
    GUISetState()

    [/autoit] [autoit][/autoit] [autoit]

    ; Hauptschleife
    While True
    $aPos = MouseGetPos()

    [/autoit] [autoit][/autoit] [autoit]

    $aTimer[0] = TimerInit()
    CheckRects($aPos)
    $aTimer[1] += TimerDiff($aTimer[0])
    $aTimer[2] += 1

    [/autoit] [autoit][/autoit] [autoit]

    If IsInt($aTimer[2]/10000) Then ConsoleWrite(Round($aTimer[1]/$aTimer[2], 3) & ' ms' & @CRLF)

    [/autoit] [autoit][/autoit] [autoit]

    WEnd

    [/autoit] [autoit][/autoit] [autoit]

    ; Unsere Funktion mit konstanter Komplexität
    Func CheckRects($aPos)
    Local $iNr = _GDIPlus_BitmapGetPixel($hBmp, $aPos[0], $aPos[1]) ; $iNr = 0xFFXXXXXX
    If @error Then Return ; Für den Fall dass der Punkt z.B. außerhalb des Bereichs liegt wird @error automatisch gesetzt.
    $iNr = Int(BitAND($iNr, 0xFFFFFF)) ; $iNr = Integer
    ;~ If $iNr > 0 Then ToolTip('Du bist in Rechteck Nr. ' & ($aRect[$iNr-1])[0])
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    ; Erzeugt ein Rechteck
    Func Rect($ID, $iX, $iY, $iW, $iH)
    Local $a[5] = [$ID, $iX, $iY, $iW, $iH]

    [/autoit] [autoit][/autoit] [autoit]

    ; ##################################################
    _GDIPlus_BrushSetSolidColor($hBru, '0xFF' & Hex(Int($ID), 6))
    _GDIPlus_GraphicsFillRect($hGfx, $iX, $iY, $iW, $iH, $hBru)
    ; ##################################################

    [/autoit] [autoit][/autoit] [autoit]

    GUICtrlCreateLabel('', $iX, $iY, $iW, $iH)
    GUICtrlSetBkColor(-1, '0x' & Hex(Int(Random(110, 146, 1)),2) & Hex(Int(Random(110, 146, 1)),2) & Hex(Int(Random(110, 146, 1)),2))
    Return $a
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    Func _Exit()
    Exit
    EndFunc

    [/autoit] [autoit][/autoit] [autoit]

    Func _Freigeben()
    _GDIPlus_BrushDispose($hBru)
    _GDIPlus_GraphicsDispose($hGfx)
    _GDIPlus_BitmapDispose($hBmp)
    _GDIPlus_Shutdown()
    EndFunc

    [/autoit]

    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.

    [autoit]

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

    [/autoit]


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

    [autoit]

    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

    [/autoit]

    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

  • Zitat

    Die Lösung liegt oft in einer unüblichen Betrachtungsweise des Problems.

    8)
    Ein gutes Beispiel, wie man mit einer anderen Herangehensweise zu schnelleren (besseren) Ergebnissen kommen kann.

    Die Frage ist, gibt es eine Methode, um bei einer gegebenen Lösung eines Problems zu einer besseren Lösung zu kommen? Ja, es gibt viele Methoden, die imho beste ist aber, Menschen das Problem analysieren und nach Lösungsmöglichkeiten suchen zu lassen, welche von der bisherigen Lösung nichts oder nur sehr begrenzt wissen. Diese Technik führt oft bei Teams von (guten) Unternehmensberatern zum Erfolg, indem das erste Team nach Analyse und stetiger und kontinuierlicher Verbesserung (Kaizen) ein System verbessert, und irgendwann unweigerlich an einen Punkt kommt, an dem Verbesserungen nur noch sehr schwer oder garnicht mehr gefunden werden können.
    Nach einiger Zeit setzt man ein weiteres Team auf eben diesen Prozess an, und seltsamerweise verbessert dieses Team den Prozess weiter!
    In den meisten Unternehmen arbeiten Menschen, welche "Betriebsblind" sind. Das ist der Grund für fehlende Innovation und hohe Kosten, welche dann wiederum zu unzufriedenen Mitarbeitern führen!
    Die führenden Unternehmen sind diejenigen, welche Kreativität und ungewöhnliche "Denke" bei ihren Mitarbeitern fördern, und somit eine hohe Leistungsbereitschaft und Motivation erzeugen. Leider gibt es davon nur eine Handvoll.... :huh: