Komplexeres? schnelles durchsuchen größerer Arrays

    Hi,
    diese Diskussion hatten wir schon einmal , oder jedenfalls ähnlich...

    Okay, ersteinmal danke für die vielen Antworten!

    @Großvater

    Dein Beispielscript beschränkt sich jetzt auch auf sehr wenige Daten. Sprich nur 3 Elemente.
    Die BinarySearch wird wohl die Binärsuche sein - aber die Binärsuche ist in meinem Fallen nicht so
    angebracht wie die Interpolationssuche - soweit ich das richtig verstanden habe.

    Das Array entsteht durch das Auslesen einer Textdatei und per StringSplit("Textdatei",@CR) ^^

    autoBert

    Gut zu wissen, dass der Vergleich funktioniert, das wusste ich nicht!
    Aber zum Ermitteln der Startposition zum Suchen müssen die Strings ja auch addiert und dividiert werden..
    also bleibt es dabei, jedem Buchstaben einen Zahlenwert zuzuweisen, oder nicht?

    • Offizieller Beitrag

    Die erwartete Laufzeit von Binärsuche auf einem sortierten Feld ist O(log n), die von Interpolationssuche O(log log n). Hängt ein bisschen von den Daten ab, aber bei Gleichverteilung wäre es so. Für die Ipolseach würde ich in dem Fall einfach annehmen, dass alle Buchstaben gleich "breit" seien, nämlich 1/26. Das wird die Formel einfach halten und trotzdem schön schnell sein im Durchschnitt…

    Johannes

    Hallo abc_User,

    Zitat von abc-user

    Aber zum Ermitteln der Startposition zum Suchen müssen die Strings ja auch addiert und dividiert werden..

    Dann wird es sich wohl nicht auf Strings übertragen lassen.

    Ich habe das Verfahren dahin umgestellt dass jeweils die Mitte der Daten genommen wird, so dass bei jedem Veruch der z keinem Treffer führt die Datenmenge halbiert wird. Ich weiss dass dieses Verfahren nicht neu ist und auch einen Namen hat. Getestet habe ich gegen _ArraySearch und _ArrayBinarySearch mit 20000 zufälligen Strings.

    Spoiler anzeigen
    [autoit]

    #include <array.au3>

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

    Dim $aArray[20000]
    For $i = 0 To 19999
    Dim $string = Chr(Random(65, 90, 1))
    For $j = 1 To 79
    $string &= Chr(Random(97, 122, 1))
    $aArray[$i] = $string
    Next
    Next
    _ArraySort($aArray)
    _ArrayDisplay($aArray)

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

    $iR = Random(15000, 19000, 1) ; zufällig ein Elementindex betimmen
    $sToSearch = $aArray[$iR] ;zu suchender String

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

    $anfang = TimerInit()
    For $x = 1 To 100
    $iMS = _MySearch($aArray, $sToSearch)
    Next
    $ende = TimerDiff($anfang)
    ConsoleWrite($ende & " MySearch" & @CRLF)

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

    $anfang = TimerInit()
    For $x = 1 To 100
    $iAS = _ArraySearch($aArray, $sToSearch)
    Next
    $ende = TimerDiff($anfang)
    ConsoleWrite($ende & " _ArraySearch" & @CRLF)

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

    $anfang = TimerInit()
    For $x = 1 To 100
    $iABS = _ArrayBinarySearch($aArray, $sToSearch)
    Next
    $ende = TimerDiff($anfang)
    ConsoleWrite($ende & " _ArrayBinarySearch" & @CRLF)

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

    ConsoleWrite($iR & " " & $iMS & " " & $iAS & " " & $iABS & @CRLF)
    ConsoleWrite("ToSearch " & $aArray[$iR] & @CRLF)
    ConsoleWrite("MySearch " & $aArray[$iMS] & @CRLF)
    ConsoleWrite("Arrayearch " & $aArray[$iAS] & @CRLF)
    ConsoleWrite("ArrayBinry " & $aArray[$iABS] & @CRLF)

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

    Func _MySearch($array, $value)
    Local $low = 1;
    Local $high = UBound($array) - 1
    Local $mid = Int(($high + $low) / 2)

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

    While $array[$low] <= $value And $array[$high] >= $value
    $mid = Int(($high + $low) / 2)
    If $array[$mid] < $value Then
    $low = $mid + 1;
    ElseIf $array[$mid] > $value Then
    $high = $mid - 1;
    Else
    Return Int($mid);
    EndIf
    WEnd
    If $array[$low] == $value Then
    Return $low;
    Else
    Return -1; // Not found
    EndIf
    EndFunc ;==>_MySearch

    [/autoit]
    • Die gute Nchricht zuerst, es funktioniert mit String's und schlägt _ArraySearch.
    • die chlechte Nachricht es geht noch schneller_ArrayBinarySearch ist fast immer Sieger und schlägt_ArraySearch um > Faktor 100 und meine Suche im Schnitt um Faktor 1,5 (knapp 40 ms absolut)


    Hier die Ergebnisse für die letzten Messungen (Zeit im mS für 100 Durchläufe):

    Zitat

    39.1817954516566 MySearch
    11023.0758378509 _ArraySearch
    48.4206791645307 _ArrayBinarySearch


    Falls sehr viele Suchläufe stattfinden sollen würde sich aber imho eine SQLite-Datenbank empfehlen, denn da weiss ich dass ähnliche suchen in einer IN-Memory DB < 5 ms möglich sind, Jedoch bin ich mir nicht sicher ob das Einlesen diesen Zeitvorteil wieder zunichte macht.

    Edit: nach Skriptumstellung auch Beitrag komplett neu
    mfg autoBert

    Edit bernd670 : AutoIt-Tag an die richtige Stelle gesetzt

    2 Mal editiert, zuletzt von bernd670 (30. Dezember 2010 um 23:20)

    Zitat von peethebee

    Die erwartete Laufzeit von Binärsuche auf einem sortierten Feld ist O(log n), die von Interpolationssuche O(log log n). Hängt ein bisschen von den Daten ab, aber bei Gleichverteilung wäre es so. Für die Ipolseach würde ich in dem Fall einfach annehmen, dass alle Buchstaben gleich "breit" seien, nämlich 1/26. Das wird die Formel einfach halten und trotzdem schön schnell sein im Durchschnitt…

    Johannes


    Hallo Chef,
    das kann ich jetzt nicht nachvollziehen, denn in den Strings im Array können ja nicht nur die 26 englischen Buchstaben vorkommen. Könntest Du mal etwas näher erläutern, wie Du dir die Implementation denkst?

    @abc-user:
    Lass Dich vom Namen _ArrayBinarySearch() nicht verunsichern. Der Name steht nur nur eine Methode, die in korrekt sortierten Arrays schneller zum Erfolg führt.

    Hallo abc_user,

    ich habe mein Testkript jetzt auf 1000 Suchläufe erweitert:

    Spoiler anzeigen
    [autoit]

    #include <array.au3>

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

    Dim $aArray[20000]
    For $i = 0 To 19999
    Dim $string = Chr(Random(65, 90, 1))
    For $j = 1 To 79
    $string &= Chr(Random(97, 122, 1))
    $aArray[$i] = $string
    Next
    Next
    _ArraySort($aArray)
    ;_ArrayDisplay($aArray)

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

    Dim $aSuchen[1001][11]
    For $x = 1 To 1000
    $aSuchen[$x][0] = Random(0, 19999, 1) ; zufällig ein Elementindex betimmen
    $aSuchen[$x][1] = $aArray[$aSuchen[$x][0]] ;zu suchender String
    Next

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

    $Zeit = TimerInit()
    $aSuchen[0][4] = $Zeit
    For $x = 1 To 1000
    $aSuchen[$x][2] = _MySearch($aArray, $aSuchen[$x][1])
    If $aSuchen[$x][1] == $aArray[$aSuchen[$x][2]] Then
    $aSuchen[$x][3] = True
    Else
    $aSuchen[$x][3] = False
    EndIf
    $aSuchen[$x][4] = TimerDiff($aSuchen[0][4])
    $aSuchen[0][4] = TimerInit()
    Next
    $ende = TimerDiff($Zeit)
    ConsoleWrite($ende & " MySearch" & @CRLF)

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

    $Zeit = TimerInit()
    $aSuchen[0][7] = $Zeit
    For $x = 1 To 1000
    $aSuchen[$x][5] = _ArraySearch($aArray, $aSuchen[$x][1])
    If $aSuchen[$x][1] == $aArray[$aSuchen[$x][5]] Then
    $aSuchen[$x][6] = True
    Else
    $aSuchen[$x][6] = False
    EndIf
    $aSuchen[$x][7] = TimerDiff($aSuchen[0][7])
    $aSuchen[0][7] = TimerInit()
    Next
    $ende = TimerDiff($Zeit)
    ConsoleWrite($ende & " _ArraySearch" & @CRLF)

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

    $Zeit = TimerInit()
    $aSuchen[0][10] = $Zeit
    For $x = 1 To 1000
    $aSuchen[$x][8] = _ArrayBinarySearch($aArray, $aSuchen[$x][1])
    If $aSuchen[$x][1] == $aArray[$aSuchen[$x][8]] Then
    $aSuchen[$x][9] = True
    Else
    $aSuchen[$x][9] = False
    EndIf
    $aSuchen[$x][10] = TimerDiff($aSuchen[0][10])
    $aSuchen[0][10] = TimerInit()
    Next
    $ende = TimerDiff($Zeit)
    ConsoleWrite($ende & " _ArrayBinarySearch" & @CRLF)
    $aSuchen[0][0] = "zufälliger Index" ;per Rando ermittelter Index
    $aSuchen[0][1] = "Suchstring" ;dazgehörigee tring
    $aSuchen[0][2] = "MySearch ID" ;gefundener Index Myerach
    $aSuchen[0][3] = "MySearch True/False" ;richtig
    $aSuchen[0][4] = "MySearch Zeit"
    $aSuchen[0][5] = "_ArraySearch ID"
    $aSuchen[0][6] = "_ArraySearch True/False"
    $aSuchen[0][7] = "_ArraySearch Zeit"
    $aSuchen[0][8] = "_ArrayBinarySearch ID"
    $aSuchen[0][9] = "_ArrayBinarySearch True/False"
    $aSuchen[0][10] = "_ArrayBinarySearch Zeit"
    _ArrayDisplay($aSuchen)

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

    Func _MySearch($array, $value)
    Local $low = 0;
    Local $high = UBound($array) - 1
    Local $mid = Int(($high + $low) / 2)

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

    While $array[$low] <= $value And $array[$high] >= $value
    $mid = Int(($high + $low) / 2)
    If $array[$mid] < $value Then
    $low = $mid + 1;
    ElseIf $array[$mid] > $value Then
    $high = $mid - 1;
    Else
    Return Int($mid);
    EndIf
    WEnd
    If $array[$low] == $value Then
    Return $low;
    Else
    Return -1; // Not found
    EndIf
    EndFunc ;==>_MySearch

    [/autoit]

    Ergebnis:

    Zitat

    532.497566031437 MySearch
    63052.335981249 _ArraySearch
    465.797468672694 _ArrayBinarySearch

    mir ist immer noch nicht bekannt wie man dieses Suchverfahren nennt, es ist jedoch sehr schnell (im Schnitt fast genauso schnell wie _ArrayBinarySearch, in Einzelfällen auch chneller) benötigt wie dieses aber ein sortiertes Array. _ArrayBinarySearch ist aber meines Erachtens noch durch eine SQLite (In-Memory) DB zu schlagen, nicht umsonst nimmt BugFix in einigen Funcs für Array's SQLite zu Hilfe,

    Edit: Im ArrayDisplay von Zwichenzeit seit 1. Suchlauf auf Einzelzeiten umgestellt

    Edit2: $low angepasst, danke Kleiner
    mfg autoBert

    2 Mal editiert, zuletzt von autoBert (31. Dezember 2010 um 13:03)

    Zitat von Großvater

    Hallo autoBert,

    man nennt es Binäre Suche (vgl. Pseudocode).

    Ok, jetzt ist mir klar warum die Messungen ein ähnliches Laufzeitverhalten wie _ArrayBinaryearch ergeben. Die wenigen Fälle wo MySearch schneller war ist wohl auf den von Kleiner bemerkten Fehler $low = 1 zurückzuführen. Diese Zeile habe ich vergessen anzupassen, als ich das Skript für Interpolationsuche von @abc_User umgeschrieben habe (=genau eine Zeile 83 in der Func, [Zeile 80 ist überflüsig fällt mir gerade auf] jetzt 2 Zeilen 78, da ich dies im vorhergehenden Post berichtigt habe).

    @abc_User: im von @Grossvater geposteten Link ist eine interesante Aussage:

    Zitat

    In Spezialfällen kann die Interpolationssuche schneller sein als die binäre Suche.

    Dies interpretiere ich so, dass ich die beiden im allgemeinen nicht sonderlich im Laufzeitverhalten unterscheiden.

    Kleiner: ob Ceiling oder Int besser geeignet ist, darüber mache ich mir keine Gedanken, denn wenn ich einmal vor einem solchen Problem stehen sollte fällt mir sicher _ArrayBinarySearch ein,

    mfg autoBert

    Hi!

    Habe mich ein wenig durch Wiki gelesen und habe das Thema gefunden Grover-Algorithmus.
    Dabei kam mir die Idee das zu durchsuchende Array aufzuteilen und rasugekommen ist für mich eine Vergleichbare Funktion zu Sortierten Unsortierten Array´s. ^^

    _ArraySearchQuad:

    Spoiler anzeigen
    [autoit]

    ;===================================================================================================================================#
    ;Function Name....: _ArraySearchQuad($vArray, $key)
    ;Description......: Dateien Finden
    ;$vArray..........: Array 1D
    ;$key........... : Gesuch
    ;
    ;Return Value(s)..: Fund/Not Fund
    ; @error -1 wenn kein Array oder kein Fund
    ;
    ;Author(s)........: Kleiner (http://www.autoit.de) # 01.01.2011 00:00 #
    ;====================================================================================================================================#
    Func _ArraySearchQuad(Const $vArray, Const $key)
    If IsArray($vArray) Then
    Local Const $Ub = UBound($vArray)
    Local $RD = Random(2, ($Ub - 1), 1)
    Local Const $1V = Int($Ub / 6) + 4
    Local Const $2V = Int($Ub / 3) + 6
    Local Const $3V = Int($Ub / 2) + 11
    Local Const $4V = Int($Ub - $2V) + 22
    Local Const $5V = Int(($1V / 2))
    Local Const $6V = ($4V + $5V) - 1
    Local Const $7V = ($4V + $1V) - 1
    If $vArray[0] = $key Then Return 0
    If $Ub <= 270 Then
    For $i = 0 To $Ub - 1
    If $vArray[$i] = $key Then Return $i
    Next
    Return SetError(1, 0, -1)
    EndIf
    For $i = 1 To $5V
    Switch $key
    Case $vArray[$i]
    Return $i
    Case $vArray[(($1V - 1) + $i)]
    Return (($1V - 1) + $i)
    Case $vArray[($1V - $i)]
    Return ($1V - $i)
    Case $vArray[(($2V - 1) + $i)]
    Return (($2V - 1) + $i)
    Case $vArray[($2V - $i)]
    Return ($2V - $i)
    Case $vArray[(($3V - 1) + $i)]
    Return (($3V - 1) + $i)
    Case $vArray[($3V - $i)]
    Return ($3V - $i)
    Case $vArray[(($4V - 1) + $i)]
    Return (($4V - 1) + $i)
    Case $vArray[($4V - $i)]
    Return ($4V - $i)
    Case $vArray[($6V + $i)]
    Return ($6V + $i)
    Case $vArray[($7V + $i)]
    Return ($7V + $i)
    Case $vArray[($Ub - $i)]
    Return ($Ub - $i)
    Case $vArray[$RD]
    Return ($RD)
    EndSwitch
    $RD = Random(2, ($Ub - 1), 1)
    Next
    EndIf
    Return SetError(1, 0, -1)
    EndFunc ;==>_ArraySearchQuad

    [/autoit]

    Lg Kleiner

    4 Mal editiert, zuletzt von Kleiner (2. Januar 2011 um 00:45)

    Hi!


    @Großvater 

    Spoiler anzeigen
    [autoit]

    $DefaultCaseSense = "AHK" ; oder auch "AU3"

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

    $Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    $aChars = StringSplit($Chars, "", 2)
    $Len = StringLen($Chars)
    $string = @CRLF

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

    For $I = 0 To $Len - 1
    For $J = 0 To $Len - 1
    For $K = 0 To $Len - 1
    $string &= $aChars[$I] & $aChars[$J] & $aChars[$K] & @CRLF
    Next
    Next
    Next

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

    $Find = "ZAB"

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

    If $DefaultCaseSense = "AU3" Then
    $CaseSense = 0
    Else
    $CaseSense = 2
    EndIf

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

    $OuterLoop = 5
    $InnerLoop = 200
    $Dauer = 0

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

    For $C = 1 To $OuterLoop ; --------> 5x wird die äußere schleife aufgerufen
    $Start = TimerInit()
    For $I = 1 To $InnerLoop ;-----> 200x wird die innere schleife aufgerufen
    $Index = StringInStr($string, @CRLF & $Find & @CRLF, $CaseSense)
    Next
    $Dauer += TimerDiff($Start)
    Next

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

    ; Wehr dann nicht die Rechnung [ $Dauer / ($OuterLoop * $InnerLoop) ] bei mein Senilen Rechner komm ich auf 10 ms

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

    $Found = StringMid($string, $Index + 2, StringLen($Find))
    MsgBox(0, "AU3-Ergebnis:", "Dauer (" & $InnerLoop & " Durchläufe): " & Round($Dauer / ($OuterLoop * $InnerLoop)) & " ms - Treffer: " & $Found)
    Exit

    [/autoit]

    ;)

    Lg Kleiner

    Einmal editiert, zuletzt von Kleiner (1. Januar 2011 um 23:57)

    • Offizieller Beitrag
    Zitat von Kleiner

    Habe mich ein wenig durch Wiki gelesen und habe das Thema gefunden Grover-Algorithmus.
    Dabei kam mir die Idee das zu durchsuchende Array aufzuteilen und rasugekommen ist für mich eine Vergleichbare Funktion zu Sortierten Unsortierten Array´s. ^^

    Rein rechnerisch ist dein Algorithmus bei Arrays mit 11 bis ca. 260 Elementen sehr Fehleranfällig! Weil du da, im ungünstigen Fall, Elemente ansprichst die es gar nicht gibt.

    Bei diesem Beispiel-Script muss der Wert von $iElemente >= 263 sein damit es fehlerfrei läuft!

    Spoiler anzeigen
    [autoit]

    $iElemente = 150
    Dim $aArray[$iElemente]
    For $i = 0 To $iElemente - 1
    Dim $string = Chr(Random(65, 90, 1))
    For $j = 1 To 79
    $string &= Chr(Random(97, 122, 1))
    $aArray[$i] = $string
    Next
    Next

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

    For $i = 0 To $iElemente - 1
    $iSuchen = $i
    $szSuchen = $aArray[$iSuchen]

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

    ConsoleWrite("suche Element: " &$iSuchen & @CRLF)
    $ret = _ArraySearchQuad($aArray, $szSuchen)
    ConsoleWrite("gefundenes Element: " & $ret & @CRLF)
    Next

    [/autoit]

    Hallo kleiner,

    ich hatte jetzt eigentlich eine echte Rakete erwartet, aber für den Fall von abc_user mit vorsortiertem Array ist es nicht brauchbar. Ich habe im Testskript von mir _arrayserach gegen _arrayserachQuad ausgetauscht. Herausgekommen sind folgende Werte für 1000 Suchvorgänge in 20000 vorsortierten Datensätzen:

    Code
    562.092947567358 MySearch
