recursiva - ¿Qué tan rápido puedes hacer una búsqueda lineal?

metodos de busqueda java (20)

Estoy buscando optimizar esta búsqueda lineal:

static int linear (const int *arr, int n, int key) { int i = 0; while (i < n) { if (arr [i] >= key) break; ++i; } return i; }

La matriz se ordena y se supone que la función devuelve el índice del primer elemento que es mayor o igual que la clave. No son grandes (menos de 200 elementos) y se prepararán una vez para una gran cantidad de búsquedas. Los elementos de la matriz después de la n-ésima pueden, si es necesario, inicializarse en algo apropiado, si eso acelera la búsqueda.

No, la búsqueda binaria no está permitida, solo la búsqueda lineal.

Editar : Todo mi conocimiento sobre este tema se resume ahora en esta publicación de blog .

Dígale a su jefe que puede hacerlo un 50% más rápido, pero le tomará 6 meses y algo de dinero.
Espera seis meses.
Compre nuevo hardware.

Bueno, tiene tanto sentido como una búsqueda lineal a través de una matriz ordenada.

(Más en serio, ¿puedes darnos algunas pistas sobre por qué no hay búsqueda binaria?)

Dado que puede poner valores conocidos después de la última entrada válida, agregue un elemento extra n + 1 = max para asegurarse de que el bucle no vaya más allá del final de la matriz sin tener que probar i <n.

static int linear (const int *arr, int n, int key) { assert(arr[n] >= key); int i = 0; while (arr[i] < key) { ++i; } return i; }

También podría intentar desenrollar el bucle, con el mismo valor centinela:

static int linear (const int *arr, int n, int key) { assert(arr[n] >= key); int i = 0; while (true) { if (arr [i++] >= key) break; if (arr [i++] >= key) break; if (arr [i++] >= key) break; if (arr [i++] >= key) break; } return --i; }

En primer lugar, cualquier solución rápida debe usar vectorización para comparar muchos elementos a la vez.

Sin embargo, todas las implementaciones vectorizadas publicadas hasta el momento adolecen de un problema común: tienen ramas. Como resultado, tienen que introducir el procesamiento en bloque de la matriz (para reducir la sobrecarga de la bifurcación), lo que conduce a un bajo rendimiento para matrices pequeñas. Para matrices grandes, la búsqueda lineal es peor que una búsqueda binaria bien optimizada, por lo que no tiene sentido optimizarla.

Sin embargo, la búsqueda lineal se puede implementar sin ramas en absoluto. La idea es muy simple: el índice que desea es precisamente la cantidad de elementos en la matriz que son menores que la clave que busca. Entonces puede comparar cada elemento de la matriz con el valor clave y sumar todas las banderas:

static int linear_stgatilov_scalar (const int *arr, int n, int key) { int cnt = 0; for (int i = 0; i < n; i++) cnt += (arr[i] < key); return cnt; }

Una cosa divertida acerca de esta solución es que devolvería la misma respuesta incluso si baraja la matriz =). Aunque esta solución parece ser bastante lenta, puede vectorizarse con elegancia. La implementación que se proporciona a continuación requiere que la matriz esté alineada con 16 bytes. Además, la matriz debe rellenarse con elementos INT_MAX porque consume 16 elementos a la vez.

static int linear_stgatilov_vec (const int *arr, int n, int key) { assert(size_t(arr) % 16 == 0); __m128i vkey = _mm_set1_epi32(key); __m128i cnt = _mm_setzero_si128(); for (int i = 0; i < n; i += 16) { __m128i mask0 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+0]), vkey); __m128i mask1 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+4]), vkey); __m128i mask2 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+8]), vkey); __m128i mask3 = _mm_cmplt_epi32(_mm_load_si128((__m128i *)&arr[i+12]), vkey); __m128i sum = _mm_add_epi32(_mm_add_epi32(mask0, mask1), _mm_add_epi32(mask2, mask3)); cnt = _mm_sub_epi32(cnt, sum); } cnt = _mm_hadd_epi32(cnt, cnt); cnt = _mm_hadd_epi32(cnt, cnt); // int ans = _mm_extract_epi32(cnt, 0); //SSE4.1 int ans = _mm_extract_epi16(cnt, 0); //correct only for n < 32K return ans; }

