búsqueda binaria en una matriz en Perl

Question

Tengo una matriz de números hexadecimales, y necesito revisar otros números y comprobar si aparecen en esa matriz. En este momento estoy usando un loop foreach que recorre toda la matriz cada vez. ¿Hay alguna manera de hacerlo más rápido al ordenar la matriz al principio y luego implementar la búsqueda binaria en ella?

El código en la actualidad

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

Existen cuatro estrategias para realizar búsquedas masivas eficientes en un conjunto de datos en Perl.

El análisis completo se detalla a continuación, pero en resumen, el mejor rendimiento en el conjunto de datos aleatorios promedio con un número importante de búsquedas se ofrece mediante búsquedas hash, seguido de BST mucho peor.

---

1. Binario (media de intervalo) búsqueda de una matriz.

   Este es obviamente un enfoque algorítmico estándar.

   Costos

   Rendimiento:

   • O(N * log N) para la clasificación inicial.
   • O(N) de promedio para insertar/eliminar datos en la lista una vez ordenados. Los arrays Perl NO son listas enlazadas, por lo que no es un O(log N).
   • O(log N) para cada búsqueda.
     
     

   Implementación: the algorithm es tan simple que es fácil de bricolaje. Como de costumbre, los módulos de CPAN existen y probablemente se deberían usar en lugar de bricolaje de todos modos: Search::Binary.

   ---

