ricerca binaria in una matrice in Perl

Question

Ho una matrice di numeri esadecimali, e ho bisogno di andare oltre altri numeri e controllare se compaiono in quella matrice. In questo momento sto usando un ciclo foreach che ricopre l'intero array ogni volta. C'è un modo per renderlo più veloce ordinando l'array all'inizio, e quindi implementando la ricerca binaria su di esso.

Il codice in questo momento:

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

Esistono quattro strategie per eseguire una ricerca di massa efficiente in un set di dati in Perl.

L'analisi completa è descritta di seguito, ma in sintesi, le migliori prestazioni su set di dati casuali medi con un numero significativo di ricerche sono ovviamente offerte da ricerche hash, seguite da BST molto peggiore.

---

1. binario (half-intervallo) ricerca di un array.

   Questo è ovviamente un approccio algoritmico standard.

   costi

   Performance:

   • O(N * log N) per l'ordinamento iniziale.
   • O(N) in media per l'inserimento/rimozione dei dati nell'elenco una volta ordinati. Gli array Perl NON sono elenchi collegati, quindi non è un O(log N).
   • O(log N) per ogni ricerca.
     
     

   Attuazione: the algorithm è così semplice che fai da te è facile. Come al solito, i moduli CPAN esistono e probabilmente dovrebbero essere usati al posto del fai-da-te in ogni caso: Search::Binary.

   ---

2. Binary Search Trees (BST) Costi

   Performance:

   • O(N * log N) per l'ordinamento iniziale.
   • O(log N) in media per l'inserimento/rimozione dei dati nell'elenco una volta ordinati
   • O(log N) per ogni ricerca.

   
   

   Attuazione: esistono diversi gusti su CPAN: Tree::Binary::Search, Tree::Treap, Tree::RedBlack. Gli ultimi due have better average performance and smaller performance fluctuations, algorithmically.

   Confronto: Se i dati cambierà, è necessario utilizzare BST per evitare i costi di ri-ordinamento. Se i tuoi dati sono casuali e non cambiano mai una volta ordinati, puoi utilizzare la semplice ricerca binaria su BST ma i BST possono essere ottimizzati se l'ultima oncia di prestazioni è importante (BST può essere ottimizzato per una ricerca media più veloce della ricerca binaria di elenchi se conosci la tua ricerca costi basati sulla distribuzione dei dati - vedere Wiki's "Optimal binary search trees" section o se la distribuzione dei dati favorisce uno degli alberi speciali come Treap o Rosso/Nero).

   ---

3. abbreviata (corto circuito) le ricerche di scansione.

   Queste sono ricerche di scansione lineare su un elenco non ordinato che interrompe la ricerca una volta trovata l'elemento.

   Prestazioni: O(N) per ricerca di dati casuali, ma un più veloce O(N) (diciamo, N/2) di una ricerca full-lista come grep. Nessun costo aggiuntivo.

   Attuazione: Ci sono 3 modi per fare loro in Perl:

   • Smart match operatore (~~). Il problema è che è disponibile SOLO in Perl 5.10 e versioni successive.
   • Il proprio loop che fa next; una volta trovato.
   • List::MoreUtils subroutine del modulo first().

   Confronto:

   • In primo luogo, tra i 3 implementazioni di cui sopra, List::MoreUtils::first è più veloce del circuito fai da te perché è implementata in XS; quindi dovrebbe essere usato nelle versioni Perl prima delle 5.10. La partita intelligente è probabilmente altrettanto veloce, anche se vorrei confrontare i due prima di scegliere uno o l'altro in Perl 5.10+.

   • In secondo luogo, il confronto di ricerca in corto circuito ad altri metodi, ci sono solo 3 casi limite in cui deve essere utilizzato:

     A. vincoli di memoria. Sia la ricerca nella lista ordinata, le ricerche BST e hash hanno un'impronta di memoria almeno pari a 2*N. Se si affronta un vincolo di memoria (data la dimensione dell'elenco) abbastanza grave da rendere la memoria vs 2*N una barriera di costo non negoziabile, si utilizza la ricerca in corto circuito e si paga la sanzione delle prestazioni in tempo. Ciò è particolarmente vero quando si elabora un set di dati di grandi dimensioni in batch/riga per riga, in modo da evitare di memorizzare l'intera cosa in memoria, in primo luogo.

     B. Se i dati vengono distribuiti e preordinati in modo che una maggioranza VAST delle ricerche trovi la loro preda all'inizio dell'elenco. Se questo è il caso, potrebbe superare i metodi più elaborati come la BST della ricerca binaria, nonostante le ricerche medie O (log N) ovviamente più veloci. Sarebbe comunque difficile sovraperformare le ricerche di hash, ma ne parleremo più avanti.

     C. La ricerca in corto circuito è superiore ai BST o alle ricerche di elenchi ordinati se il numero di ricerche eseguite è piuttosto piccolo rispetto alla dimensione dell'elenco, nel qual caso il costo iniziale di smistamento dei primi 2 metodi (O(N log N)) supererebbe cerca risparmi. Poiché il risparmio di BST rispetto alla ricerca lineare è O(M * N) dove M è # di ricerche, ne consegue che # di ricerche M deve essere minore di O (log N) per realizzare i risparmi in media, ma potrebbe essere maggiore nel secondo caso limite dove il costo medio della scansione è inferiore a O(N) a causa della distribuzione dei dati.

   ---

