print - búsqueda binaria en una matriz en Perl

print array perl

Question

Tengo una serie de números hexadecimales, y necesito revisar otros números y verificar si aparecen en esa matriz. En este momento estoy usando un bucle 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 este 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

Hay cuatro estrategias para hacer una búsqueda masiva eficiente 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 significativo de búsquedas, por supuesto, se ofrece mediante búsquedas hash, seguidas de BST mucho peor.

1. Búsqueda binaria (medio intervalo) de una matriz.

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

   Costos de rendimiento:

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

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

2. Árboles de búsqueda binaria (BST)

   Costos de rendimiento:

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

   
   

   Implementación : existen varios sabores en CPAN: Tree::Binary::Search , Tree::Treap , Tree::RedBlack . Los dos últimos tienen un mejor rendimiento promedio y menores fluctuaciones de rendimiento, algorítmicamente .

   Comparación : si los datos cambiarán, debe usar BST para evitar volver a ordenar los costos. 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 costos basados ​​en la distribución de datos: consulte la sección "Árboles óptimos de búsqueda binaria" de Wiki o si su distribución de datos favorece uno de los árboles especiales como Treap o Rojo / Negro).

3. Búsquedas de exploración abreviadas (en cortocircuito).

   Estas son búsquedas de escaneo lineal en la lista no ordenada que detiene la búsqueda una vez que se encuentra el elemento.

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

   Implementación : hay 3 formas de hacerlo en Perl:

   • Operador de coincidencia inteligente ( ~~ ). El problema es que SOLAMENTE está disponible en Perl 5.10 y superior.
   • Tu propio bucle que next; una vez encontrado.
   • List::MoreUtils la first() subrutina del módulo List::MoreUtils .

   Comparación :

   • Primero, entre las 3 implementaciones anteriores, List::MoreUtils::first es más rápido que el bucle DIY 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, al comparar la búsqueda en cortocircuito con otros métodos, solo hay 3 casos de borde donde debería usarse:

     A. Limitaciones de memoria. Tanto la búsqueda de lista ordenada, BST y búsquedas hash tienen una huella de 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 la memoria N vs 2*N convierta en una barrera de costos no negociables, entonces usa 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 clasifican 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 de listas si el número de búsquedas realizadas es bastante pequeño en comparación con el tamaño de la lista, en cuyo caso el costo de clasificación inicial de los primeros 2 métodos ( O(N log N) ) superaría los ahorros de búsqueda. Como 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 el número de búsquedas M debe ser menor que O (log N) para obtener los ahorros en promedio, pero puede ser mayor en el segundo caso de borde donde el costo promedio de escaneo es menor que O(N) debido a la distribución de datos.

4. Búsquedas Hash

   Costos de rendimiento:

   • O(N) + epsilon para la creación de hash inicial (No es estrictamente hablando O (N) para un conjunto de datos aleatorio grande, debido a una posible colisión de clave. No sé lo suficiente acerca de la implementación de hash de Perl para aclarar esto aparte de afirmar que PUEDE ser una preocupación para cualquier hashmaps.
   • O(1) en promedio para insertar / eliminar datos en la lista una vez ordenados (más el mismo épsilon que la creación de hash inicial debido a colisiones de teclas).
   • O(1) para cada búsqueda (más el mismo epsilon).
     
     

   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, se aplica la misma lógica para comparar búsquedas en cortocircuito con búsquedas de hash que con BST versus búsqueda en cortocircuito. Por ejemplo, casi siempre debes usar hashmaps sobre búsqueda lineal, con la excepción de los mismos dos casos extremos (el conjunto de datos es tal que el escaneo promedio de listas se convierte en O(1) lugar de O(N) y la razón de # de búsquedas en el tamaño del conjunto de datos hace que el costo agregado de búsquedas sea menor que O(N) necesario para la creación de hash).

   • En segundo lugar, los hashmaps ON AVERAGE son, obviamente, mucho más rápidos que los BST o la búsqueda de listas binarias . 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 extra "épsilon" en un peso lo suficientemente grande como para comenzar con un rendimiento bajo O(log N) .

     Dudo mucho que sea remotamente posible, pero una vez más, no sé lo suficiente sobre la implementación de los hashmaps de Perl para demostrar que nunca sucederá, incluso para el peor conjunto de datos.

Answer 2

Si solo va a hacer una búsqueda, entonces la clasificación tomará más tiempo que realizar un único escaneo lineal, por lo que también puede simplemente seguir con el bucle sobre la matriz. Para una matriz pequeña, o si puede tener varias coincidencias, también puede consultar 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 clasificas y haces una búsqueda binaria (suponiendo que puedas pagar el costo de la memoria, pero casi con seguridad puedes).