Wyszukiwanie binarne w tablicy w Perlu

Question

Mam tablicę liczb szesnastkowych i muszę przejrzeć inne liczby i sprawdzić, czy pojawiają się w tej tablicy. Teraz używam pętli foreach, która za każdym razem przechodzi przez całą tablicę. Czy istnieje sposób, aby przyspieszyć działanie, najpierw sortując tablicę, a następnie wdrażając wyszukiwanie binarne.

Kod w tej chwili:

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

Istnieją cztery strategie umożliwiające wydajne wyszukiwanie zbiorcze w zbiorze danych w Perlu.

Pełna analiza została przedstawiona poniżej, ale podsumowując, najlepsze wyniki na przeciętnym losowym zestawie danych ze znaczącym liczbą wyszukiwań są oczywiście oferowane przez wyszukiwanie hash, a następnie znacznie gorsze BST.

---

1. binarny (pół odstępu) przeszukanie tablicy.

   Jest to oczywiście standardowe podejście algorytmiczne.

   Koszty

   wydajności:

   • O(N * log N) do wstępnego sortowania.
   • O(N) średnio za wstawienie/usunięcie danych z listy po posortowaniu. Tablice Perla NIE są połączonymi listami, więc nie jest to O(log N).
   • O(log N) dla każdego wyszukiwania.
     
     

   Realizacja: the algorithm jest tak prosty, że DIY jest łatwe. Jak zwykle, istnieją moduły CPAN, które powinny i tak zostać użyte zamiast DIY: Search::Binary.

   ---

