Vereinfachen Sie die binäre Suche in Excel - Double VLOOKUP Trick-Implementierung mit UDF

    Ich werde dem Sparschwein von Habrs Artikeln über die binäre Suche noch eine hinzufügen . Es handelt sich um eine benutzerdefinierte Implementierung, die für alle nützlich sein kann, die in ihrer Arbeit häufig VPR verwenden, um große Listen zu vergleichen oder in großen Arrays nach Daten zu suchen.

    Hintergrund


    Alles begann damit, dass ich das sogenannte entdeckte Double-TRUE VLOOKUP-Trick (Trick mit doppelter Verwendung von VLOOKUP und TRUE im 4. Parameter). Eine detaillierte Beschreibung des Algorithmus finden Sie in Charles Williams 'Artikel "Warum 2 VLOOKUPS besser sind als 1 VLOOKUP" (am Ende des Artikels).

    Das Prinzip der Arbeit verstehen und entdecken, dass dieser Ansatz zu Tausenden sein kannMal schneller als eine konventionelle lineare Suche (VLOOKUP mit dem 4. Parameter FALSE), fing ich an, Optionen zu überdenken, um ihre Fähigkeiten zu enthüllen. Während der Implementierung haben sich mehrere geeignete Tools für die kontextbezogene Werbung herausgestellt, von denen sich eines noch weiter verbessert und dem Projekt auf Habré bereits einige Artikel gewidmet haben. Es wird SEO- und Kontextwerbefachleuten empfohlen (Ich werde sofort eine Reservierung vornehmen, die Links in den Artikeln sind bereits veraltete Versionen, die neueste Version ist bedingt 6.0, Links zum Herunterladen aller Versionen, einschließlich der neuesten, finden Sie am Ende dieses Artikels):

    » Analyse großer semantischer Kernel, oder "Erkennungsroboter"
    - Lemmatisierung in Excel oder "Erkennungsroboter 3.0"

    Trotz der unglaublichen Geschwindigkeit dieser Dateien (unglaublich für Excel) erforderte ihre Erstellung die Verwendung derselben unglaublich langen Mega-Formeln wie eine der Komponenten von Makros (der letzte der obigen Artikel enthält ein Beispiel - eine Formel mit 3215 Zeichen). Und der ganze Fehler ist die komplizierte Syntax der Funktion.

    Wenn Sie sich damit befassen, hört es auf, schwierig zu erscheinen, aber unerfahrene Benutzer, für die dieser Ansatz gedacht ist, werden ihn kaum verstehen wollen.

    Die Syntax sieht folgendermaßen aus:
    If (VLOOKUP (gesucht; Array; 1; TRUE) <gesucht; ""; VLOOKUP (gesucht; Array; n; TRUE))

    Dabei ist n die Seriennummer der Spalte, aus der der dem gewünschten Schlüssel entgegengesetzte Wert zurückgegeben werden soll.

    Anstelle von "TRUE" im 4. Parameter können Sie "1" für eine nominelle Reduzierung der Länge von Formeln verwenden, dies ändert jedoch nichts an ihrem Wesen.

    Wenn Sie den Fortschritt der Formel ankündigen, lautet dieser wie folgt:

    „Wenn eine binäre Suche nach einem Schlüssel in der ersten Spalte eines Arrays einen Wert zurückgibt, der kleiner als der Schlüssel selbst ist, geben wir eine leere Zeichenfolge zurück. Ansonsten geben wir das Ergebnis der Binärschlüsselsuche mit Offset n zurück “.

    Der Ansatz wird verwendet, um keine Werte zurückzugeben, wenn der im Array zu findende Schlüssel nicht vorhanden ist, weil häufig , wenn das Ergebnis nicht - wir brauchen nicht weniger wichtig. Sozusagen alles oder nichts. Kurz gesagt, das ist die Essenz des "Tricks".

    Lassen Sie mich daran erinnern, dass es um die Geschwindigkeitssteigerung geht, die in drei- oder vierstelligen Zahlen berechnet wird. Wenn Sie sich dem rein mathematisch nähern - auf einem Array von 2 ^ 20 Zeilen führt eine reguläre binäre Suche ~ 10 Berechnungen aus, die obige Formel ist ungefähr 20, während eine lineare Suche ~ 500.000 ergibt, d. H. das Wachstum der obigen Formel ist 25.000-fach. Wenn die bloßen Zahlen nicht beeindruckend sind, beträgt der eloquentere Vergleich 1 Sekunde gegenüber ~ 7 Stunden.

    In der Praxis ist das Wachstum nicht so signifikant (am Ende des Artikels ein Link zu einem Artikel, in dem verschiedene Methoden verglichen wurden). Dies ist hauptsächlich auf die Prozessorzeit zurückzuführen, die für zusätzliche Prozeduren aufgewendet wird, die das Programm ausführt (z. B. das Schreiben von Werten in Zellen). ABER die Verstärkung ist immer noch kritisch signifikant (~ 4000-fach).

    Gleichzeitig haben wir aber eine komplexe, völlig unbrauchbare Syntax. Nicht allen Sterblichen wurde CMD gegeben, was von Kombinationen von 2 CPR mit IF zu sprechen ist.

    Ich habe das Problem mit der komplexen Syntax mithilfe von VBA gelöst - ich habe UDF (benutzerdefinierte Funktion, Benutzerfunktion) geschrieben, die unsere bedingten Konstruktionen unter der Haube verbirgt und uns die übliche Syntax des bekannten VLOOKUP zurücklässt.

    UDF-Code:

    Public Function БИНПОИСК(a, b As Range, c As Integer) As String
    If Application.VLookup(a, b.Columns(1), 1, True) = a Then
        БИНПОИСК = Application.VLookup(a, b, c, True)
    Else
        БИНПОИСК = ""
    End If
    End Function

    Um eine Funktion in Ihrer Excel - Datei zu verwenden, um das aktuelle Buch - Modul hinzufügen, die den obigen Code hinzufügen oder heruntergeladen aus dem Link - Datei-Beispiel , wo dies ist für Sie erledigt.

    Die Funktion akzeptiert 3 Parameter als Eingabe, die Syntax ist ähnlich wie bei einem normalen VLR, mit Ausnahme des 4. Parameters, weil es wird nicht benötigt: (erforderlich; Array; Spaltennummer) .

    Am Ausgang haben wir also eine Funktion mit der üblichen Syntax und dem bekannten Verhalten, aber mit einer Geschwindigkeit, die zehn-, hundert- und tausendmal schneller ist als ein normales VLOOKUP, abhängig von der Länge des Arrays. Mit einer Einschränkung funktioniert die Funktion nur in einem Array, das vom kleinsten zum größten Array sortiert ist, korrekt. Oft ist der letzte Moment kein unüberwindbares Hindernis.

    Verwenden Sie, Kommentar. Ich werde mit Verbesserungen des Algorithmus und ähnlichen Implementierungsideen zufrieden sein.
    Ich arbeite an der Suchoptimierung in Python. Momentan habe ich sie nicht schneller als die Standardwörterbuchsuche gefunden. Gerne kommentiere ich dies auch.

    Referenzen


    Artikel über die Stunt - Double CDF“ Warum 2 pps besser als 1 „
    Vergleich verschiedener Möglichkeiten zu suchen, darunter „stunt double CDF»
    » Die neueste Version von‚Robot-Erkenner‘und alle bisherigen und einige andere Tools für die Content - bezogene Werbung, einschließlich Gegenstand dieses Artikels ist ein Link.

    Jetzt auch beliebt: