¿En qué n la búsqueda binaria se vuelve más rápida que la búsqueda lineal en una CPU moderna?

Question

Debido a las maravillas de la predicción de bifurcación, una búsqueda binaria puede ser más lenta que una búsqueda lineal a través de una matriz de enteros. En un procesador de escritorio típico, ¿qué tan grande tiene que llegar ese conjunto antes de que sea mejor utilizar una búsqueda binaria? Supongamos que la estructura se usará para muchas búsquedas.

Answer 1

He intentado un poco de benchmarking de C++ y estoy sorprendido: la búsqueda lineal parece prevalecer hasta varias docenas de artículos, y no he encontrado un caso en que la búsqueda binaria sea mejor para esos tamaños. ¿Quizás el STL de gcc no está bien ajustado? Pero entonces - ¿qué se puede utilizar para implementar cualquiera tipo de búsqueda -) Así que aquí está mi código, por lo que todo el mundo puede ver si he hecho algo tonto que puedan falsear la sincronización groseramente ...:?

#include <vector> 
#include <algorithm> 
#include <iostream> 
#include <stdlib.h> 

int data[] = {98, 50, 54, 43, 39, 91, 17, 85, 42, 84, 23, 7, 70, 72, 74, 65, 66, 47, 20, 27, 61, 62, 22, 75, 24, 6, 2, 68, 45, 77, 82, 29, 59, 97, 95, 94, 40, 80, 86, 9, 78, 69, 15, 51, 14, 36, 76, 18, 48, 73, 79, 25, 11, 38, 71, 1, 57, 3, 26, 37, 19, 67, 35, 87, 60, 34, 5, 88, 52, 96, 31, 30, 81, 4, 92, 21, 33, 44, 63, 83, 56, 0, 12, 8, 93, 49, 41, 58, 89, 10, 28, 55, 46, 13, 64, 53, 32, 16, 90 
      }; 

int tosearch[] = {53, 5, 40, 71, 37, 14, 52, 28, 25, 11, 23, 13, 70, 81, 77, 10, 17, 26, 56, 15, 94, 42, 18, 39, 50, 78, 93, 19, 87, 43, 63, 67, 79, 4, 64, 6, 38, 45, 91, 86, 20, 30, 58, 68, 33, 12, 97, 95, 9, 89, 32, 72, 74, 1, 2, 34, 62, 57, 29, 21, 49, 69, 0, 31, 3, 27, 60, 59, 24, 41, 80, 7, 51, 8, 47, 54, 90, 36, 76, 22, 44, 84, 48, 73, 65, 96, 83, 66, 61, 16, 88, 92, 98, 85, 75, 82, 55, 35, 46 
       }; 

bool binsearch(int i, std::vector<int>::const_iterator begin, 
         std::vector<int>::const_iterator end) { 
    return std::binary_search(begin, end, i); 
} 

bool linsearch(int i, std::vector<int>::const_iterator begin, 
         std::vector<int>::const_iterator end) { 
    return std::find(begin, end, i) != end; 
} 

int main(int argc, char *argv[]) 
{ 
    int n = 6; 
    if (argc < 2) { 
    std::cerr << "need at least 1 arg (l or b!)" << std::endl; 
    return 1; 
    } 
    char algo = argv[1][0]; 
    if (algo != 'b' && algo != 'l') { 
    std::cerr << "algo must be l or b, not '" << algo << "'" << std::endl; 
    return 1; 
    } 
    if (argc > 2) { 
    n = atoi(argv[2]); 
    } 
    std::vector<int> vv; 
    for (int i=0; i<n; ++i) { 
    if(data[i]==-1) break; 
    vv.push_back(data[i]); 
    } 
    if (algo=='b') { 
    std::sort(vv.begin(), vv.end()); 
    } 
    bool (*search)(int i, std::vector<int>::const_iterator begin, 
         std::vector<int>::const_iterator end); 
    if (algo=='b') search = binsearch; 
    else search = linsearch; 
    int nf = 0; 
    int ns = 0; 
    for(int k=0; k<10000; ++k) { 
    for (int j=0; tosearch[j] >= 0; ++j) { 
     ++ns; 
     if (search(tosearch[j], vv.begin(), vv.end())) 
     ++nf; 
    } 
    } 
    std::cout << nf <<'/'<< ns << std::endl; 

    return 0; 
} 

y mi un par de mis tiempos en un dúo de la base:

AmAir:stko aleax$ time ./a.out b 93 
1910000/2030000 

real 0m0.230s 
user 0m0.224s 
sys 0m0.005s 

AmAir:stko aleax$ time ./a.out l 93 
1910000/2030000 

real 0m0.169s 
user 0m0.164s 
sys 0m0.005s 

Son muy repetible, de todos modos ...

OP dice: Alex, editado su programa sólo tiene que rellenar la matriz con 1 .. n, no ejecuta std :: sort, y realiza aproximadamente 10 millones de búsquedas (división de enteros mod). La búsqueda binaria comienza a alejarse de la búsqueda lineal en n = 150 en un Pentium 4. Lo siento por los colores del gráfico.

binary vs linear search http://spreadsheets.google.com/pub?key=tzWXX9Qmmu3_COpTYkTqsOA&oid=1&output=image

Answer 2

Es posible que desee echar un vistazo a este article, que analiza la pregunta que ha hecho.

Answer 3

No muchas, pero es difícil de decir exactamente sin compararla.

Personalmente prefiero la búsqueda binaria, porque en dos años, cuando otra persona ha cuadruplicado el tamaño de su pequeña matriz, no ha perdido mucho rendimiento. A menos que supiera muy específicamente que es un cuello de botella en este momento y que necesitaba que fuera lo más rápido posible, por supuesto.

Habiendo dicho eso, recuerde que también hay tablas hash; podrías hacer una pregunta similar sobre ellos vs. búsqueda binaria.

Answer 4

No creo que la predicción de salto sea importante porque una búsqueda lineal también tiene ramas. Y que yo sepa, no hay SIMD que pueda hacer una búsqueda lineal por usted.

Dicho esto, un modelo útil sería suponer que cada paso de la búsqueda binaria tiene un costo multiplicador C.

log C n = n

Así para razonar sobre esto sin comparar realmente, harías una conjetura para C, y una vuelta n para el siguiente entero. Por ejemplo, si adivina C = 3, entonces sería más rápido usar la búsqueda binaria en n = 11.

Answer 5

He investigado esta cuestión en detalle una de resumir mis conclusiones in this blog post.