La reducción final de un único registro SSE2 se puede implementar con SSE2 solo si es necesario, no debería afectar realmente el rendimiento general.

Lo he probado con el compilador de Visual C ++ 2013 x64 en Intel Core 2 Duo E4700 (bastante viejo, sí). La matriz de tamaño 197 se genera con elementos proporcionados por rand (). El código completo con todas las pruebas está here . Este es el momento de realizar búsquedas de 32M:

[OP] Time = 3.155 (-896368640) //the original OP''s code [Paul R] Time = 2.933 (-896368640) [stgatilov] Time = 1.139 (-896368640) //the code suggested

El código original de OP procesa 10.6 millones de matriz por segundo (2.1 billones de elementos por segundo). El código sugerido procesa 29.5 millones de matrices por segundo (5.8 billones de elementos por segundo). Además, el código sugerido funciona bien para matrices más pequeñas: incluso para matrices de 15 elementos, todavía es casi tres veces más rápido que el código original de OP.

Aquí está el ensamblaje generado:

$LL56@main: movdqa xmm2, xmm4 movdqa xmm0, xmm4 movdqa xmm1, xmm4 lea rcx, QWORD PTR [rcx+64] pcmpgtd xmm0, XMMWORD PTR [rcx-80] pcmpgtd xmm2, XMMWORD PTR [rcx-96] pcmpgtd xmm1, XMMWORD PTR [rcx-48] paddd xmm2, xmm0 movdqa xmm0, xmm4 pcmpgtd xmm0, XMMWORD PTR [rcx-64] paddd xmm1, xmm0 paddd xmm2, xmm1 psubd xmm3, xmm2 dec r8 jne SHORT $LL56@main $LN54@main: phaddd xmm3, xmm3 inc rdx phaddd xmm3, xmm3 pextrw eax, xmm3, 0

Finalmente, me gustaría señalar que una búsqueda binaria bien optimizada puede hacerse más rápida al cambiar a la búsqueda lineal vectorizada descrita tan pronto como el intervalo se vuelve pequeño.

ACTUALIZACIÓN: se puede encontrar más información en la publicación de mi blog sobre el tema.

En realidad, la respuesta a esta pregunta depende en un 100% de la plataforma para la que está escribiendo el código. Por ejemplo:

Evitar la rama condicional requerida para enlazar los datos dará una ligera mejora en el rendimiento.
Una vez que la CPU comienza a ser más rápida que la RAM, no importa qué tan eficiente sea el bucle (a menos que sea un bucle realmente malo), se estancará debido a que tendrá que esperar a que los datos ingresen desde la RAM. SIMD realmente no ayuda ya que la ventaja de las pruebas paralelas aún se ve superada por tener que esperar a que lleguen más datos. SIMD realmente tiene éxito cuando tienes un CPU limitado.

Esta respuesta es un poco más oscura que la otra, así que la estoy publicando por separado. Se basa en el hecho de que C garantiza un resultado booleano falso = 0 y verdadero = 1. X86 puede producir booleanos sin ramificación, por lo que podría ser más rápido, pero no lo he probado. Las micro-optimizaciones como estas siempre dependerán en gran medida de su procesador y compilador.

Como antes, la persona que llama es responsable de poner un valor centinela al final de la matriz para garantizar que el bucle finalice.

La determinación de la cantidad óptima de desenrollado requiere cierta experimentación. Desea encontrar el punto de rendimientos decrecientes (o negativos). Voy a tomar un SWAG e intentaré 8 esta vez.

static int linear (const int *arr, int n, int key) { assert(arr[n] >= key); int i = 0; while (arr[i] < key) { i += (arr[i] < key); i += (arr[i] < key); i += (arr[i] < key); i += (arr[i] < key); i += (arr[i] < key); i += (arr[i] < key); i += (arr[i] < key); i += (arr[i] < key); } return i; }

Editar: Como señala Mark, esta función introduce una dependencia en cada línea en la línea anterior, lo que limita la capacidad de la canalización del procesador para ejecutar operaciones en paralelo. Intentemos hacer una pequeña modificación en la función para eliminar la dependencia. Ahora la función realmente requiere 8 elementos centinelas al final.

