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
#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
Jetzt mit Beispiel:
Beispiel
#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
?
.
.