Optimierung der Suche in Arrays mit fixer Größe

[uweb]

Ich habe etwas über Optimierung nachgedacht und bin von folgenden Punkten ausgegangen :

- Bei Arrays deren Größe ich schon beim coden festlege macht es wohl Sinn die Suche darin nicht rekursiv durchzuführen.
(Die Suche lässt sich leicht auf andere Größen umschreiben.)

- Es gibt Fälle in denen ich sicher sein kann, dass es das gesuchte Elemnt im Array gibt.
Mit jeweils einer Suche für beide Fälle lässt sich die Suche auch hier optimieren.

- Macros sind schneller als Proceduren.

Da das Ergebnis wohl kaum für Code, Tipps und Tricks reicht, ich aber trotzdem auch mal etwas in den Topf werfen will, formuliere ich es mal als Frage :
Gibt es da noch etwas das man besser machen könnte?

Code: Alles auswählen

EnableExplicit

Structure BasicStructure 
  Key.i ; 0 means it is free
  First.i
  Second.i
EndStructure


Define i, Element
Define Elements = 8
Define MaxElements = 8


Dim StructuredArray.BasicStructure(MaxElements-1) ; 8 elements - 0 to MaxElements-1

Macro DebugArray()
  For i=0 To 7
    Debug Str(i) +" :      "+ Str(StructuredArray(i)\Key) +" - "+ Str(StructuredArray(i)\First) +" - "+ Str(StructuredArray(i)\Second)
  Next
  Debug "----------------------------------------------------------------------------------------------------------"  
EndMacro

Macro FindExistingElementFrom8(Keyvalue) ; for 8 Elements - 0 to 7
  If StructuredArray(3)\Key < Keyvalue
    If StructuredArray(5)\Key < Keyvalue
      If StructuredArray(6)\Key < Keyvalue
        Element = 7
      Else
        Element = 6
      EndIf
    ElseIf StructuredArray(4)\Key < Keyvalue
      Element = 5
    Else
      Element = 4
    EndIf
  ElseIf StructuredArray(1)\Key < Keyvalue
    If StructuredArray(2)\Key < Keyvalue
      Element = 3
    Else
      Element = 2
    EndIf
  ElseIf StructuredArray(0)\Key = Keyvalue
    Element = 0
  Else
    Element = 1
  EndIf
EndMacro

Macro FindElementFrom8(Keyvalue) ; for 8 Elements - 0 to 7
  If StructuredArray(3)\Key < Keyvalue
    If StructuredArray(5)\Key < Keyvalue
      If StructuredArray(6)\Key < Keyvalue
        If StructuredArray(7)\Key = Keyvalue : Element = 7 : Else : Element = -1 : EndIf
      Else
        If StructuredArray(6)\Key = Keyvalue : Element = 6 : Else : Element = -1 : EndIf
      EndIf
    ElseIf StructuredArray(4)\Key < Keyvalue
      If StructuredArray(5)\Key = Keyvalue : Element = 5 : Else : Element = -1 : EndIf
    Else
      If StructuredArray(4)\Key = Keyvalue : Element = 4 : Else : Element = -1 : EndIf
    EndIf
  ElseIf StructuredArray(1)\Key < Keyvalue
    If StructuredArray(2)\Key < Keyvalue
      If StructuredArray(3)\Key = Keyvalue : Element = 3 : Else : Element = -1 : EndIf
    Else
      If StructuredArray(2)\Key = Keyvalue : Element = 2 : Else : Element = -1 : EndIf
    EndIf
  ElseIf StructuredArray(0)\Key = Keyvalue
    Element = 0
  Else
    If StructuredArray(1)\Key = Keyvalue : Element = 1 : Else : Element = -1 : EndIf
  EndIf
EndMacro

Macro DelElement(Keyvalue)
  FindExistingElementFrom8(Keyvalue)
  Debug "DelElement("+Str(Keyvalue)+") -> #"+Str(Element) : Debug ""
  StructuredArray(Element)\Key = 0
  StructuredArray(Element)\First = 0
  StructuredArray(Element)\Second = 0
  SortStructuredArray(StructuredArray(), #PB_Sort_Ascending, OffsetOf(BasicStructure\Key), TypeOf(BasicStructure\Key))
  Elements - 1
EndMacro

Macro CreateElement(Keyvalue, Firstvalue, Secondvalue)
  Debug "CreateElement("+Str(Keyvalue)+", "+Str(Firstvalue)+", "+Str(Secondvalue)+") -> #0" : Debug ""
  StructuredArray(0)\Key = Keyvalue
  StructuredArray(0)\First = Firstvalue
  StructuredArray(0)\Second = Secondvalue
  SortStructuredArray(StructuredArray(), #PB_Sort_Ascending, OffsetOf(BasicStructure\Key), TypeOf(BasicStructure\Key))
  Elements + 1
  DebugArray()
EndMacro




For i=0 To MaxElements-1        ; Fill the structured array..
  StructuredArray(i)\Key = i+1
  StructuredArray(i)\First = i+2
  StructuredArray(i)\Second = i+3
Next


DebugArray()

DelElement(3)
DelElement(4)

DebugArray()

Debug ""
If Elements < MaxElements : CreateElement(42, 1492, 2015)
Else
  Debug "No free element available for CreateElement()."
  Debug "----------------------------------------------------------------------------------------------------------" 
EndIf

If Elements < MaxElements : CreateElement(32, 1024, 2048)
Else
  Debug "No free element available for CreateElement()."
  Debug "----------------------------------------------------------------------------------------------------------" 
EndIf


If Elements < MaxElements : CreateElement(64, 4096, 8192)
Else
  Debug "No free element available for CreateElement()."
  Debug "----------------------------------------------------------------------------------------------------------" 
EndIf


FindExistingElementFrom8(6)
Debug "FindExistingElementFrom8(6)" : Debug Element : Debug ""

FindExistingElementFrom8(32)
Debug "FindExistingElementFrom8(32)" : Debug Element : Debug ""

;- wrong result because wrong macro
FindExistingElementFrom8(3)
Debug "FindExistingElementFrom8(3)" : Debug Element : Debug ""


Debug "----------------------------------------------------------------------------------------------------------" 

FindElementFrom8(6)
Debug "FindElementFrom8(6)" : Debug Element : Debug ""

FindElementFrom8(32)
Debug "FindElementFrom8(32)" : Debug Element : Debug ""

;- right result because right macro
FindElementFrom8(3)
Debug "FindElementFrom8(3)" : Debug Element : Debug ""

DebugArray()

edit - deutsch/englisch-Mix auf englisch umgestellt
edit - Denkfehler im Text, Find mit einem If weniger

[NicTheQuick]

Für solche Dinge bieten sich Heaps an. Mit dem Fibonacci-Heap hat man eine sehr schnelle Datenstruktur, mit der Löschen in Log(n) geht und Insert und Merge sogar in konstanter Zeit gehen.

[uweb]

Danke für den Tipp und sorry für die späte Antwort.
Ich komme leider nicht so oft dazu mich mit PB zu beschäftigen. Das ist wohl auch der Grund weshalb ich seit Jahren kaum voran komme und mein Versuch auch einmal etwas beisteuer zu wollen so bescheiden ausfällt. Bei nächster Gelegenheit schaue ich mir den Fibonacci-Heap mal genauer an.