86359.919766339 _ArraySearchQuad
562.9634492652 _ArrayBinarySearch

    Frohes gutes neues Jahr autoBert

    Hallo Kleiner,

    das Ergebnis in der MsgBox lautet aber:

    [autoit]

    "Dauer (" & $InnerLoop & " Durchläufe): " & Round($Dauer / ($OuterLoop * $InnerLoop)) & " ms

    [/autoit]

    "Dauer (200 Durchläufe)".

    Wenn Du das nochmal durch $InnerLoop teilst, bekommst Du die durchschnittliche Zeit für einen Durchlauf. Das sieht dann zwar schon "schmeichelhafter" aus, wären auf meinen "Superrechner" (Core2Duo E7300, 3GB RAM) aber immer noch 7,56 ms für AU3 und 0,78 für AHK, und mir gefallen die 0,78 nun mal besser. ;)

    Ich habe drei Anwendungen, die auf eine schnelle Stringsuche angewiesen sind. Die laufen auf halbwegs aktuellen Bürorechnern zwar inzwischen auch mit AU3, im direkten Vergleich zum alten AHK-Skript ist aber die verzögerte Reaktion deutlich spürbar.


    Edit: Hab ich doch fast vergessen:

    Ich wünsche Allen ein gutes neues Jahr!

    Zitat von Großvater

    Anmerkung 1: Die Funktion StringInStr() scheint nicht optimal umgesetzt zu sein.

    Zitat von Großvater

    Ergebnisse:
    Schlechtestes AHK Ergebnis bei 10 abwechselnd mit AU3 gestarteten Durchläufen: 156 ms
    Bestes AU3 Ergebnis bei 10 abwechselnd mit AHK gestarteten Durchläufen: 1512 ms


    Hab mir deswegen auch nochmal AutoHotkey besorgt um das ganze nachzuvollziehen.
    Hab die Zeitmessung etwas umgebaut so dass die Timer-Fehler gesenkt werden und folgendes sind nun meine Ergebnisse (auf nem Netbook):

    Ergebnisse Zeitvergleich Au3-AHK
    Code
    Not Case-Sensitive
	AHK: 	2,68ms
	AU3:	33,69ms

