_ArrayBinarySearch "übersieht"/klappt nicht

  • Hallo

    auf den wunsch von president chip der Thread zur frage:

    Es geht um eine zusammenführung von div. IP-Listen (mitbeschreibung)
    1. Dim. = IP; 2. Dim. = beschreibung (kann variieren, daher auch kein _ArrayUnique möglich)

    Nun soll eine Neue Liste (array) erstellt werden in die nur einträge hinzugefügt werden, wenn sie nicht schon vorhanden sind.

    Wie oben beschrieben wird ein 2d-array angeliefert, ein neues 1d erstellt, und der rest in Codeform :P

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

    _ArraySort ($aTemp)

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

    Local $aTempCleaned_RAW[1]=["IPs"]

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

    For $i=$iStartIndex To UBound($aTemp,1) - 1 ; führ den block für jede IP-Adr. in der Liste ($aTemp) aus.

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

    $iSearchResult=_ArrayBinarySearch ($aTempCleaned_RAW,$aTemp[$i][0]) ; überprüft ob der Momentane Eintrag ($aTemp[$i][0], 0=Ip, 1=Info) schon in der neuen Liste ($aTempCleaned_RAW) vorhanden ist.

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

    ;_ArrayDisplay ($aTempCleaned_RAW,"$aTempCleaned_RAW") ; nur zum test ob es echt so logisch daneben läuft ^^

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

    If $iSearchResult== (-1) Then _ArrayAdd ($aTempCleaned_RAW,$aTemp[$i][0]) ; Beim Fehler auf -1 und @error - Wenn FEHLER dann Nicht Vorhanden =>> also eintrag hinzufügen.

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

    Next ; schließt bekanntlich den block

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


    anschließend würden die IPs mit der orginalliste verglichen und die informationen in die 2. dim. ergänzt aber das dürfte erstmal egal sein :)

    PS: BSP Liste:

    [autoit]

    $aTemp[6][2] = [["127.0.0.1","Lokales System"],["127.0.0.1","localhost"],["10.0.0.1","Gateway"],["10.123.200.254","Router_1"],["192.168.10.1","DMZ denkt euch was aus :D"],["10.123.200.254","Router1"]]

    [/autoit]


    Hoffe es versteht jmd ^^ und kann mir auch noch weiterhelfen :whistling: :thumbup:

  • Hoffe es versteht jmd und kann mir auch noch weiterhelfen


    Du hast keine Frage formuliert.
    Wobei sollen wir dir also helfen?

    Prinzpielles: Die Binäre Suche setzt eine sortierte Datenstruktur voraus.
    Da du $a_Temp aber vorher sortierst und schrittweise $aTempCleanRAW hinzufügst sollte das aber der Fall sein.

    Da $a_Temp am Anfang leer ist und nur Werte von $aTempCleanRAW enthält, kann der Algorithmus nur dazu dienen die doppelten Einträge zu killen.
    Das könnte man alternativ aber auch mit ArrayUnique hinbekommen.
    Da du aber hier einen Key-Value Datenstruktur beschreibst (IP-Adresse - Beschreibung) wäre es viel cleverer ein Dictionary zu verwenden.
    Dann hast du nämlich deine Schlüssel-Wert-Struktur, die Such nach dem Schlüssel ist wahnsinnig schnell und leicht zu nutzen und doppelte Einträge werden von vornherein unterbunden.

    Hier ein Beispiel wie man dieses verwendet:

    Beispiel zum Scripting.Dictionary
    [autoit]

    ;//// Dictionary Erstellen ///////////
    $oDict = ObjCreate("Scripting.Dictionary")

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

    ;//// Einträge hinzufügen ///////////
    $oDict.add ("Berlin", 3395189)
    $oDict.add ("Hamburg", 1743627)
    $oDict.add ("München", 1259677)
    ; alternativ: (bringt keinen Fehler wenn Schlüssel schon existiert)
    $oDict("Köln") = 983347
    $oDict("Dresden") = 517052
    ;Beispiel hier: Einwohnerzahl wird der jeweiligen Stadt zugeordnet.

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

    ;//// Anzahl der Elemente bestimmen ///////////
    MsgBox(0,"Anzahl Elemente in Dictionary", $oDict.Count)

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

    ;//// Überprüft ob ein Element vorhanden ist ///////////
    If $oDict.Exists ("Bonn") Then MsgBox(0, "", "Bonn ist eingetragen") ;Bonn ist im Bsp. nicht enthalten

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

    ;//// Löscht ein Element aus dem Dictionary ///////////
    $oDict.remove ("München")

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

    ;//// Elemente aufrufen ///////////
    ConsoleWrite("Einwohner(Berlin): " & $oDict("Berlin") & @CRLF)
    ConsoleWrite("Einwohner(Dresden): " & $oDict("Dresden") & @CRLF & @CRLF)

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

    ;//// alle Schlüssel durchgehen ///////////
    For $k in $oDict.Keys
    ConsoleWrite("Einwohner(" & $k & "): " & $oDict($k) & @CRLF)
    Next
    ;/// Alle Werte statt Schlüssel erreicht man mit $oDict.Items ////

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

    ;//// Leert das Dictionary ///////////
    $oDict.RemoveAll

    [/autoit]
  • Ok ich versteh jz auch dein ansatz ^^ aber... das ist zu groß aufgebaut.

    Zur Frage :thumbup: : Warum "killt", wie du es so schöhn beschrieben hast, Binarysearch nicht die doppelten einträge?!

    Und jz nochmal kurz zum aufbau:

    Ausgangs Array =>>

    [autoit]

    $aTemp[6][2] = [["127.0.0.1","Lokales System"],["127.0.0.1","localhost"],["10.0.0.1","Gateway"],["10.123.200.254","Router_1"],["192.168.10.1","DMZ denkt euch was aus :D"],["10.123.200.254","Router1"]]

    [/autoit]

    die Informationen sind also faktisch, durch einen delimiter, von der IP getrennt.
    Wie in dem noch beigefügten Script:

    [autoit]

    #cs ====Tabelle sieht etwa so aus:====================================================

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

    ##########################################################
    ## 127.0.0.1 ___________# Lokales System _______________##
    ## 127.0.0.1 ___________# localhost ____________________##
    ## 10.0.0.1 ____________# Gateway ______________________##
    ## 10.123.200.254 ______# Router_1 _____________________##
    ## 192.168.10.1 ________# DMZ denkt euch was aus :D ____##
    ## 10.123.200.254 ______# Router1 ______________________##
    ##########################################################

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

    #ce ==================================================================================

    [/autoit]

    Die in der 2. Spalte befindliche Info lassen wir links liegen, wir arbeiten jetzt mit _arrayAdd (also rein 1Dimensional)
    Wir nehmen uns die oben abgebildete Tabelle (natürlich als array siehe "$aTemp[6][2] = [["127.0"...)

    und durchwandern sie mit einer For/Newxt schleife in Einzelnen Schritten:

    [autoit]

    For $i=$iStartIndex To UBound($aTemp,1) - 1

    [/autoit]


    oder einfacher

    [autoit]

    For $i=0 To UBound($aTemp) - 1 Step 1

    [/autoit]


    also von Anfang:0 bis variables ende (Arrayumfang-1, weil 0basieren!) Ubound($aTemp)-1

    (Jetzt erstellen wir ein 1 dimensionales Array names "$aTempCleaned_RAW" (weil arbeit mit _arrayAdd() nur 1ne Dim.)

    [autoit]

    $aTempCleaned_RAW[1]

    [/autoit]

    +=> Ein Leeres Array benötigt IMMER min. 1 Eintrag (der leer is aber egal).. darum das..._RAW[1])

    Und nun nochmal zu dem Schleifen inhalt der das eigentliche Problem dastellt:

    [autoit]

    _ArrayBinarySearch ($aTempCleaned_RAW,$aTemp[$i][0])

    [/autoit]


    Beim ersten durchlauf(also $i=0) nemhen wir also aus der Tabelle (oben) die Zeile 0 (da $i=0) und auch die erste Spalte(0, da ..."[$i][0])", mit der IP)
    => also wir haben jz schlicht die Aller 1. IP-Adresse.

    Nun schauen wir ob diese (1.IP-Adr.) in dem eben angelegen Array sind (natürlich jetzt noch nicht, aber später ist es möglich dass diese IP schon in der liste steht)
    Dies tun wir mit _ArrayBinarySearch($a_Such_In_Mir, $s_Was_du_auch_immer_suchen_moechtest)

    Syntax von _ArrayBinarySearch()

    Und WENN ein Fehler Auftritt (Rückgabewert also == (-1)) also der Eintrag NICHT gefunden wird, dann fügen wir ihn mittels _arrayadd hinzu.

    Und so testen wir jede IP der ausgangsTabelle.


    und zum Schluss biitte, guckt euch das angefügt Script an...

    :)

  • Zur Frage :thumbup: : Warum "killt", wie du es so schöhn beschrieben hast, Binarysearch nicht die doppelten einträge?!

    Ladet euch das Script einfach runter, und Testet es selbst... es klappt einfach nich?! -______-

    PS:
    es sind im Endeffekt 9Zeilen Code...
    zum Anzeigen:

    über das

    [autoit]

    EndFunc ;==>__clearList

    [/autoit]


    schreibt ihr ein

    [autoit]

    Return $aTempCleaned_RAW

    [/autoit]

    und etwa ca um zeile 80-82 steht

    [autoit]

    __clearList($aTest)

    [/autoit]


    ersetzt das durch

    [autoit]

    $a=__clearList($aTest)
    _arrayDisplay($a)

    [/autoit]


    und ihr bekommt die (eigenlich wiederholungsFreie Tabelle) angezeit

  • Statt dem Rückgabewert von _ArrayBinarySearch solltest du dir eher mal die @error-Variable abfragen.
    Da kommt nämlich immer 2 heraus.
    Du möchtest hingegen auf 3 testen.
    Wenn du dir aber mal schaust was 2 als @error-code hierbei bedeutet und dann überlegst was dein Wert "IPs" da mit zu tun hast kommst du sicherlich selbst auf die Lösung.

    Mit der aktuellen Autoit-Version kann man übrigens leere Arrays erstellen.
    Mit einem Dictionary kannst du dir den ganzen Krempel aber gleich von vornherein sparen.
    Ist einfacher und effektiver.

  • bin nich so der changelog suchti :D hm ja aber das ist eine ganz andere art in die ich mich fast komplett einarbeiten müsste...

    Da du mich jz wieder mit der @error Anomalie drauf gehoben hast... das "Problem" liegt eigenlich garnicht als solches vor.

    vorne weg: Probelm gelöst => _ArraySearch () statt der Binary Alternative.
    Im Test Klappts... jz muss es sich nurnoch in der Praxis beweisen :P


    Das Problem liegt im Unterschied: _ArrayBinarySearch() VS. _ArraySearch ()
    _ArrayBinarySearch sucht mittels lexikographischem Muster(desswegen ja auch das anfängliche _arraySort)

    die "Fehlerhafte"-Zeile (z116@\Include\Array.au3):

    [autoit]

    If $avArray[$iStart] > $vValue Or $avArray[$iEnd] < $vValue Then Return SetError(2, 0, -1)

    [/autoit]


    ... oder im Spoiler z14:

    Array.au3(UDF-Funtion _ArrayBinarySearch)
    [autoit]

    Func _ArrayBinarySearch(Const ByRef $avArray, $vValue, $iStart = 0, $iEnd = 0)
    If Not IsArray($avArray) Then Return SetError(1, 0, -1)
    If UBound($avArray, 0) <> 1 Then Return SetError(5, 0, -1)

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

    Local $iUBound = UBound($avArray) - 1

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

    ; Bounds checking
    If $iEnd < 1 Or $iEnd > $iUBound Then $iEnd = $iUBound
    If $iStart < 0 Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(4, 0, -1)

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

    Local $iMid = Int(($iEnd + $iStart) / 2)

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

    If $avArray[$iStart] > $vValue Or $avArray[$iEnd] < $vValue Then Return SetError(2, 0, -1)

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

    ; Search
    While $iStart <= $iMid And $vValue <> $avArray[$iMid]
    If $vValue < $avArray[$iMid] Then
    $iEnd = $iMid - 1
    Else
    $iStart = $iMid + 1
    EndIf
    $iMid = Int(($iEnd + $iStart) / 2)
    WEnd

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

    If $iStart > $iEnd Then Return SetError(3, 0, -1) ; Entry not found

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

    Return $iMid
    EndFunc ;==>_ArrayBinarySearch

    [/autoit]

    Wir vergleichen mit den Operatoren "<" & ">"
    Diese arbeiten auf lexikographischer Ebene

    Operatoren


    >
    Prüft, ob der erste Wert größer als der zweite ist. Die Strings werden
    lexikographisch verglichen, auch wenn die Inhalte der Strings numerisch sind.

    <
    Prüft, ob der erste Wert kleiner als der zweite ist. Die Strings werden
    lexikographisch verglichen, auch wenn die Inhalte der Strings numerisch sind.

    //Wer sich mal die mühe machen will vergleicht die 2 Funktionen der arrayUDF (au3v3381)

    __ArrayBinarySearch
    [autoit]

    Func _ArrayBinarySearch(Const ByRef $avArray, $vValue, $iStart = 0, $iEnd = 0)
    If Not IsArray($avArray) Then Return SetError(1, 0, -1)
    If UBound($avArray, 0) <> 1 Then Return SetError(5, 0, -1)

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

    Local $iUBound = UBound($avArray) - 1

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

    ; Bounds checking
    If $iEnd < 1 Or $iEnd > $iUBound Then $iEnd = $iUBound
    If $iStart < 0 Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(4, 0, -1)

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

    Local $iMid = Int(($iEnd + $iStart) / 2)

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

    If $avArray[$iStart] > $vValue Or $avArray[$iEnd] < $vValue Then Return SetError(2, 0, -1)

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

    ; Search
    While $iStart <= $iMid And $vValue <> $avArray[$iMid]
    If $vValue < $avArray[$iMid] Then
    $iEnd = $iMid - 1
    Else
    $iStart = $iMid + 1
    EndIf
    $iMid = Int(($iEnd + $iStart) / 2)
    WEnd

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

    If $iStart > $iEnd Then Return SetError(3, 0, -1) ; Entry not found

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

    Return $iMid
    EndFunc ;==>_ArrayBinarySearch

    [/autoit]
    _ArraySearch
    [autoit]

    Func _ArraySearch(Const ByRef $avArray, $vValue, $iStart = 0, $iEnd = 0, $iCase = 0, $iCompare = 0, $iForward = 1, $iSubItem = -1)
    If Not IsArray($avArray) Then Return SetError(1, 0, -1)
    If UBound($avArray, 0) > 2 Or UBound($avArray, 0) < 1 Then Return SetError(2, 0, -1)

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

    Local $iUBound = UBound($avArray) - 1

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

    ; Bounds checking
    If $iEnd < 1 Or $iEnd > $iUBound Then $iEnd = $iUBound
    If $iStart < 0 Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(4, 0, -1)

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

    ; Direction (flip if $iForward = 0)
    Local $iStep = 1
    If Not $iForward Then
    Local $iTmp = $iStart
    $iStart = $iEnd
    $iEnd = $iTmp
    $iStep = -1
    EndIf

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

    ; same var Type of comparison
    Local $iCompType = False
    If $iCompare = 2 Then
    $iCompare = 0
    $iCompType = True
    EndIf

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

    ; Search
    Switch UBound($avArray, 0)
    Case 1 ; 1D array search
    If Not $iCompare Then
    If Not $iCase Then
    For $i = $iStart To $iEnd Step $iStep
    If $iCompType And VarGetType($avArray[$i]) <> VarGetType($vValue) Then ContinueLoop
    If $avArray[$i] = $vValue Then Return $i
    Next
    Else
    For $i = $iStart To $iEnd Step $iStep
    If $iCompType And VarGetType($avArray[$i]) <> VarGetType($vValue) Then ContinueLoop
    If $avArray[$i] == $vValue Then Return $i
    Next
    EndIf
    Else
    For $i = $iStart To $iEnd Step $iStep
    If StringInStr($avArray[$i], $vValue, $iCase) > 0 Then Return $i
    Next
    EndIf
    Case 2 ; 2D array search
    Local $iUBoundSub = UBound($avArray, 2) - 1
    If $iSubItem > $iUBoundSub Then $iSubItem = $iUBoundSub
    If $iSubItem < 0 Then
    ; will search for all Col
    $iSubItem = 0
    Else
    $iUBoundSub = $iSubItem
    EndIf

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

    For $j = $iSubItem To $iUBoundSub
    If Not $iCompare Then
    If Not $iCase Then
    For $i = $iStart To $iEnd Step $iStep
    If $iCompType And VarGetType($avArray[$i][$j]) <> VarGetType($vValue) Then ContinueLoop
    If $avArray[$i][$j] = $vValue Then Return $i
    Next
    Else
    For $i = $iStart To $iEnd Step $iStep
    If $iCompType And VarGetType($avArray[$i][$j]) <> VarGetType($vValue) Then ContinueLoop
    If $avArray[$i][$j] == $vValue Then Return $i
    Next
    EndIf
    Else
    For $i = $iStart To $iEnd Step $iStep
    If StringInStr($avArray[$i][$j], $vValue, $iCase) > 0 Then Return $i
    Next
    EndIf
    Next
    Case Else
    Return SetError(7, 0, -1)
    EndSwitch

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

    Return SetError(6, 0, -1)
    EndFunc ;==>_ArraySearch

    [/autoit]


    //\// Neue Suche:

    [autoit]

    $iSearchResult = _ArraySearch($aTempCleaned_RAW, $aTemp[$i][0], 0, 0, 1, 2)

    [/autoit]
  • die "Fehlerhafte"-Zeile (z116@\Include\Array.au3):

    [autoit]

    If $avArray[$iStart] > $vValue Or $avArray[$iEnd] < $vValue Then Return SetError(2, 0, -1)

    [/autoit]


    Warum ist denn die Zeile fehlerhaft?

    Um herauszufinden ob ein Wert in einer sortierten Datenstruktur existiert ist es doch das einfachste zu schauen ob der Wert kleiner als der kleinste Wert oder größer als der größte Wert ist - also ob der Wert überhaupt im Wertebereich liegt.
    Der wirklich Fehler liegt immer noch auf deiner Seite.
    Durch die Vorbelegung des Arrays mit dem Wert "IPs" zerstörst du die Sortierung des Arrays - es ist nicht mehr sortiert.
    "IPs", der Wert der am Anfang steht, ist größer als alle einzufügenden Werte - logisch das das nicht klappt.

    Du hast also mehrere Möglichkeiten:

    • Ohne Vorbelegung des Arrays arbeiten
    • Nach jedem ArrayAdd das Array neu sortieren ("den Wert IPs damit ans Ende schieben")
    • ArrayBinarySearch erst ab dem zweiten Element suchen lassen (_ArrayBinarySearch($aTempCleaned_RAW, $aTemp[$i][0], 1)) - wäre das einfachste
    • ArraySearch nehmen - ist langsamer als ArrayBinarySearch
    • ArrayUnique statt dieser manuellen Variante nutzen
    • Ein Dictionary verwenden - ist schneller als beide Varianten und syntaktisch einfacher.

    Einmal editiert, zuletzt von AspirinJunkie (21. April 2014 um 22:14)