¿Encuentra rápidamente si un valor está presente en una matriz C?

Tengo una aplicación integrada con un ISR de tiempo crítico que necesita iterar a través de una matriz de tamaño 256 (preferiblemente 1024, pero 256 es el mínimo) y verificar si un valor coincide con el contenido de la matriz. A boolse establecerá en verdadero si este es el caso.

El microcontrolador es un NXP LPC4357, núcleo ARM Cortex M4, y el compilador es GCC. Ya combiné el nivel de optimización 2 (3 es más lento) y coloqué la función en RAM en lugar de flash. También utilizo la aritmética del puntero y un forbucle, que cuenta hacia abajo en lugar de hacia arriba (comprobar si i!=0es más rápido que comprobar si i<256). Con todo, termino con una duración de 12.5 µs que debe reducirse drásticamente para ser factible. Este es el (pseudo) código que uso ahora:

uint32_t i;
uint32_t *array_ptr = &theArray[0];
uint32_t compareVal = 0x1234ABCD;
bool validFlag = false;

for (i=256; i!=0; i--)
{
    if (compareVal == *array_ptr++)
    {
         validFlag = true;
         break;
     }
}

¿Cuál sería la forma más rápida de hacer esto? Se permite el montaje en línea. También se permiten otros trucos "menos elegantes".

En situaciones en las que el rendimiento es de suma importancia, el compilador de C probablemente no producirá el código más rápido en comparación con lo que puede hacer con el lenguaje ensamblador ajustado a mano. Tiendo a tomar el camino de menor resistencia: para pequeñas rutinas como esta, solo escribo un código asm y tengo una buena idea de cuántos ciclos tomará ejecutar. Es posible que pueda jugar con el código C y hacer que el compilador genere una buena salida, pero puede terminar perdiendo mucho tiempo ajustando la salida de esa manera. Los compiladores (especialmente de Microsoft) han recorrido un largo camino en los últimos años, pero aún no son tan inteligentes como el compilador entre tus oídos porque estás trabajando en tu situación específica y no solo en un caso general. El compilador no puede hacer uso de ciertas instrucciones (por ejemplo, LDM) que pueden acelerar esto, y ' Es poco probable que sea lo suficientemente inteligente como para desenrollar el bucle. Aquí hay una manera de hacerlo que incorpora las 3 ideas que mencioné en mi comentario: Desenrollo de bucle, captación previa de caché y haciendo uso de la instrucción de carga múltiple (ldm). El recuento del ciclo de instrucciones es de aproximadamente 3 relojes por elemento de matriz, pero esto no tiene en cuenta los retrasos de memoria.

Teoría de operación: el diseño de CPU de ARM ejecuta la mayoría de las instrucciones en un ciclo de reloj, pero las instrucciones se ejecutan en una tubería. Los compiladores de C intentarán eliminar los retrasos en la canalización intercalando otras instrucciones intermedias. Cuando se presenta un bucle cerrado como el código C original, el compilador tendrá dificultades para ocultar los retrasos porque el valor leído de la memoria debe compararse de inmediato. Mi código a continuación alterna entre 2 conjuntos de 4 registros para reducir significativamente los retrasos de la memoria en sí y la tubería que busca los datos. En general, cuando trabaja con grandes conjuntos de datos y su código no hace uso de la mayoría o de todos los registros disponibles, no obtiene el máximo rendimiento.