static int linear (const int *arr, int n, int key) { assert(arr[n] >= key); assert(arr[n+7] >= key); int i = 0; while (arr[i] < key) { int j = i; i += (arr[j] < key); i += (arr[j+1] < key); i += (arr[j+2] < key); i += (arr[j+3] < key); i += (arr[j+4] < key); i += (arr[j+5] < key); i += (arr[j+6] < key); i += (arr[j+7] < key); } return i; }

Ha recibido muchas sugerencias de mejoras, pero necesita medir cada optimización para ver cuál es la mejor dada a su hardware y compilador .

Como un ejemplo de esto, en la primera versión de esta respuesta, supuse que por 100-200 elementos de la matriz, la sobrecarga ligeramente más alta de la búsqueda binaria debería pagarse fácilmente con muchas menos sondas en la matriz. Sin embargo, en los comentarios a continuación, Mark Probst informa que ve una búsqueda lineal de hasta 500 entradas en su hardware. Esto refuerza la necesidad de medir cuando se busca el mejor rendimiento.

Nota : Editado siguiendo los comentarios de Mark a continuación sobre sus medidas de búsqueda lineal frente a binaria para N. razonablemente pequeña.

Hasta ahora ha recibido múltiples consejos, la mayoría de los cuales indican que la búsqueda lineal no tiene sentido en los datos ordenados, cuando la búsqueda binaria funcionará mucho más eficientemente. A menudo, esta es una de esas afirmaciones populares que "suena bien" hechas por personas a las que no les importa pensar demasiado. En realidad, si considera el panorama general, dadas las circunstancias correctas, la búsqueda lineal puede ser mucho más eficiente que la búsqueda binaria.

Tenga en cuenta que si consideramos una única consulta de búsqueda para una matriz ordenada, la búsqueda binaria es un método significativamente más eficiente que la búsqueda lineal. No hay discusión sobre eso. Además, cuando realiza múltiples consultas completamente aleatorias a la misma búsqueda binaria de datos, aún gana la búsqueda lineal.

Sin embargo, la imagen comienza a cambiar si consideramos consultas de búsqueda secuenciales y estas consultas no son exactamente al azar. Imagine que las consultas llegan ordenadas, es decir, cada consulta siguiente tiene un valor mayor que la consulta anterior. Es decir, las consultas también están ordenadas . Por cierto, no tienen que estar globalmente y estrictamente ordenados, de vez en cuando la secuencia de consulta puede ser "reiniciada", es decir, se consulta un valor bajo, pero en promedio las consultas consiguientes deberían llegar en orden creciente. En otras palabras, las consultas llegan en serie , cada serie ordenada en orden ascendente. En este caso, si la longitud promedio de la serie es comparable a la longitud de su matriz, la búsqueda lineal superará a la búsqueda binaria por un margen enorme. Sin embargo, para aprovechar esta situación, debe implementar su búsqueda de manera gradual . Es simple: si la siguiente consulta es mayor que la anterior, no es necesario iniciar la búsqueda desde el comienzo de la matriz. En cambio, puede buscar desde el punto donde se detuvo la búsqueda anterior. La implementación más simple (solo para ilustrar la idea) podría verse de la siguiente manera

static int linear(const int *arr, int n, int key) { static int previous_key = INT_MIN; static int previous_i = 0; i = key >= previous_key ? previous_i : 0; while (i < n) { if (arr[i] >= key) break; ++i; } previous_key = key; previous_i = i; return i; }

(Descargo de responsabilidad: la implementación anterior es terriblemente fea por la razón obvia de que la matriz está llegando desde afuera como un parámetro, mientras que el estado de búsqueda anterior está almacenado internamente. Por supuesto, esta es una forma incorrecta de hacerlo en la práctica. arriba está destinado a ilustrar la idea y nada más).

