Beiträge von L3viathan

  • Priority Queue

    Ich bin gerade in Passau und schaue mir einige Vorlesungen an. Heute war eine über "Priority Queue" dabei:
    Priority Queues sind Datentyprn, die sehr schnell sind, wenn man nur auf das kleinste Element zugreifen und Elemente ergänzen will. Das ganze wird als binärer Baum realisiert und wird für prioritätsabhängige Echtzeitaufgaben verwendet, zB. scheduling. Die Rechenzeit einer Operation ist dabei O(log n). Für nähere Infos hilft sicher Wikipedia.

    Ich habe mich mal an einer AutoIt-Realisierung versucht, möglicherweise ist es hier gar nicht schneller als vergleichbare Operationen, aber es war eine hübsche Aufgabe. Auch können in meiner Version noch keine Daten angehängt werden, was für eine praktische Nutzbarkeit essentiell wäre. Das ergänze ich aber noch.

    PriorityQueue.au3
    [autoit]

    #include-once <Array.au3>
    ;Priority Queue
    Func _PQ_Add(ByRef $queue,$data)
    _ArrayAdd($queue,$data)
    $element=UBound($queue)-1
    Do
    If $queue[$element] < $queue[vater($element)] Then
    _PQ_swap($queue,$element,vater($element))
    $element=vater($element)
    Else
    ExitLoop
    EndIf
    Until $element=0
    EndFunc
    Func _PQ_extractMin(ByRef $queue)
    $return=$queue[0]
    $last=UBound($queue)-1
    $queue[0]=$queue[$last]
    _ArrayDelete($queue,$last)
    $element=0
    Do
    If (exists($queue,sohn($element,1)) And $queue[$element] > $queue[sohn($element,1)]) Or (exists($queue,sohn($element,2)) And $queue[$element] > $queue[sohn($element,2)]) Then
    _PQ_swap($queue,$element,sohn($element,_PQ_SmallestSon($queue,$element)))
    $element=sohn($element,1)
    Else
    ExitLoop
    EndIf
    Until False
    Return $return
    EndFunc
    Func _PQ_swap(ByRef $queue,$e1,$e2)
    $h=$queue[$e1]
    $queue[$e1]=$queue[$e2]
    $queue[$e2]=$h
    EndFunc
    Func vater($x)
    ;internal use only
    Return Floor(($x-1)/2)
    EndFunc
    Func sohn($x,$which=1)
    ;internal use only
    Return $x*2+$which
    EndFunc
    Func exists($queue,$element)
    ;internal use only
    If UBound($queue) > $element Then
    Return True
    Else
    Return False
    EndIf
    EndFunc
    Func _PQ_SmallestSon($queue,$element)
    ;internal use only
    If not exists($queue,sohn($element,2)) Or $queue[sohn($element,1)] < $queue[sohn($element,2)] Then Return 1
    Return 2
    EndFunc

    [/autoit]


    Jetzt mit Beispiel:

    Beispiel
    [autoit]


    #include "PriorityQueue.au3"
    Dim $queue[1]=[0]
    ;Q füllen
    _PQ_Add($queue,4)
    _PQ_Add($queue,3)
    _PQ_Add($queue,8)
    _PQ_Add($queue,2)
    _PQ_Add($queue,99)
    _PQ_Add($queue,1)
    _PQ_Add($queue,0)
    _PQ_Add($queue,4.4)
    ;Elemente geordnet ausgeben
    For $i=1 To 8
    MsgBox(64,$i & ". Element",_PQ_extractmin)
    Next

    [/autoit]

  • [beendet] µitLight Juli '10

    Wir besprechen das mal, geduldet euch bitte etwas.
    Das Benutzen von Dlls führt den Wettbewerb ad absurdum. Dann ist es nämlich kein AutoIt- sondern ein C/C++-Wettbewerb. Ausnahmsweise ist diesmal die SQLite-dll zugelassen, wie schon im Startpost erläutert. Ansonsten sind dlls aber verboten.