; r0 = count, r1 = source ptr, r2 = comparison value

   stmfd sp!,{r4-r11}   ; save non-volatile registers
   mov r3,r0,LSR #3     ; loop count = total count / 8
   pld [r1,#128]
   ldmia r1!,{r4-r7}    ; pre load first set
loop_top:
   pld [r1,#128]
   ldmia r1!,{r8-r11}   ; pre load second set
   cmp r4,r2            ; search for match
   cmpne r5,r2          ; use conditional execution to avoid extra branch instructions
   cmpne r6,r2
   cmpne r7,r2
   beq found_it
   ldmia r1!,{r4-r7}    ; use 2 sets of registers to hide load delays
   cmp r8,r2
   cmpne r9,r2
   cmpne r10,r2
   cmpne r11,r2
   beq found_it
   subs r3,r3,#1        ; decrement loop count
   bne loop_top
   mov r0,#0            ; return value = false (not found)
   ldmia sp!,{r4-r11}   ; restore non-volatile registers
   bx lr                ; return
found_it:
   mov r0,#1            ; return true
   ldmia sp!,{r4-r11}
   bx lr

Actualización: Hay muchos escépticos en los comentarios que piensan que mi experiencia es anecdótica / sin valor y requieren pruebas. Utilicé GCC 4.8 (del Android NDK 9C) para generar el siguiente resultado con la optimización -O2 (todas las optimizaciones activadas, incluido el desenrollado del bucle ). Compilé el código C original presentado en la pregunta anterior. Esto es lo que produjo GCC:

.L9: cmp r3, r0
     beq .L8
.L3: ldr r2, [r3, #4]!
     cmp r2, r1
     bne .L9
     mov r0, #1
.L2: add sp, sp, #1024
     bx  lr
.L8: mov r0, #0
     b .L2

La salida de GCC no solo no desenrolla el bucle, sino que también desperdicia un reloj en una parada después del LDR. Requiere al menos 8 relojes por elemento de matriz. Hace un buen trabajo al usar la dirección para saber cuándo salir del bucle, pero todas las cosas mágicas que los compiladores son capaces de hacer no se encuentran en este código. No ejecuté el código en la plataforma de destino (no tengo uno), pero cualquier persona con experiencia en el rendimiento del código ARM puede ver que mi código es más rápido.

Actualización 2: le di a Microsoft Visual Studio 2013 SP2 la oportunidad de mejorar con el código. Fue capaz de usar instrucciones NEON para vectorizar mi inicialización de matriz, pero la búsqueda de valor lineal tal como está escrita por el OP resultó similar a lo que generó GCC (cambié el nombre de las etiquetas para que sea más legible):

loop_top:
   ldr  r3,[r1],#4  
   cmp  r3,r2  
   beq  true_exit
   subs r0,r0,#1 
   bne  loop_top
false_exit: xxx
   bx   lr
true_exit: xxx
   bx   lr

Como dije, no soy dueño del hardware exacto del OP, pero probaré el rendimiento en un nVidia Tegra 3 y Tegra 4 de las 3 versiones diferentes y publicaré los resultados aquí pronto.

Actualización 3: ejecuté mi código y el código ARM compilado de Microsoft en un Tegra 3 y Tegra 4 (Surface RT, Surface RT 2). Ejecuté 1000000 iteraciones de un bucle que no puede encontrar una coincidencia para que todo esté en caché y sea fácil de medir.

             My Code       MS Code
Surface RT    297ns         562ns
Surface RT 2  172ns         296ns  

En ambos casos, mi código se ejecuta casi el doble de rápido. La mayoría de las CPU ARM modernas probablemente darán resultados similares.

Hay un truco para optimizarlo (una vez me preguntaron esto en una entrevista de trabajo):

• Si la última entrada en la matriz contiene el valor que está buscando, entonces devuelva verdadero
• Escriba el valor que está buscando en la última entrada de la matriz
• Itera la matriz hasta que encuentres el valor que estás buscando
• Si lo ha encontrado antes de la última entrada en la matriz, devuelva verdadero
• Falso retorno

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    uint32_t x = theArray[SIZE-1];
    if (x == compareVal)
        return true;
    theArray[SIZE-1] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    theArray[SIZE-1] = x;
    return i != SIZE-1;
}

Esto produce una rama por iteración en lugar de dos ramas por iteración.

ACTUALIZAR:

Si se le permite asignar la matriz a SIZE+1, entonces puede deshacerse de la parte del "intercambio de la última entrada":

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t i;
    theArray[SIZE] = compareVal;
    for (i = 0; theArray[i] != compareVal; i++);
    return i != SIZE;
}

También puede deshacerse de la aritmética adicional incorporada theArray[i], utilizando en su lugar lo siguiente:

bool check(uint32_t theArray[], uint32_t compareVal)
{
    uint32_t *arrayPtr;
    theArray[SIZE] = compareVal;
    for (arrayPtr = theArray; *arrayPtr != compareVal; arrayPtr++);
    return arrayPtr != theArray+SIZE;
}

Si el compilador aún no lo aplica, entonces esta función lo hará con seguridad. Por otro lado, puede hacer que sea más difícil para el optimizador desenrollar el bucle, por lo que tendrá que verificar eso en el código de ensamblaje generado ...

Estás pidiendo ayuda para optimizar tu algoritmo, lo que puede llevarte al ensamblador. Pero su algoritmo (una búsqueda lineal) no es tan inteligente, por lo que debería considerar cambiar su algoritmo. P.ej:

• función hash perfecta
• búsqueda binaria

Función hash perfecta

Si sus 256 valores "válidos" son estáticos y se conocen en tiempo de compilación, puede usar una función hash perfecta . Debe encontrar una función hash que asigne su valor de entrada a un valor en el rango 0 .. n , donde no hay colisiones para todos los valores válidos que le interesan. Es decir, no hay dos valores "válidos" hash para el mismo valor de salida. Al buscar una buena función hash, su objetivo es:

• Mantenga la función hash razonablemente rápida.
• Minimizar n . Lo más pequeño que puede obtener es 256 (función hash perfecta mínima), pero eso es probablemente difícil de lograr, dependiendo de los datos.

Tenga en cuenta que para funciones hash eficientes, n es a menudo una potencia de 2, que es equivalente a una máscara de bits bajos (operación AND). Ejemplo de funciones hash:

• CRC de bytes de entrada, módulo n .
• ((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n(recogiendo el mayor número i, j, k, ..., según sea necesario, con desplazamientos a la izquierda o derecha)

Luego, crea una tabla fija de n entradas, donde el hash asigna los valores de entrada a un índice i en la tabla. Para valores válidos, la entrada de tabla i contiene el valor válido. Para todas las demás entradas de la tabla, asegúrese de que cada entrada del índice i contenga algún otro valor no válido que no sea hash para i .

Luego, en su rutina de interrupción, con la entrada x :

1. Hash x para indexar i (que está en el rango 0..n)
2. Busque la entrada i en la tabla y vea si contiene el valor x .

Esto será mucho más rápido que una búsqueda lineal de 256 o 1024 valores.

He escrito un código de Python para encontrar funciones hash razonables.

Búsqueda binaria

Si ordena su matriz de 256 valores "válidos", puede hacer una búsqueda binaria , en lugar de una búsqueda lineal. Eso significa que debería poder buscar una tabla de 256 entradas en solo 8 pasos ( log2(256)), o una tabla de 1024 entradas en 10 pasos. Nuevamente, esto será mucho más rápido que una búsqueda lineal de 256 o 1024 valores.

Mantenga la tabla ordenada y use la búsqueda binaria desenrollada de Bentley:

i = 0;
if (key >= a[i+512]) i += 512;
if (key >= a[i+256]) i += 256;
if (key >= a[i+128]) i += 128;
if (key >= a[i+ 64]) i +=  64;
if (key >= a[i+ 32]) i +=  32;
if (key >= a[i+ 16]) i +=  16;
if (key >= a[i+  8]) i +=   8;
if (key >= a[i+  4]) i +=   4;
if (key >= a[i+  2]) i +=   2;
if (key >= a[i+  1]) i +=   1;
return (key == a[i]);

La cuestión es,

• si sabe qué tan grande es la tabla, entonces sabe cuántas iteraciones habrá, por lo que puede desenrollarla por completo.
• Entonces, no hay ningún punto de prueba para el ==caso en cada iteración porque, excepto en la última iteración, la probabilidad de ese caso es demasiado baja para justificar pasar tiempo probando para ello. **
• Finalmente, al expandir la tabla a una potencia de 2, agrega como máximo una comparación y como máximo un factor de dos de almacenamiento.

** Si no estás acostumbrado a pensar en términos de probabilidades, cada punto de decisión tiene una entropía , que es la información promedio que aprendes al ejecutarla. Para las >=pruebas, la probabilidad de cada rama es de aproximadamente 0.5, y -log2 (0.5) es 1, entonces eso significa que si toma una rama, aprende 1 bit, y si toma la otra rama, aprende un bit, y el promedio es solo la suma de lo que aprendes en cada rama multiplicado por la probabilidad de esa rama. Entonces 1*0.5 + 1*0.5 = 1, entonces la entropía de la>= prueba es 1. Como tienes 10 bits para aprender, se necesitan 10 ramas. ¡Por eso es rápido!

Por otro lado, ¿qué pasa si tu primera prueba es if (key == a[i+512)? La probabilidad de ser verdadero es 1/1024, mientras que la probabilidad de ser falso es 1023/1024. Entonces, si es verdad, ¡aprendes los 10 bits! Pero si es falso, aprende -log2 (1023/1024) = .00141 bits, ¡prácticamente nada! Entonces, la cantidad promedio que aprende de esa prueba es10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112 bits. Alrededor de una centésima de bit. ¡Esa prueba no tiene su peso!

Si el conjunto de constantes en su tabla se conoce de antemano, puede usar el hash perfecto para asegurarse de que solo se haga un acceso a la tabla. El hash perfecto determina una función de hash que asigna cada tecla interesante a una ranura única (esa tabla no siempre es densa, pero puede decidir qué tan poco densa puede permitirse una tabla, con tablas menos densas que generalmente conducen a funciones de hash más simples).

Por lo general, la función hash perfecta para el conjunto específico de claves es relativamente fácil de calcular; no quieres que sea largo y complicado porque eso compite por el tiempo, quizás mejor gastado haciendo múltiples sondas.

El hashing perfecto es un esquema de "1 sonda máxima". Se puede generalizar la idea, con el pensamiento de que se debe intercambiar la simplicidad de calcular el código hash con el tiempo que lleva hacer sondas k. Después de todo, el objetivo es "el menor tiempo total para buscar", no la menor cantidad de sondas o la función hash más simple. Sin embargo, nunca he visto a nadie construir un algoritmo de hash k-probes-max. Sospecho que uno puede hacerlo, pero eso es probablemente una investigación.

Otro pensamiento: si su procesador es extremadamente rápido, la única sonda a la memoria desde un hash perfecto probablemente domine el tiempo de ejecución. Si el procesador no es muy rápido, k> 1 sondas pueden ser prácticas.

Use un conjunto de hash. Le dará a O (1) tiempo de búsqueda.

El siguiente código asume que puede reservar el valor 0como un valor 'vacío', es decir, que no aparece en los datos reales. La solución se puede ampliar para una situación en la que este no es el caso.

#define HASH(x) (((x >> 16) ^ x) & 1023)
#define HASH_LEN 1024
uint32_t my_hash[HASH_LEN];

int lookup(uint32_t value)
{
    int i = HASH(value);
    while (my_hash[i] != 0 && my_hash[i] != value) i = (i + 1) % HASH_LEN;
    return i;
}

void store(uint32_t value)
{
    int i = lookup(value);
    if (my_hash[i] == 0)
       my_hash[i] = value;
}

bool contains(uint32_t value)
{
    return (my_hash[lookup(value)] == value);
}

En la implementación de este ejemplo, el tiempo de búsqueda generalmente será muy bajo, pero en el peor de los casos puede ser hasta el número de entradas almacenadas. Para una aplicación en tiempo real, puede considerar también una implementación utilizando árboles binarios, que tendrán un tiempo de búsqueda más predecible.

En este caso, podría valer la pena investigar los filtros de Bloom . Son capaces de establecer rápidamente que un valor no está presente, lo cual es bueno, ya que la mayoría de los 2 ^ 32 valores posibles no están en esa matriz de 1024 elementos. Sin embargo, hay algunos falsos positivos que necesitarán un control adicional.

Dado que su tabla es aparentemente estática, puede determinar qué falsos positivos existen para su filtro Bloom y ponerlos en un hash perfecto.

Suponiendo que su procesador funciona a 204 MHz, que parece ser el máximo para el LPC4357, y también suponiendo que su resultado de sincronización refleja el caso promedio (la mitad de la matriz recorrida), obtenemos:

• Frecuencia de la CPU: 204 MHz
• Periodo del ciclo: 4.9 ns
• Duración en ciclos: 12.5 µs / 4.9 ns = 2551 ciclos
• Ciclos por iteración: 2551/128 = 19,9

Entonces, su ciclo de búsqueda gasta alrededor de 20 ciclos por iteración. Eso no suena horrible, pero supongo que para hacerlo más rápido, debe mirar el ensamblaje.

Recomendaría soltar el índice y usar una comparación de puntero, y hacer todos los punteros const.

bool arrayContains(const uint32_t *array, size_t length)
{
  const uint32_t * const end = array + length;
  while(array != end)
  {
    if(*array++ == 0x1234ABCD)
      return true;
  }
  return false;
}

Al menos eso vale la pena probar.

Otras personas han sugerido reorganizar su tabla, agregar un valor centinela al final u ordenarlo para proporcionar una búsqueda binaria.

Usted declara "También utilizo la aritmética de puntero y un bucle for, que realiza un conteo regresivo en lugar de uno ascendente (verificar si i != 0es más rápido que verificar si i < 256)".

Mi primer consejo es: deshacerse de la aritmética del puntero y la cuenta regresiva. Cosas como

for (i=0; i<256; i++)
{
    if (compareVal == the_array[i])
    {
       [...]
    }
}

tiende a ser idiomático para el compilador. El bucle es idiomático, y la indexación de una matriz sobre una variable de bucle es idiomática. El malabarismo con la aritmética de punteros y los punteros tenderá a ofuscar las expresiones idiomáticas al compilador y hará que genere código relacionado con lo que escribió en lugar de con lo que el escritor del compilador decidió ser el mejor curso para la tarea general .

Por ejemplo, el código anterior podría compilarse en un bucle que se ejecuta desde -256o -255hasta cero, indexando &the_array[256]. Posiblemente cosas que ni siquiera se pueden expresar en una C válida pero que coinciden con la arquitectura de la máquina para la que está generando.

Entonces no microoptimice. Solo está lanzando llaves en los trabajos de su optimizador. Si quiere ser inteligente, trabaje en las estructuras de datos y algoritmos, pero no optimice su expresión. Simplemente volverá a morderte, si no en el compilador / arquitectura actual, luego en el siguiente.

En particular, el uso de la aritmética del puntero en lugar de las matrices y los índices es un veneno para el compilador que es plenamente consciente de las alineaciones, ubicaciones de almacenamiento, consideraciones de alias y otras cosas, y para hacer optimizaciones como la reducción de la fuerza de la manera más adecuada para la arquitectura de la máquina.

Aquí se puede utilizar la vectorización, como suele ocurrir en las implementaciones de memchr. Utiliza el siguiente algoritmo:

1. Cree una máscara de la repetición de su consulta, de igual longitud que el recuento de bits de su sistema operativo (64 bits, 32 bits, etc.). En un sistema de 64 bits, repetiría la consulta de 32 bits dos veces.

2. Procese la lista como una lista de múltiples datos a la vez, simplemente convirtiendo la lista en una lista de un tipo de datos más grande y extrayendo valores. Para cada fragmento, XOR con la máscara, luego XOR con 0b0111 ... 1, luego agregue 1, luego & con una máscara de 0b1000 ... 0 repitiendo. Si el resultado es 0, definitivamente no hay una coincidencia. De lo contrario, puede haber (por lo general, con una probabilidad muy alta) una coincidencia, así que busque el fragmento normalmente.

Implementación de ejemplo: https://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src

Si puede acomodar el dominio de sus valores con la cantidad de memoria disponible para su aplicación, entonces, la solución más rápida sería representar su matriz como una matriz de bits:

bool theArray[MAX_VALUE]; // of which 1024 values are true, the rest false
uint32_t compareVal = 0x1234ABCD;
bool validFlag = theArray[compareVal];

EDITAR

Estoy asombrado por la cantidad de críticos. El título de este hilo es "¿Cómo puedo encontrar rápidamente si un valor está presente en una matriz C?" por lo cual apoyaré mi respuesta porque responde precisamente eso. Podría argumentar que esta tiene la función hash más eficiente en cuanto a velocidad (ya que address === value). He leído los comentarios y estoy al tanto de las advertencias obvias. Indudablemente, esas advertencias limitan el rango de problemas que esto puede usarse para resolver, pero, para aquellos problemas que resuelve, resuelve de manera muy eficiente.

En lugar de rechazar esta respuesta directamente, considérela como el punto de partida óptimo para el cual puede evolucionar utilizando funciones hash para lograr un mejor equilibrio entre velocidad y rendimiento.

Asegúrese de que las instrucciones ("el pseudocódigo") y los datos ("theArray") estén en memorias separadas (RAM) para que la arquitectura CM4 Harvard se utilice en todo su potencial. Del manual del usuario:

Para optimizar el rendimiento de la CPU, el ARM Cortex-M4 tiene tres buses para acceso a Instrucción (código) (I), acceso a Datos (D) y acceso al Sistema (S). Cuando las instrucciones y los datos se guardan en memorias separadas, los accesos de código y datos se pueden hacer en paralelo en un ciclo. Cuando el código y los datos se guardan en la misma memoria, las instrucciones que cargan o almacenan datos pueden tomar dos ciclos.

Lo siento si mi respuesta ya fue respondida, solo soy un lector vago. Siéntete libre de votar abajo entonces))

1) podría eliminar el contador 'i' en absoluto: solo compare los punteros, es decir

for (ptr = &the_array[0]; ptr < the_array+1024; ptr++)
{
    if (compareVal == *ptr)
    {
       break;
    }
}
... compare ptr and the_array+1024 here - you do not need validFlag at all.

Sin embargo, todo eso no proporcionará ninguna mejora significativa, tal optimización probablemente podría ser lograda por el compilador mismo.

2) Como ya se mencionó en otras respuestas, casi todas las CPU modernas están basadas en RISC, por ejemplo ARM. Incluso las CPU Intel X86 modernas usan núcleos RISC en el interior, hasta donde yo sé (compilando desde X86 sobre la marcha). La optimización principal para RISC es la optimización de canalización (y también para Intel y otras CPU), minimizando los saltos de código. Un tipo de tal optimización (probablemente una importante), es el "ciclo de reversión". Es increíblemente estúpido y eficiente, incluso el compilador de Intel puede hacer eso AFAIK. Parece que:

if (compareVal == the_array[0]) { validFlag = true; goto end_of_compare; }
if (compareVal == the_array[1]) { validFlag = true; goto end_of_compare; }
...and so on...
end_of_compare:

De esta manera, la optimización es que la tubería no se rompe en el peor de los casos (si compareVal está ausente en la matriz), por lo que es lo más rápido posible (por supuesto, sin contar las optimizaciones de algoritmos como tablas hash, matrices ordenadas, etc.) mencionado en otras respuestas, que pueden dar mejores resultados dependiendo del tamaño de la matriz. El enfoque de Ciclos Rollback puede aplicarse allí también por cierto. Estoy escribiendo aquí sobre eso, creo que no lo vi en otros)

La segunda parte de esta optimización es que ese elemento de la matriz se toma por dirección directa (se calcula en la etapa de compilación, asegúrese de usar una matriz estática) y no necesita una operación ADD adicional para calcular el puntero desde la dirección base de la matriz. Es posible que esta optimización no tenga un efecto significativo, ya que la arquitectura AFAIK ARM tiene características especiales para acelerar el direccionamiento de matrices. Pero de todos modos, siempre es mejor saber que hiciste todo lo mejor solo en código C directamente, ¿verdad?

El ciclo de reversión puede parecer incómodo debido al desperdicio de ROM (sí, lo hizo correctamente al colocarlo en una parte rápida de la RAM, si su placa admite esta función), pero en realidad es un pago justo por la velocidad, que se basa en el concepto RISC. Este es solo un punto general de optimización de cálculo: sacrifica espacio por razones de velocidad y viceversa, según sus requisitos.