Tenga en cuenta que la complejidad de procesar cada serie de consultas ordenadas utilizando el enfoque anterior siempre es O(N) , independientemente de la longitud de la serie. Usando la búsqueda binaria, la complejidad sería O(M * log N) . Entonces, por razones obvias cuando M está cerca de N , es decir, las consultas llegan en series ordenadas suficientemente largas, la búsqueda lineal anterior superará significativamente a la búsqueda binaria, mientras que para M pequeña la búsqueda binaria ganará.

Además, incluso si la serie ordenada de consultas no es muy larga, la modificación anterior podría darle una mejora notable en el rendimiento de la búsqueda, teniendo en cuenta que debe utilizar la búsqueda lineal.

PD Como información adicional sobre la estructura del problema:

Cuando necesite realizar la búsqueda en una matriz ordenada de longitud N y sepa de antemano que las consultas llegarán en series ordenadas de longitud M [aproximada, promedio], el algoritmo óptimo se verá de la siguiente manera

Calcule el valor de la zancada S = [N/M] . También podría tener sentido "ajustar" el valor de S a la potencia [más cercana] de 2. Piense en su matriz ordenada como una secuencia de bloques de longitud S , llamados bloques S.
Después de recibir una consulta, realice una búsqueda lineal incremental para el S-block que potencialmente contiene el valor consultado, es decir, es una búsqueda lineal ordinaria con zancada S (por supuesto, recuerde comenzar desde el bloque donde dejó la búsqueda anterior).
Después de encontrar el bloque S, realice la búsqueda binaria dentro del bloque S para el valor consultado.

Lo anterior es el algoritmo de búsqueda incremental más óptimo posible, en el sentido de que alcanza el límite teórico sobre la eficiencia asintótica de la búsqueda repetitiva. Tenga en cuenta que si el valor de M es mucho más pequeño que N , el algoritmo "automáticamente" se desplaza hacia la búsqueda binaria , mientras que cuando M se acerca a N el algoritmo "automáticamente" favorece la búsqueda lineal . Esto último tiene sentido porque en dicho entorno la búsqueda lineal es significativamente más eficiente que la búsqueda binaria.

Todo esto es solo para ilustrar el hecho de que las afirmaciones generales como "la búsqueda lineal en una matriz ordenada es siempre inútil" indican nada más que la falta de conocimiento por parte de quienes hacen tales afirmaciones.

Podría evitar n controles similares a cómo se desenrolla el bucle