2. Binary Search Trees (BSTS) Koszty

   Wydajność:

   • O(N * log N) do wstępnego sortowania.
   • O(log N) średnio za wstawienie/usunięcie danych z listy po posortowaniu
   • O(log N) dla każdego wyszukiwania.

   
   

   Realizacja: kilka smaków istnieje na CPAN: Tree::Binary::Search, Tree::Treap, Tree::RedBlack. Te dwa ostatnie have better average performance and smaller performance fluctuations, algorithmically.

   Porównanie: Jeśli dane będą zmiany, należy użyć BST aby uniknąć kosztów ponownego sortowania. Jeśli twoje dane są losowe i nigdy nie zmieniają się po posortowaniu, możesz użyć prostej przeszukiwania binarnego przez BST, ale BST można lepiej dostroić, jeśli liczy się każda ostatnia uncja wydajności (BST może być zoptymalizowany do szybszego wyszukiwania przeciętnego niż wyszukiwanie binarne listy, jeśli znasz swoje wyszukiwanie koszty oparte na dystrybucji danych - patrz Wiki's "Optimal binary search trees" section lub jeśli twoja dystrybucja danych sprzyja jednemu ze specjalnych drzew takich jak Treap lub Czerwony/Czarny).

   ---

3. skrócone (zwarte) wyszukiwań skanowania.

   Są to wyszukiwania liniowe na liście nie posortowanej, w której wyszukiwanie STOP następuje po znalezieniu przedmiotu.

   Wydajność: O(N) na poszukiwaniu przypadkowych danych, ale szybciej O(N) (powiedzmy, N/2) niż poszukiwanie pełnej listy jak grep. Bez dodatkowych kosztów.

   Realizacja: Istnieją 3 sposoby, aby zrobić je w Perlu:

   • Smart match operator (~~). Problem polega na tym, że jest on dostępny TYLKO w Perlu 5.10 i powyżej.
   • Własna pętla, która znajduje się po znalezieniu next;.
   • moduł podprogramu first().

   Porównanie:

   • pierwsze, między 3 implementacji powyższych List::MoreUtils::first jest szybszy niż DIY pętli, ponieważ jest realizowany w XS; więc powinno być używane w wersjach Perla przed 5.10. Inteligentne dopasowanie jest prawdopodobnie równie szybkie, ale chciałbym porównać te dwa, zanim wybierzesz jeden lub drugi w Perlu 5.10+.

   • drugie, porównując zwarcie wyszukiwanie do innych metod, są tylko 3 przypadki brzegowe, gdzie powinien być stosowany:

     A. Ograniczenia pamięci. Zarówno posortowane wyszukiwanie list, wyszukiwanie BST, jak i hash mają rozmiar pamięci co najmniej 2*N. Jeśli napotkasz ograniczenie pamięci (biorąc pod uwagę wielkość listy) na tyle poważne, że pamięć N vs 2*N stanie się niezbywalną barierą kosztową, wówczas użyjesz zwarcia w wyszukiwaniu i zapłacisz karę za wyniki w czasie. Jest to szczególnie ważne, gdy przetwarzasz duży zestaw danych w partiach/liniach po linii, aby uniknąć przechowywania całego elementu w pamięci w pierwszej kolejności.

     B. Jeśli Twoje dane są rozprowadzane i wstępnie sortowane w taki sposób, że większość wyszukiwań VAST znajdzie ich kamieniołom na samym początku listy. Jeśli tak jest, MOŻE osiągnąć lepsze wyniki niż metody hodowcy, takie jak BST wyszukiwania binarnego, mimo że są to oczywiście szybsze średnie wyszukiwania O (log N). Wciąż trudno byłoby prześcignąć wyniki wyszukiwania hash, ale o tym później.

     C. Zwarte wyszukiwanie jest lepsze niż wyszukiwanie BST lub posortowane wyszukiwanie list, jeśli liczba wyszukiwań jest dość mała w porównaniu do rozmiaru listy, w którym to przypadku początkowy koszt sortowania pierwszych 2 metod (O(N log N)) byłby większy niż oszczędności w wyszukiwaniu. Ponieważ oszczędności BST vs. wyszukiwanie liniowe wynoszą O(M * N), gdzie M jest liczbą wyszukiwań, wynika, że ​​liczba wyszukiwań M musi być mniejsza niż O (log N), aby uzyskać średnie oszczędności, ale może być większa w przypadku drugiej krawędzi gdzie średni koszt skanowania jest mniejszy niż O(N) z powodu dystrybucji danych.

   ---

4. Hash wyszukiwań

   Koszty wydajności:

   • O(N) + epsilon do wstępnego utworzenia skrótu (nie jest ściśle rzecz biorąc O (N) za losową duża zestaw danych, z powodu możliwej kolizji kluczy. Nie wiem eno w sprawie haszowania Perla, aby wyjaśnić to inaczej niż stwierdzić, że może to być problemem dla każdej hashmap.
   • O(1) średnio za wstawienie/usunięcie danych na liście po posortowaniu (+ ten sam epsilon co początkowe tworzenie skrótu z powodu kolizji kluczy).
   • O(1) dla każdego wyszukiwania (plus ten sam epsilon).
     
     

   Realizacja:

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

   Porównanie:

   • pierwsze, ta sama logika odnosi się do porównywania zwartego wyszukiwania z hashami, tak jak w przypadku BST w porównaniu z wyszukiwaniem zwartym. Np. Powinieneś PRAWIE zawsze używać hashmapów zamiast przeszukiwania liniowego, z wyjątkiem tych samych przypadków krawędzi (zestaw danych jest taki, że średni skan listy staje się O(1) zamiast O(N), a stosunek liczby wyszukiwań do rozmiaru zestawu danych powoduje, że agregat koszt wyszukiwania mniejszy niż O(N) potrzebny do utworzenia skrótu).

   • drugie, hashmaps średnio są oczywiście znacznie szybciej niż BSTS lub listy binarnego wyszukiwania. Jedynym możliwym przypadkiem na krawędzi jest to, że w jakiś sposób wpadłeś w zestaw danych, który jest w stanie przeciążyć wiadra i przekształcić ten dodatkowy koszt "epsilon" w wystarczająco dużą wagę, która zaczyna się od zbyt niskiej wydajności O(log N).

     Jestem głęboko przekonany, że jest to nawet możliwe, ale znowu, nie wiem wystarczająco dużo na temat wdrażania impulsu Perla, aby udowodnić, że nigdy nie zdarzy się to w przypadku nawet najgorszego zestawu danych.

Answer 2

Jeśli dopiero zamierzasz zrobić jedno kliknięcie, a następnie sortowania będzie trwać dłużej niż wykonując pojedynczy skan liniowy, więc równie dobrze może po prostu trzymać się z zapętlenie nad tablica. Jeśli masz małą tablicę lub możesz mieć wiele dopasowań, możesz również spojrzeć na funkcję grep; jest nieco łatwiejszy w użyciu, ale zawsze sprawdza całą listę meczów kandydujących, zamiast zatrzymywać się, gdy zostanie znaleziony mecz.

Jeśli zamierzasz przeszukiwać wiele razy, umieszczając wartości tablicy w haszu, a wyszukiwanie hash będzie szybsze niż przeszukiwanie tablicy, nawet jeśli ją posortujesz i wykonasz wyszukiwanie binarne (zakładając, że możesz pozwolić sobie na koszt pamięci, ale prawie na pewno można).