Si cree que la reversión de una matriz de 1024 elementos es un sacrificio demasiado grande para su caso, puede considerar la 'reversión parcial', por ejemplo, dividir la matriz en 2 partes de 512 elementos cada una, o 4x256, y así sucesivamente.

3) la CPU moderna a menudo admite operaciones SIMD, por ejemplo, el conjunto de instrucciones ARM NEON: permite ejecutar las mismas operaciones en paralelo. Hablando francamente, no recuerdo si es adecuado para operaciones de comparación, pero creo que puede serlo, deberías comprobarlo. Google muestra que también puede haber algunos trucos, para obtener la velocidad máxima, consulte https://stackoverflow.com/a/5734019/1028256

Espero que pueda darte algunas ideas nuevas.

Soy un gran fanático del hash. El problema, por supuesto, es encontrar un algoritmo eficiente que sea rápido y use una cantidad mínima de memoria (especialmente en un procesador integrado).

Si conoce de antemano los valores que pueden ocurrir, puede crear un programa que se ejecute a través de una multitud de algoritmos para encontrar el mejor o, mejor dicho, los mejores parámetros para sus datos.

Creé un programa sobre el que puedes leer en esta publicación y obtuve algunos resultados muy rápidos. 16000 entradas se traducen aproximadamente a 2 ^ 14 o un promedio de 14 comparaciones para encontrar el valor mediante una búsqueda binaria. Apunté explícitamente a búsquedas muy rápidas, en promedio encontrando el valor en <= 1.5 búsquedas, lo que resultó en mayores requisitos de RAM. Creo que con un valor promedio más conservador (digamos <= 3) se podría guardar mucha memoria. En comparación, el caso promedio para una búsqueda binaria en sus 256 o 1024 entradas daría como resultado un número promedio de comparaciones de 8 y 10, respectivamente.

