Array 3D effektiv durchsuchen

**BugFix**

Hi,
ich habe ein 3D-Array, das durchaus einige hundert Einträge haben kann.
Nun suche ich eine Möglichkeit dieses Array effektiv zu durchsuchen. Bisher iteriere ich durch das Array, was bei vielen Elementen nicht unbedingt zügig ist. Die Suchposition ist fix, s. Code.

[autoit]

Local $ar3D[500][20][5]

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

Func __ArraySearch(ByRef $array, $search)
For $i = 0 To UBound($array) -1
If $array[$i][0][0] = $search Then
Return $i
EndIf
Next
Return -1
EndFunc ;==>__ArraySearch

[/autoit]

Falls ihr Ideen habt, immer her damit.

**Oscar**

Kommt auf die Daten drauf an, würde ich sagen.
Wenn das Array sortiert (alphabetisch oder alphanumerisch) vorliegt, dann könnte man mit einem "kleiner/größer als" jeweils die Mitte abfragen.

**BugFix**

Sortiert sind die Daten nur direkt nach dem Erstellen. Mögliches Löschen von Elementen führt allerdings zu einer geänderten Reihenfolge, da aus Geschwindigkeitsgründen das letzte Arrayelement an die Position des gelöschten geschrieben und dann das Array per ReDim verkleinert wird.

anno2008

Hi,
wenn das Array nicht sortiert ist gibt es wohl gar keine andere Möglichkeit als die Elemente durchzugehen. Was sollte auch schneller sein?
Das Array extra zu sortieren wird wohl noch viel länger dauern. Lineare Suche ist in Listen eigentlich immer der schnellste Algorithmus (unsortiert).

**BugFix**

OK, Danke.
Ich hatte überlegt, ob es Sinn macht, wie bei Quicksearch vorzugehen. Bloß bei unsortiert müßte ich dann willkürlich die Richtung wechseln und noch zusätzlich die Bereiche verwalten.
Dann bleib ich bei meiner Version.

**Oscar**

Eine andere Überlegung wäre, zusätzlich mit diesen "Such"-Daten ein Scripting.Dictionary-Objekt anzulegen und als Key die Array-Position zu speichern. Mit dem Scripting.Dictionary-Objekt wäre die Suche schneller.

**Andy**

Hallo,
die Stringbefehle sind sehr schnell.
Man könnte beim Füllen des Arrays einen String anlegen der beispielsweise so aussehen könnte:

[autoit]

$String="[001]search1[002]search2[003]search3....[468]search468["

[/autoit]

Beim Löschen von Daten müsste nur genau wie im Array der letzte "Datensatz" an den entsprechenden Index kopiert werden.

[autoit]

stringreplace($String,"[034]search34[","[468]search468[")

[/autoit]

Gesucht wird dann nicht über den Index sondern über das Suchwort $search=" ]search356[" mittels stringinstr()
Die drei Ziffern (2 Byte würden reichen ;)) vor dem Treffer sind dann der Index des Arrays. Die Suche im String dauert nur Millisekunden.

Btw, wie ist denn ein dreidimensionales Array im Speicher abgelegt? Ggf könnte man z.B. mit der prospeed.dll das Suchwort im Speicher lokalisieren und den Index "zurückrechnen".

*EDIT*Testroutine simpel

Spoiler anzeigen

[autoit]

Local $ar3D[500][20][5]

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

$string = ""
For $x = 0 To UBound($ar3D, 1) - 1
For $y = 0 To UBound($ar3D, 2) - 1
For $z = 0 To UBound($ar3D, 3) - 1
$ar3D[$x][$y][$z] = Hex(Random(1000000)) & Hex(Random(1000000)) & Hex(Random(1000000)) & Hex(Random(1000000))
Next
Next
$string &= StringFormat("[%03s]", $x) & $ar3D[$x][0][0]
;MsgBox(262144,'Debug line ~' & @ScriptLineNumber,'Selection:' & @lf & '$string' & @lf & @lf & 'Return:' & @lf & $string) ;### Debug MSGBOX
Next

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

$t = TimerInit()
$index = __ArraySearch($ar3D, $ar3D[495][0][0])
$arraysearchtime = TimerDiff($t)

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