Case-Sensitive: 
	AHK:	0,96ms
	AU3:	1,45ms


    Die Case-Sensitive-Aufrufe wurden bei Au3-StringInStr mit dem 3.Parameter=2 gemacht.
    Die Funktionen wurden dabei 10.000x bzw. 1.000x aufgerufen um Streuungen auszugleichen.
    Diese Ergebnisse scheinen deine Vermutung, dass die StringInStr-Funktion nicht optimal umgesetzt wurde, zu bestätigen.
    Wir können das sogar weiter eingrenzen:
    Die Implementierung der Case-InSensitive Methode ist ziemlich langsam implementiert.
    Sobald das ganze nicht Case-Sensitive ist sind die Ergebnisse zufriedenstellend.
    Das AHK da immer noch schneller ist, ist bekannt und liegt ja am umfangreicheren Interpreter von Au3.
    Aber es liegen dann keine Welten mehr dazwischen.

    Wie im anderen Thread vorgeschlagen kannst du die Stringsuche auch in eine Dll auslagern wenn sie dermaßen zeitkritisch für dich ist oder die Au3-Entwickler mal darauf hinweisen ob sie sich die Implementierung der Groß und Kleinschreibung nicht nochmal anschauen sollten... ;)

    Einmal editiert, zuletzt von AspirinJunkie (2. Januar 2011 um 11:48)