Mi búsqueda promedio requirió alrededor de 60 ciclos (en una computadora portátil con Intel i5) con un algoritmo genérico (utilizando una división por una variable) y 40-45 ciclos con un especialista (probablemente utilizando una multiplicación). Esto debería traducirse en tiempos de búsqueda de menos de microsegundos en su MCU, dependiendo, por supuesto, de la frecuencia de reloj en la que se ejecuta.

Puede modificarse aún más en la vida real si el conjunto de entradas realiza un seguimiento de cuántas veces se accedió a una entrada. Si la matriz de entrada se ordena de mayor a menor acceso antes de que se calculen las indeces, encontrará los valores más comunes con una sola comparación.

Esto es más como un apéndice que una respuesta.

He tenido un caso similar en el pasado, pero mi matriz fue constante durante un número considerable de búsquedas.

En la mitad de ellos, el valor buscado NO estaba presente en la matriz. Entonces me di cuenta de que podía aplicar un "filtro" antes de hacer cualquier búsqueda.

Este "filtro" es solo un número entero simple, calculado UNA VEZ y utilizado en cada búsqueda.

Está en Java, pero es bastante simple:

binaryfilter = 0;
for (int i = 0; i < array.length; i++)
{
    // just apply "Binary OR Operator" over values.
    binaryfilter = binaryfilter | array[i];
}

Entonces, antes de hacer una búsqueda binaria, verifico binaryfilter:

// Check binaryfilter vs value with a "Binary AND Operator"
if ((binaryfilter & valuetosearch) != valuetosearch)
{
    // valuetosearch is not in the array!
    return false;
}
else
{
    // valuetosearch MAYBE in the array, so let's check it out
    // ... do binary search stuff ...

}

Puede usar un algoritmo hash 'mejor', pero esto puede ser muy rápido, especialmente para números grandes. Puede ser que esto pueda ahorrarle aún más ciclos.