4. ricerche Hash

   Costi Prestazioni:

   • O(N) + epsilon per la creazione iniziale di hash (non è strettamente O parlando (N) per una grande casuale set di dati, a causa di possibili collisioni tra chiavi. Non so eno Per quanto riguarda l'implementazione dell'hash di Perl per chiarire questo diverso da affermare che può essere una preoccupazione per qualsiasi hashmap.
   • O(1) in media per l'inserimento/rimozione di dati nell'elenco una volta ordinati (+ lo stesso epsilon della creazione iniziale di hash a causa di collisioni di chiavi).
   • O(1) per ogni ricerca (più lo stesso epsilon).
     
     

   Attuazione:

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

   Confronto:

   • In primo luogo, la stessa logica si applica al confronto della ricerca in corto circuito con le ricerche hash come con la ricerca BST vs cortocircuitata. Ad esempio, dovresti SEMPRE usare sempre le hashmap sulla ricerca lineare, ad eccezione degli stessi due casi limite (il set di dati è tale che la scansione dell'elenco medio diventa O(1) anziché O(N) e il rapporto tra # di ricerche e la dimensione dell'insieme di dati rende l'aggregato costo delle ricerche inferiori a O(N) necessarie per la creazione di hash).

   • In secondo luogo, HashMaps in media si ovviamente molto più velocemente di quanto BST o lista binario di ricerca. L'unico caso limite qui è che in qualche modo inciampi in un set di dati che riesce a sovraccaricare i bucket e trasformare quel costo extra di "epsilon" in un peso abbastanza grande da causare un sottoperformance O(log N).

     Dubito fortemente che sia anche solo lontanamente possibile, ma ancora una volta, non ne so abbastanza sull'implementazione delle hashmap di Perl per dimostrare che non sarebbe mai accaduto neanche per il peggiore data set.

Answer 2

Se hai intenzione di fare una ricerca, quindi l'ordinamento avrà più di eseguire una singola scansione lineare, quindi si può anche semplicemente attaccare con loop su l'array. Per un piccolo array, o se si possono avere più corrispondenze, si potrebbe anche voler guardare la funzione grep; è un po 'più facile da usare, ma controllerà sempre l'intero elenco di corrispondenze candidate invece di fermarsi quando viene trovata una corrispondenza.

Se stai cercando più volte, inserendo i valori dell'array in un hash e eseguendo ricerche di hash sarà più veloce della ricerca nell'array, anche se lo si ordina e si effettua una ricerca binaria (presupponendo che si possa permettere costo della memoria, ma quasi certamente puoi).