algorithm - ordenamiento - ¿En qué n la búsqueda binaria se vuelve más rápida que la búsqueda lineal en una CPU moderna?
busqueda binaria recursiva (5)
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.
Es posible que desee echar un vistazo a este artículo , que analiza la pregunta que hizo.
No creo que la predicción de ramas sea importante porque una búsqueda lineal también tiene ramificaciones. Y que yo sepa, no hay SIMD que pueda hacer una búsqueda lineal por usted.
Habiendo dicho eso, un modelo útil sería suponer que cada paso de la búsqueda binaria tiene un costo multiplicador C.
C log 2 n = n
Entonces, para razonar acerca de esto sin compararlo realmente, harías una conjetura para C, y alrededor de 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.
No muchos, pero es difícil decirlo exactamente sin compararlo.
Personalmente, tendería a preferir 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.
Una vez dicho esto, recuerde que también hay tablas hash; podrías hacer una pregunta similar sobre ellos vs. búsqueda binaria.
Intenté una pequeña evaluación comparativa de C ++ y estoy sorprendido: la búsqueda lineal parece prevalecer en varias docenas de artículos, y no encontré ningún caso en el que la búsqueda binaria sea mejor para esos tamaños. ¿Quizás el STL de gcc no está bien ajustado? Pero entonces, ¿qué usarías para implementar cualquiera de los dos tipos de búsqueda? -) Así que aquí está mi código, para que todos puedan ver si he hecho algo tonto que distorsionaría el tiempo ...:
#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 un par de mis tiempos en un dúo central:
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 bastante repetibles, de todos modos ...
OP dice: Alex, he editado tu programa para que simplemente llene la matriz con 1..n, no ejecutes std :: sort y hagas 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.
Investigué esta pregunta en detalle y resumí mis hallazgos en esta publicación del blog .