$t = TimerInit()
$index = __stringArraySearch($string, $ar3D[495][0][0])
$stringarraysearchtime = TimerDiff($t)

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

MsgBox(0, "Index = " & $index, _
StringFormat("__ArraySearch()" & @TAB & @TAB & "%.2f%", $arraysearchtime) & " Millisekunden" & @CRLF & _
StringFormat("__stringArraySearch()" & @TAB & "%.2f%", $stringarraysearchtime) & " Millisekunden")

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

Func __stringArraySearch($string, $search)
$pos = StringInStr($string, $search) - 4
Return Number(StringMid($string, $pos, 3))
EndFunc ;==>__stringArraySearch

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

Func __ArraySearch(ByRef $array, $search)
For $i = 0 To UBound($array) - 1
;consolewrite($array[$i][0][0]&@tab&$i&@crlf)
If $array[$i][0][0] = $search Then
Return $i
EndIf
Next
Return -1
EndFunc ;==>__ArraySearch

[/autoit]

**Oscar**

Um mal zu zeigen, wie schnell ein Dictionary.Objekt in dem Fall wäre:

Spoiler anzeigen

[autoit]

Local $ar3D[500][20][5]
Global $oDictionary = ObjCreate('Scripting.Dictionary')

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

$string = ""
For $x = 0 To UBound($ar3D, 1) - 1
For $y = 0 To UBound($ar3D, 2) - 1
For $z = 0 To UBound($ar3D, 3) - 1
$ar3D[$x][$y][$z] = Hex(Random(1000000)) & Hex(Random(1000000)) & Hex(Random(1000000)) & Hex(Random(1000000))
Next
Next
$string &= StringFormat("[%03s]", $x) & $ar3D[$x][0][0]
$oDictionary.Add($ar3D[$x][0][0], $x)
;MsgBox(262144,'Debug line ~' & @ScriptLineNumber,'Selection:' & @lf & '$string' & @lf & @lf & 'Return:' & @lf & $string) ;### Debug MSGBOX
Next

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

$t = TimerInit()
$index = __ArraySearch($ar3D, $ar3D[495][0][0])
$arraysearchtime = TimerDiff($t)
ConsoleWrite($index & @CR)

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

$t = TimerInit()
$index = __stringArraySearch($string, $ar3D[495][0][0])
$stringarraysearchtime = TimerDiff($t)
ConsoleWrite($index & @CR)

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

$t = TimerInit()
$index = $oDictionary.Item($ar3D[495][0][0])
$dictionarysearchtime = TimerDiff($t)
ConsoleWrite($index & @CR)

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

MsgBox(0, "Index = " & $index, _
StringFormat("__ArraySearch()" & @TAB & @TAB & "%.2f%", $arraysearchtime) & " Millisekunden" & @CRLF & _
StringFormat("__stringArraySearch()" & @TAB & "%.2f%", $stringarraysearchtime) & " Millisekunden" & @CRLF & _
StringFormat("__DictionarySearch()" & @TAB & "%.2f%", $dictionarysearchtime) & " Millisekunden")

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

Func __stringArraySearch($string, $search)
$pos = StringInStr($string, $search) - 4
Return Number(StringMid($string, $pos, 3))
EndFunc ;==>__stringArraySearch

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

Func __ArraySearch(ByRef $array, $search)
For $i = 0 To UBound($array) - 1
;consolewrite($array[$i][0][0]&@tab&$i&@crlf)
If $array[$i][0][0] = $search Then
Return $i
EndIf
Next
Return -1
EndFunc ;==>__ArraySearch

[/autoit]

**BugFix**

Danke für beide Ideen.

Oscar : Das ist dann ein klares Votum für das Dictionary Object.
Erspart mir dann auch einiges an Arraymanagement. Werde beim Löschen von Werten dann das Array nicht mehr verändern, sondern nur den Schlüsselwert entfernen. Bringt auch wieder Zeitgewinn.
Ist eigentlich für ein altes Projekt, dass aber einer Optimierung bedarf.
Wenn alles fertig ist, zeig ich euch, was draus geworden ist.