binäre Suche in einem Array in Perl

Question

Ich habe ein Array von Hex-Zahlen, und ich muss über andere Zahlen gehen und prüfen, ob sie in diesem Array erscheinen. Im Moment verwende ich eine foreach Schleife, die jedes Mal über das gesamte Array geht. Gibt es eine Möglichkeit, es schneller zu machen, indem Sie das Array zuerst sortieren und dann binäre Suche darauf implementieren.

Der Code zur Zeit:

sub is_bad_str{ 
    my ($str, @keys) = @_; 
    my $flag = 0; 
    my ($key, $hex_num); 
     if ($str =~ m/14'h([0-9a-f][0-9a-f][0-9a-f][0-9a-f])/;){ #'# fixes bad highlighting 
    $hex_num = $1; 
     } 
    if (defined $hex_num){ 
    foreach $key (@keys){ 
     if ($hex_num =~ /\Q$key\E/i){ 
      $flag = 1; 
      last; 
     } 
    } 
    } 
    if (($flag == 0) && (defined $hex_num)){ 
    return 1;#Bad str 
    }else{ 
    return 0;#Good str 
     } 
} 

Answer 1

Es gibt vier Strategien, um eine effiziente Massensuche in einer Gruppe von Daten in Perl durchzuführen.

Die vollständige Analyse wird unten skizziert, aber zusammenfassend wird die beste Leistung bei durchschnittlichen Zufallsdatensätzen mit einer signifikanten Anzahl von Suchvorgängen natürlich durch Hash-Nachschlagevorgänge angeboten, gefolgt von viel schlechteren BST.

---

1. Binary (half-Intervall) Suche eines Arrays.

   Dies ist offensichtlich ein Standard algorithmischen Ansatz.

   Performance-Kosten:

   • O(N * log N) für die erste Sortierung.
   • O(N) im Durchschnitt für das Einfügen/Entfernen von Daten in der Liste einmal sortiert. Perl-Arrays sind keine verknüpften Listen, also ist es kein O(log N).
   • O(log N) für jede Suche.
     
     

   Implementierung: the algorithm ist so einfach, dass DIY einfach ist. Wie immer gibt es CPAN-Module und sollte wahrscheinlich anstelle von DIY sowieso verwendet werden: Search::Binary.

   ---

2. Binary Search Trees (BSTs)

   Leistung Kosten:

   • O(N * log N) für erste Sortierung.
   • O(log N) im Durchschnitt für das Einfügen/Entfernen von Daten in der Liste einmal sortiert
   • O(log N) für jede Suche.

   
   

   Implementierung: mehrere Varianten existieren auf CPAN: Tree::Binary::Search, Tree::Treap, Tree::RedBlack. Die letzteren beiden have better average performance and smaller performance fluctuations, algorithmically.

   Vergleich: Wenn die Daten ändern, müssen Sie BST verwenden Umsortieren Kosten zu vermeiden. Wenn Ihre Daten zufällig sind und sich nach der Sortierung nie ändern, können Sie eine einfache Binärsuche über BST verwenden, aber BSTs können besser abgestimmt werden, wenn die letzte Unze der Leistung wichtig ist (BST kann für eine schnellere durchschnittliche Suche optimiert werden als die Listen-Suche) Kosten basierend auf der Datenverteilung - siehe Wiki's "Optimal binary search trees" section oder wenn Ihre Datenverteilung einen der speziellen Bäume wie Treap oder Rot/Schwarz bevorzugt.

   ---