static int linear(const int *array, int arraySize, int key) { //assuming the actual size of the array is always 1 less than arraySize array[arraySize] = key; int i = 0; for (; ; ++i) { if (array[i] == key) return i; } }

Puede buscar un elemento más grande que un int a la vez, específicamente en la plataforma, esto puede ser mucho más rápido o más lento dependiendo de cómo maneje la lectura de datos más grande. Por ejemplo, en un sistema de 64 bits, leer en la matriz 2 elementos a la vez y verificar los elementos hi / low por separado podría correr más rápido debido a menos E / S. Aún así, este es un tipo de variedad O (n) sin importar qué.

Puedes hacerlo en paralelo.

Si la lista es pequeña, tal vez no valga la pena dividir la búsqueda, pero si tiene que procesar muchas búsquedas, puede ejecutarlas definitivamente en paralelo. Eso no reduciría la latencia de las operaciones, pero mejoraría el rendimiento.

Sé que este tema es antiguo, pero no pude evitar publicarlo. Mi optimización para una búsqueda lineal centinela es:

int sentinel_linear_search(int key, int *arr, int n) { int last_value, i; /* considering that n is the real size of the array */ if (--n < 1) return -1; last_value = arr[n]; /* set array last member as the key */ arr[n] = key; i = 0; while (arr[i] != key) ++i; /* recover the real array last member */ arr[n] = last_value; return (arr[i] == key) ? i : -1; }

La gran mejora de búsqueda centinela es que su iteración usa solo una rama condicional (clave) en lugar de dos (índice y clave).

while (arr[i] != key) ++i;

Si estás en una plataforma Intel:

int linear (const int *array, int n, int key) { __asm { mov edi,array mov ecx,n mov eax,key repne scasd mov eax,-1 jne end mov eax,n sub eax,ecx dec eax end: } }

pero eso solo encuentra coincidencias exactas, coincidencias iguales o no mayores.

En C, también puedes usar el dispositivo de Duff :

int linear (const int *array, int n, int key) { const int *end = &array [n]; int result = 0; switch (n % 8) { do { case 0: if (*(array++) >= key) break; ++result; case 7: if (*(array++) >= key) break; ++result; case 6: if (*(array++) >= key) break; ++result; case 5: if (*(array++) >= key) break; ++result; case 4: if (*(array++) >= key) break; ++result; case 3: if (*(array++) >= key) break; ++result; case 2: if (*(array++) >= key) break; ++result; case 1: if (*(array++) >= key) break; ++result; } while(array < end); } return result; }

Si tuviera una computadora cuántica, podría usar el algoritmo de Grover para buscar sus datos en el tiempo O (N ^1/2 ) y usar el espacio de almacenamiento O (log N). De lo contrario, tu pregunta es bastante tonta. La búsqueda binaria o una de sus variantes (búsqueda trinaria, por ejemplo) es realmente su mejor opción. Hacer micro-optimizaciones en una búsqueda lineal es estúpido cuando puedes elegir un algoritmo superior.

Si una solución específica para un objetivo es aceptable, entonces puede usar fácilmente SIMD (SSE, AltiVec, o lo que sea que tenga disponible) para obtener ~ 4x de aceleración probando 4 elementos a la vez en lugar de solo 1.

Fuera de interés, armé una implementación SIMD simple de la siguiente manera:

int linear_search_ref(const int32_t *A, int32_t key, int n) { int result = -1; int i; for (i = 0; i < n; ++i) { if (A[i] >= key) { result = i; break; } } return result; } int linear_search(const int32_t *A, int32_t key, int n) { #define VEC_INT_ELEMS 4 #define BLOCK_SIZE (VEC_INT_ELEMS * 32) const __m128i vkey = _mm_set1_epi32(key); int vresult = -1; int result = -1; int i, j; for (i = 0; i <= n - BLOCK_SIZE; i += BLOCK_SIZE) { __m128i vmask0 = _mm_set1_epi32(-1); __m128i vmask1 = _mm_set1_epi32(-1); int mask0, mask1; for (j = 0; j < BLOCK_SIZE; j += VEC_INT_ELEMS * 2) { __m128i vA0 = _mm_load_si128(&A[i + j]); __m128i vA1 = _mm_load_si128(&A[i + j + VEC_INT_ELEMS]); __m128i vcmp0 = _mm_cmpgt_epi32(vkey, vA0); __m128i vcmp1 = _mm_cmpgt_epi32(vkey, vA1); vmask0 = _mm_and_si128(vmask0, vcmp0); vmask1 = _mm_and_si128(vmask1, vcmp1); } mask0 = _mm_movemask_epi8(vmask0); mask1 = _mm_movemask_epi8(vmask1); if ((mask0 & mask1) != 0xffff) { vresult = i; break; } } if (vresult > -1) { result = vresult + linear_search_ref(&A[vresult], key, BLOCK_SIZE); } else if (i < n) { result = i + linear_search_ref(&A[i], key, n - i); } return result; #undef BLOCK_SIZE #undef VEC_INT_ELEMS }

En un Core i7 a 2.67 GHz, usando OpenSUSE x86-64 y gcc 4.3.2, obtengo una mejora de 7x - 8x alrededor de un "punto óptimo" bastante amplio donde n = 100000 con la clave encontrada en el punto medio de la matriz (es decir, resultado = n / 2). El rendimiento cae a alrededor de 3.5x cuando n es grande y, por lo tanto, la matriz excede el tamaño de caché (en este caso, se está convirtiendo en el límite de ancho de banda de la memoria). El rendimiento también disminuye cuando n es pequeño, debido a la ineficiencia de la implementación de SIMD (por supuesto, fue optimizado para n grandes).

ciclo hacia atrás, esto podría ser traducido ...

// loop backward for (int i = arraySize - 1; i >=0; --i)

... a esto ("podría ser" más rápido):

mov cx, arraySize - 1 detectionHere: ... loop detectionHere

Aparte de eso, solo la búsqueda binaria puede hacer que la búsqueda sea más rápida

desenrollar con índices de arreglos fijos.

int linear( const int *array, int n, int key ) { int i = 0; if ( array[n-1] >= key ) { do { if ( array[0] >= key ) return i+0; if ( array[1] >= key ) return i+1; if ( array[2] >= key ) return i+2; if ( array[3] >= key ) return i+3; array += 4; i += 4; } while ( true ); } return -1; }

esto podría forzar instrucciones vectoriales (sugeridas por Gman):

for (int i = 0; i < N; i += 4) { bool found = false; found |= (array[i+0] >= key); ... found |= ( array[i+3] >= key); // slight variation would be to use max intrinsic if (found) return i; } ... // quick search among four elements

esto también hace menos instrucciones de bifurcación. usted hace la ayuda asegurando que la matriz de entrada esté alineada con el límite de 16 bytes

Otra cosa que puede ayudar a la vectorización (haciendo la comparación máxima vertical):

for (int i = 0; i < N; i += 8) { bool found = false; found |= max(array[i+0], array[i+4]) >= key; ... found |= max(array[i+3], array[i+7] >= key; if (found) return i; } // have to search eight elements

In one of the comments you said the array length is 64.

Well if you must do it linearly, you can do:

int i = -1; do { if (arr[0] >= key){i = 0; break;} if (arr[1] >= key){i = 1; break;} ... if (arr[62] >= key){i = 62; break;} if (arr[63] >= key){i = 63; break;} } while(0);

However, I seriously doubt if that is faster than this binary search: *

int i = 0; if (key >= arr[i+32]) i += 32; if (key >= arr[i+16]) i += 16; if (key >= arr[i+ 8]) i += 8; if (key >= arr[i+ 4]) i += 4; if (key >= arr[i+ 2]) i += 2; if (key >= arr[i+ 1]) i += 1;

*Thanks to Jon Bentley for that one.

Added: since you said this table is prepared once for a large number of searches, and you want fast , you could allocate some space somewhere and generate machine code with the values hard-wired into it. It could either be linear or binary search. If binary, the machine code would look like what the compiler would generate from this:

if (key < value32){ if (key < value16){ ... } else { ... } } else { if (key < value48){ ... } else { ... } }

Then you just copy that into a place where you can call it.

OR you could print the code above, compile and link it on the fly into a dll, and load the dll.

Well, you could use pointers...

static int linear(const int *array, int arraySize, int key) { int i; for(i = 0; i < arraySize; ++i) { if(*array >= key) { return i; } ++array; } return arraySize; }

uint32 LinearFindSse4( uint8* data, size_t data_len, uint8* finddata, size_t finddatalen ) { /** * the following is based on... * #define haszero(v) (((v) - 0x01010101UL) & ~(v) & 0x80808080UL) * we split it into 2 sections * first section is: * (v) - 0x01010101UL) * * second section is: * ~(v) & 0x80808080UL) */ __m128i ones = _mm_set1_epi8( 0x01 ); __m128i eights = _mm_set1_epi8( 0x80 ); __m128i find_field = _mm_set1_epi8( finddata[0] ); uint32 found_at = 0; for (int i = 0; i < data_len; i+=16) { #define CHECKTHIS( n ) if (!memcmp(&data[i+n], &finddata[0], sizeof(finddata))) { found_at = i + n; break; } __m128i chunk = _mm_stream_load_si128( (__m128i *)&data[i] ); __m128i xor_result = _mm_xor_si128( chunk, find_field ); __m128i first_sec = _mm_sub_epi64( xor_result, ones ); __m128i second_sec = _mm_andnot_si128( xor_result, eights ); if(!_mm_testz_si128(first_sec, second_sec)) { CHECKTHIS(0); CHECKTHIS(1); CHECKTHIS(2); CHECKTHIS(3); CHECKTHIS(4); CHECKTHIS(5); CHECKTHIS(6); CHECKTHIS(7); CHECKTHIS(8); CHECKTHIS(9); CHECKTHIS(10); CHECKTHIS(11); CHECKTHIS(12); CHECKTHIS(13); CHECKTHIS(14); CHECKTHIS(15); } } return found_at; }