2. Binary Search Trees (BSTs) Costos

   Rendimiento:

   • O(N * log N) para la clasificación inicial.
   • O(log N) de promedio para insertar/eliminar datos en la lista una vez que se ordenó
   • O(log N) para cada búsqueda.

   
   

   Implementación: existen varios sabores en CPAN: Tree::Binary::Search, Tree::Treap, Tree::RedBlack. Los últimos dos have better average performance and smaller performance fluctuations, algorithmically.

   Comparación: Si los datos van a cambiar, debe utilizar BST para evitar los costos de re-ordenar. Si sus datos son aleatorios y nunca cambian una vez ordenados, puede usar la búsqueda binaria simple sobre BST, pero los BST pueden ajustarse mejor si hasta la última onza de rendimiento importa (BST puede optimizarse para una búsqueda promedio más rápida que la búsqueda binaria en la lista si conoce su búsqueda los costos se basan en la distribución de datos; consulte Wiki's "Optimal binary search trees" section o si su distribución de datos favorece uno de los árboles especiales como Treap o Rojo/Negro).

   ---

3. Abreviada (cortocircuitado) búsquedas de exploración.

   Se trata de búsquedas de escaneo lineal en la lista no ordenada que detienen la búsqueda una vez que se encuentra el elemento.

   Rendimiento: O(N) por búsqueda de datos aleatorios, pero un rápido O(N) (por ejemplo, N/2) de una búsqueda de la lista completa como grep. Sin costos adicionales

   Implementación: Existen 3 maneras de hacerlo en Perl:

   • Smart match operador (~~). El problema es que SOLAMENTE está disponible en Perl 5.10 y superior.
   • Su propio bucle que hace next; una vez encontrado.
   • List::MoreUtils módulo first() subrutina.

   Comparación:

   • En primer lugar, entre las 3 implementaciones anteriores, List::MoreUtils::first es más rápido que el bucle de bricolaje porque está implementado en XS; por lo tanto, debe usarse en versiones de Perl antes de 5.10. La coincidencia inteligente es probablemente igual de rápida, aunque compararía las dos antes de elegir una u otra en Perl 5.10+.

   • En segundo lugar, la comparación de la búsqueda en cortocircuito con otros métodos, sólo hay 3 casos extremos donde debe ser usado cuando:

     A. restricciones de memoria. Las búsquedas de listas ordenadas, BST y hash tienen una memoria de al menos 2*N. Si enfrenta una restricción de memoria (dado el tamaño de su lista) lo suficientemente severa como para que N frente a 2*N la memoria se convierta en una barrera de costos no negociables, entonces utiliza la búsqueda en cortocircuito y paga la penalización de rendimiento a tiempo. Esto es especialmente cierto cuando procesa un gran conjunto de datos en lotes/línea por línea, para evitar almacenar todo en la memoria en primer lugar.

     B. Si sus datos se distribuyen y ordenan previamente de tal manera que una mayoría VAST de las búsquedas encontrarían su cantera al principio de la lista. Si ese es el caso, PUEDE superar a los métodos más sofisticados como BST de búsqueda binaria a pesar de sus búsquedas promedio O (log N) obviamente más rápidas. Todavía sería difícil superar las búsquedas de hash, pero más sobre eso más adelante.

     C. La búsqueda en cortocircuito es superior a BST o búsquedas ordenadas si el número de búsquedas realizadas es bastante pequeño comparado con el tamaño de lista, en cuyo caso el costo inicial de clasificación de los primeros 2 métodos (O(N log N)) buscar ahorros Dado que los ahorros de BST frente a la búsqueda lineal son O(M * N) donde M es el número de búsquedas, se deduce que # de búsquedas M debe ser menor que O (log N) para realizar los ahorros en promedio, pero puede ser mayor en el segundo caso marginal donde el costo promedio de escaneo es menor que O(N) debido a la distribución de datos.

   ---

4. búsquedas de hash

   Costos de rendimiento:

   • O(N) + epsilon para la creación inicial de hash (no es estrictamente hablando O (N) para un gran azar conjunto de datos, debido a una posible colisión clave. No sé eno ugh sobre la implementación de hash de Perl para aclarar esto, aparte de afirmar que puede ser una preocupación para cualquier hashp.
   • O(1) promedio para insertar/eliminar datos en la lista una vez ordenados (más el mismo épsilon que la creación del hash inicial debido a colisiones de teclas).
   • O(1) para cada búsqueda (más el mismo épsilon).
     
     

   Implementación:

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

   Comparación:

   • En primer lugar, la misma lógica se aplica a la comparación de búsqueda en cortocircuito con búsquedas de hash como con BST vs búsqueda en cortocircuito. Por ejemplo, casi siempre debe usar hashmaps sobre la búsqueda lineal, con la excepción de los mismos dos casos extremos (el conjunto de datos es tal que el escaneo de lista promedio se convierte en O(1) en lugar de O(N) y la proporción de búsquedas del tamaño del conjunto de datos hace que el agregado costo de búsquedas menor que O(N) necesario para la creación de hash).

   • En segundo lugar, HashMaps en promedio son, evidentemente, mucho más rápido de BSTs o lista de búsqueda binaria. El único caso de borde posible aquí es que de alguna manera se tropieza con un conjunto de datos que logra sobrecargar los cubos y convertir ese costo adicional "épsilon" en un peso lo suficientemente grande como para comenzar a tener un rendimiento bajo O(log N).

     Tengo una gran duda de que sea remotamente posible, pero una vez más, no sé lo suficiente acerca de la implementación de hasmaps de Perl para demostrar que nunca sucederá, incluso para el peor conjunto de datos.

Answer 2

Si sólo vamos a hacer una búsqueda, a continuación, la clasificación va a llevar más tiempo que la realización de una sola exploración lineal, por lo que es posible que así sólo se adhieren con más de un bucle la matriz Para una matriz pequeña, o si puede tener varias coincidencias, es posible que también desee examinar la función grep; es un poco más fácil de usar, pero siempre revisará toda la lista de coincidencias candidatas en lugar de detenerse cuando se encuentre una coincidencia.

Si vas a buscar muchas veces, poner los valores de la matriz en un hash y hacer búsquedas de hash será más rápido que buscar la matriz, incluso si la ordenas y haces una búsqueda binaria (suponiendo que puedas pagar la costo de memoria, pero casi con seguridad puedes).