3. Abgekürzte scan-Lookups (kurzgeschlossen).

   Dies sind lineare Scan-Suchen in einer nicht sortierten Liste, die die Suche STOPPEN, sobald das Element gefunden wurde.

   Leistung: O(N) pro Suche nach Zufallsdaten, sondern ein schneller O(N) (sagen wir, N/2) als Voll Liste Suche wie grep. Keine zusätzlichen Kosten.

   Implementierung: Es gibt 3 Möglichkeiten, um sie in Perl zu tun:

   • Smart match Operator (~~). Das Problem ist, dass es NUR in Perl 5.10 und höher verfügbar ist.
   • Ihre eigene Schleife, die next; einmal gefunden hat.
   • List::MoreUtils Modul first() Subroutine.

   Vergleich:

   • zunächst zwischen den drei Implementierungen oben ist List::MoreUtils::first schneller als die DIY-Schleife, weil es in XS implementiert ist; Daher sollte es in Perl-Versionen vor 5.10 verwendet werden. Smart Match ist wahrscheinlich genauso schnell, obwohl ich die beiden Benchmarks machen würde, bevor Sie das eine oder andere in Perl 5.10+ auswählen.

   • Zweitens, um andere Methoden kurzgeschlossen Suche zu vergleichen, gibt es nur drei Ränder Fälle, in denen es verwendet werden soll:

     A. Speicherbeschränkungen. Sowohl die Suche nach sortierten Listen als auch BST- und Hash-Lookups haben einen Speicherbedarf von mindestens 2*N. Wenn Sie eine Speicherbeschränkung (angesichts Ihrer Listengröße) so schwerwiegend erleiden, dass N vs 2*N Speicher zu einer nicht verhandelbaren Kostenbarriere wird, dann verwenden Sie eine Kurzschlusssuche und zahlen die Leistungsstrafe rechtzeitig. Dies gilt insbesondere, wenn Sie einen großen Datensatz in Stapeln/zeilenweise verarbeiten, um zu vermeiden, dass das gesamte Objekt zuerst im Speicher abgelegt wird.

     B. Wenn Ihre Daten so verteilt und vorsortiert sind, dass ein Großteil der Suchanfragen ihren Steinbruch ganz am Anfang der Liste finden würde. Wenn dies der Fall ist, kann es die schickeren Methoden wie BST der binären Suche trotz ihrer offensichtlich schneller O (log N) durchschnittlichen Suchen übertreffen. Es wäre immer noch schwierig, Hash-Lookups zu übertreffen, aber dazu später mehr.

     C. Kurzgeschlossene Suche ist besser als BSTs oder sortierte Listensuchen, wenn die Anzahl der ausgeführten Suchen im Vergleich zur Listengröße relativ gering ist. In diesem Fall würden die anfänglichen Sortierkosten der ersten beiden Methoden (O(N log N)) überwiegen Suche Einsparungen. Da die Einsparungen von BST im Vergleich zur linearen Suche O(M * N) sind, wobei M die Anzahl der Suchen ist, folgt, dass die Anzahl der Suchen M kleiner als O (log N) sein muss, um die Einsparungen im Durchschnitt zu realisieren, aber im Fall des zweiten Rands mehr sein kann Die durchschnittlichen Scan-Kosten liegen aufgrund der Datenverteilung unter O(N).

   ---

4. Hash-Lookups

   Performance-Kosten:

   • O(N) + epsilon für die erste Hash-Erstellung (Es ist nicht streng O (N) für eine zufällige große sprechen Datensatz wegen möglicher Schlüsselkollision Ich kenne eno nicht ugh über Perls Hash-Implementierung, um dies zu verdeutlichen, außer dass es um irgendwelche Haschmaps geht.
   • O(1) im Durchschnitt zum Einfügen/Entfernen von Daten in der Liste einmal sortiert (+ gleichen Epsilon als anfängliche Hash-Erstellung aufgrund von Schlüsselkollisionen).
   • O(1) für jede Suche (plus gleichen Epsilon).
     
     

   Implementierung:

   my %lookup = map { $_ => 1 } @list; 
   my @lookup2{ @list } =(); # Alternative method of creating a hash 
   sub find { return exists $lookup{$_[0]; } 
   

   Vergleich:

   • Erstens die gleiche Logik gilt für das Vergleichen von Kurzschlusssuche mit Hash-Suchvorgängen wie bei BST vs Kurzschlusssuche. ZB sollten Sie fast immer hashmaps über lineare Suche verwenden, mit Ausnahme der gleichen zwei Rand Fälle (Datensatz ist so, dass durchschnittliche Liste Scan wird O(1) anstelle von O(N) und das Verhältnis von # der Suche auf die Datensatzgröße macht das Aggregat Suchkosten von weniger als O(N) werden für die Hash-Erstellung benötigt.

   • Zweitens Hashmaps im Durchschnitt offenbar viel schneller als BSTs oder Binär-Liste Suche. Der einzige mögliche Edge-Fall ist hier, dass Sie irgendwie in einen Datensatz stolpern, der es schafft, die Buckets zu überladen und die zusätzlichen "Epsilon" -Kosten so groß zu machen, dass er O(log N) unterfordert.

     Ich bezweifle stark, dass es sogar im entferntesten möglich ist, aber wieder, weiß nicht genug über Perls Implementierung von hashmaps, um zu beweisen, dass es nie selbst für den schlimmsten Datensatz passieren würde.

Answer 2

Wenn Sie nur eine Suche gehen zu tun, dann wird länger dauern, Sortierung als eine einzelne lineare Abtastung durchgeführt wird, so dass Sie auch können nur mit Schleifen über Stick das Array. Für ein kleines Array oder wenn Sie mehrere Übereinstimmungen haben könnten, sollten Sie sich auch die grep Funktion ansehen; Es ist ein wenig einfacher zu verwenden, aber es wird immer die gesamte Liste der möglichen Übereinstimmungen überprüfen, anstatt anzuhalten, wenn eine Übereinstimmung gefunden wird.

Wenn Sie viele Male suchen, die Werte des Arrays in einen Hash setzen und Hash-Suchen durchführen, werden Sie schneller als das Array durchsuchen, selbst wenn Sie es sortieren und eine binäre Suche durchführen (vorausgesetzt, Sie können sich das leisten Speicherkosten, aber Sie können fast sicher).