_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



    _ArraySort ($aTemp)


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


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


    $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.


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


    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.


    Next ; schließt bekanntlich den block




    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:
    $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"]]



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

  • 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:

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


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


    Und jz nochmal kurz zum aufbau:


    Ausgangs Array =>>
    $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"]]


    die Informationen sind also faktisch, durch einen delimiter, von der IP getrennt.
    Wie in dem noch beigefügten Script:
    #cs ====Tabelle sieht etwa so aus:====================================================


    ##########################################################
    ## 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 ______________________##
    ##########################################################


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


    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:
    For $i=$iStartIndex To UBound($aTemp,1) - 1
    oder einfacher
    For $i=0 To UBound($aTemp) - 1 Step 1
    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.) $aTempCleaned_RAW[1] +=> 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:
    _ArrayBinarySearch ($aTempCleaned_RAW,$aTemp[$i][0])
    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)


    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 :thumbsup: : 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
    EndFunc ;==>__clearList
    schreibt ihr ein Return $aTempCleaned_RAW


    und etwa ca um zeile 80-82 steht
    __clearList($aTest)
    ersetzt das durch
    $a=__clearList($aTest)
    _arrayDisplay($a)
    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):
    If $avArray[$iStart] > $vValue Or $avArray[$iEnd] < $vValue Then Return SetError(2, 0, -1)
    ... oder im Spoiler z14:


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


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




    //\// Neue Suche:
    $iSearchResult = _ArraySearch($aTempCleaned_RAW, $aTemp[$i][0], 0, 0, 1, 2)

  • die "Fehlerhafte"-Zeile (z116@\Include\Array.au3):
    If $avArray[$iStart] > $vValue Or $avArray[$iEnd] < $vValue Then Return SetError(2, 0, -1)


    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.