programacion - ¿Encuentra rápidamente si un valor está presente en una matriz C?
matrices en c (14)
Tengo una aplicación incorporada 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 las matrices. Un bool se establecerá en verdadero es este es el caso. MCU es un compilador NXP LPC4357, ARM Cortex M4, es GCC. Ya tengo el nivel de optimización combinada 2 (3 es más lento) y coloco la función en RAM en lugar de flash. También uso la aritmética del puntero y un ciclo for , que realiza un conteo progresivo en lugar de activo (comprobando si i!=0 es más rápido que comprobar si i<256 ). Con todo, termino con una duración de 12.5us que debe reducirse drásticamente para que sea 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 y absoluta de hacer esto? Se permite el ensamblaje en línea. También se permiten otros trucos "menos elegantes".
En este caso, podría valer la pena investigar los filtros de floración. 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 poner esos en un hash perfecto.
En situaciones en las que el rendimiento es de suma importancia, es probable que el compilador de C no produzca el código más rápido en comparación con lo que puede hacer con un lenguaje de ensamblaje sintonizado a mano. Tiendo a tomar el camino de menor resistencia: para rutinas pequeñas como esta, solo escribo el código asm y tengo una buena idea de cuántos ciclos llevará ejecutar. Es posible que pueda jugar con el código C y hacer que el compilador genere un buen resultado, pero puede perder mucho tiempo sintonizando la salida de esa manera. Los compiladores (especialmente de Microsoft) han recorrido un largo camino en los últimos años, pero todavía no son tan inteligentes como el compilador entre sus oídos porque están trabajando en su situación específica y no solo en un caso general. El compilador puede no 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 ciclo. Aquí hay una manera de hacerlo que incorpora las 3 ideas que mencioné en mi comentario: desenrollar el bucle, captar previamente la caché y hacer uso de la instrucción de carga múltiple (ldm). El recuento de ciclos de instrucciones sale a aproximadamente 3 relojes por elemento de conjunto, pero esto no tiene en cuenta los retrasos de memoria.
Teoría de la operación: el diseño de la 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 interconexión intercalando otras instrucciones intermedias. Cuando se presenta un ciclo cerrado como el código C original, el compilador tendrá dificultades para ocultar los retrasos porque el valor leído de la memoria se debe comparar inmediatamente. Mi código a continuación alterna entre 2 juegos de 4 registros para reducir significativamente las demoras de la memoria y la tubería que busca los datos. En general, cuando se trabaja con grandes conjuntos de datos y su código no hace uso de la mayoría o de todos los registros disponibles, entonces 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. Usé GCC 4.8 (del Android NDK 9C) para generar el siguiente resultado con optimización -O2 (todas las optimizaciones activadas, incluido el despliegue del bucle ). Recopilé 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 conjunto. Hace un buen trabajo al usar la dirección para saber cuándo salir del ciclo, pero todos los compiladores de cosas mágicas que son capaces de hacer no se encuentran en este código. No he ejecutado 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. Pude usar las instrucciones de NEON para vectorizar la inicialización de mi matriz, pero la búsqueda de valor lineal escrita por OP resultó similar a lo que generó GCC (cambié el nombre de las etiquetas para hacerlo 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 poseo el 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 den resultados similares.
Estás pidiendo ayuda para optimizar tu algoritmo, lo que puede llevarte a 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
Si sus 256 valores "válidos" son estáticos y conocidos en tiempo de compilación, puede usar una función hash perfecta . Necesita encontrar una función hash que asigne el valor de entrada a un valor en el rango 0 .. n , donde no haya 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, tu 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 probablemente sea difícil de lograr, dependiendo de los datos.
Nota para funciones hash eficientes, n es a menudo una potencia de 2, que es equivalente a una máscara bit a bit de bits bajos (operación Y). Ejemplo de funciones hash:
- CRC de bytes de entrada, módulo n .
-
((x << i) ^ (x >> j) ^ (x << k) ^ ...) % n(seleccionando tantasi,j,k, ... según sea necesario, con turnos de 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 la 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 se herede en i .
Luego en tu rutina de interrupción, con la entrada x :
- Hash x para indexar i (que está en el rango 0..n)
- 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 Python para encontrar funciones hash razonables.
Búsqueda binaria
Si ordena su matriz de 256 valores "válidos", entonces puede hacer una búsqueda binaria , en lugar de una búsqueda lineal. Eso significa que debe poder buscar la tabla de 256 entradas en solo 8 pasos ( log2(256) ) o una tabla de 1024 entradas en 10 pasos. De nuevo, esto será mucho más rápido que una búsqueda lineal de 256 o 1024 valores.
Hay un truco para optimizarlo (me lo pidieron en una entrevista de trabajo):
- Si la última entrada en la matriz tiene 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 encuentre el valor que está buscando
- Si lo ha encontrado antes de la última entrada en la matriz, devuelva true
- 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 puede asignar la matriz a SIZE+1 , puede deshacerse de la parte "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 en theArray[i] , usando 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, esta función lo hará con seguridad. Por otro lado, podría dificultar el desenrollado del optimizador, por lo que deberá verificarlo en el código ensamblador generado ...
La vectorización se puede usar aquí, como suele ser en las implementaciones de memchr. Usas el siguiente algoritmo:
Cree una máscara de repetición de su consulta, igual en longitud a la cuenta 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.
Procese la lista como una lista de varias piezas de datos a la vez, simplemente lanzando la lista a una lista de un tipo de datos más grande y extrayendo los 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 repetición. Si el resultado es 0, definitivamente no hay una coincidencia. De lo contrario, puede (por lo general con una probabilidad muy alta) ser un partido, por lo que buscar el trozo normalmente.
Ejemplo de implementación: https://sourceware.org/cgi-bin/cvsweb.cgi/src/newlib/libc/string/memchr.c?rev=1.3&content-type=text/x-cvsweb-markup&cvsroot=src
Lo siento si mi respuesta ya fue respondida, solo soy un lector perezoso. Siente que eres libre de votar abajo))
1) podría eliminar el contador ''i'' en absoluto, simplemente 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 dará ninguna mejora significativa, tal optimización probablemente podría ser lograda por el propio compilador.
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 su interior, hasta donde yo sé (compilando desde X86 en vuelo). Major optimization for RISC is pipeline optimization (and for Intel and other CPU as well), minimizing code jumps. One type of such optimization (probably a major one), is "cycle rollback" one. It''s incredibly stupid, and efficient, even Intel compiler can do that AFAIK. It looks like:
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:
This way the optimization is that the pipeline is not broken for the worst case (if compareVal is absent in the array), so it is as fast as possible (of course not counting algorithm optimizations such as hash tables, sorted arrays and so on, mentioned in other answers, which may give better results depending on array size. Cycles Rollback approach can be applied there as well by the way. I''m writing here about that I think I didn''t see in others)
The second part of this optimization is that that array item is taken by direct address (calculated at compiling stage, make sure you use a static array), and do not need additional ADD op to calculate pointer from array''s base address. This optimization may not have significant effect, since AFAIK ARM architecture has special features to speed up arrays addressing. But anyway it''s always better to know that you did all the best just in C code directly, right?
Cycle Rollback may look awkward due to waste of ROM (yep, you did right placing it to fast part of RAM, if your board supports this feature), but actually it''s a fair pay for speed, being based on RISC concept. This is just a general point of calculation optimization - you sacrifice space for sake of speed, and vice versa, depending on your requirements.
If you think that rollback for array of 1024 elements is too large sacrifice for your case, you can consider ''partial rollback'', for example dividing the array into 2 parts of 512 items each, or 4x256, and so on.
3) modern CPU often support SIMD ops, for example ARM NEON instruction set - it allows to execute the same ops in parallel. Frankly speaking I do not remember if it is suitable for comparison ops, but I feel it may be, you should check that. Googling shows that there may be some tricks as well, to get max speed, see https://.com/a/5734019/1028256
I hope it can give you some new ideas.
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 cuán grande es la tabla, entonces sabrá cuántas iteraciones habrá, de modo 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 el tiempo probándolo. ** - Finalmente, al expandir la tabla a una potencia de 2, agrega como máximo una comparación y, como máximo, un factor de almacenamiento de dos.
** 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 aproximadamente 0.5, y -log2 (0.5) es 1, entonces eso significa que si tomas una rama aprendes 1 bit, y si tomas la otra rama aprendes un bit, y el promedio es solo la suma de lo que aprende 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, toma 10 ramas. ¡Por eso es rápido!
Por otro lado, ¿qué pasa si su primera prueba es if (key == a[i+512) ? La probabilidad de ser verdadero es 1/1024, mientras que la probabilidad de falso es 1023/1024. Entonces, si es verdad, ¡aprendes los 10 bits! Pero si es falso aprendes -log2 (1023/1024) = .00141 bits, ¡prácticamente nada! Entonces la cantidad promedio que aprende de esa prueba es 10/1024 + .00141*1023/1024 = .0098 + .00141 = .0112 bits. Alrededor de una centésima de bit. ¡Esa prueba no está llevando su peso!
Otras personas han sugerido reorganizar su tabla, agregar un valor centinela al final o clasificarlo para proporcionar una búsqueda binaria.
Usted declara "También uso la aritmética del puntero y un ciclo for, que realiza el conteo regresivo en lugar de hacia arriba (verificando si i != 0 es más rápido que comprobar si i < 256 )".
Mi primer consejo es: deshacerse de la aritmética del puntero y la cuenta atrás. 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. Hacer malabares con punteros aritméticos y apuntadores tenderá a ofuscar las expresiones idiomáticas al compilador y hacer que genere código relacionado con lo que escribió en lugar de lo que el 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 -256 o -255 hasta cero, indexación desactivada &the_array[256] . Posiblemente cosas que ni siquiera se pueden expresar en C válida pero que coinciden con la arquitectura de la máquina que está generando.
Entonces no micro-optimizar. Simplemente está lanzando llaves en los trabajos de su optimizador. Si quieres ser inteligente, trabaja en las estructuras de datos y algoritmos, pero no micro-optimizar su expresión. Simplemente regresará para morderte, si no en el compilador / arquitectura actual, y luego en el siguiente.
En particular, usar aritmética de puntero en lugar de matrices e índices es veneno para el compilador al estar completamente al tanto de las alineaciones, ubicaciones de almacenamiento, consideraciones de alias y otras cosas, y para realizar optimizaciones como la reducción de la fuerza de la forma más adecuada para la arquitectura de la máquina.
Si el conjunto de constantes en su tabla se conoce de antemano, puede usar hashing perfecto para asegurar que solo se haga un acceso a la tabla. El hash perfecto determina una función hash que asigna cada clave interesante a una ranura única (esa tabla no siempre es densa, pero puede decidir qué tan poco denso puede permitirse una tabla, con tablas menos densas que generalmente conducen a funciones 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 querrás que sea largo y complicado porque eso compite por el tiempo, quizás mejor gastado haciendo múltiples sondeos.
El hash perfecto es un esquema de "1 sonda máxima". Uno puede generalizar la idea, con la idea de que se debe cambiar la simplicidad de la computación del código hash con el tiempo que lleva hacer las sondas k. Después de todo, el objetivo es "menos tiempo total para buscar", no hay menos sondas o la función hash más simple. Sin embargo, nunca he visto a nadie construir un algoritmo hash k-probes-max. Sospecho que uno puede hacerlo, pero es probable que sea una investigación.
Otro pensamiento: si su procesador es extremadamente rápido, la sonda a la memoria de un hash perfecto probablemente domine el tiempo de ejecución. Si el procesador no es muy rápido, entonces k> 1 sondas podrían ser prácticas.
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 el número 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 esto tiene la función hash más eficiente de velocidad (desde address === value). He leído los comentarios y soy consciente de las advertencias obvias. Sin lugar a dudas, estas advertencias limitan el rango de problemas que se pueden usar para resolver, pero, para aquellos problemas que resuelve, lo resuelve muy eficientemente.
En lugar de rechazar esta respuesta abiertamente, considérela como el punto de partida óptimo para el cual puede evolucionar mediante el uso de funciones hash para lograr un mejor equilibrio entre velocidad y rendimiento.
Suponiendo que su procesador se ejecuta a 204 MHz, que parece ser el máximo para el LPC4357, y también suponiendo que su resultado de tiempo refleja el caso promedio (la mitad de la matriz atravesada), obtenemos:
- Frecuencia de la CPU: 204 MHz
- Periodo de ciclo: 4.9 ns
- Duración en ciclos: 12.5 μs / 4.9 ns = 2551 ciclos
- Ciclos por iteración: 2551/128 = 19.9
Por lo tanto, su ciclo de búsqueda gasta alrededor de 20 ciclos por iteración. Eso no suena mal, pero supongo que para hacerlo más rápido debes mirar el conjunto.
Yo recomendaría eliminar el índice y usar una comparación de punteros, y hacer que todos los punteros sean 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;
}
Eso al menos vale la pena probarlo.
Use un conjunto de hash. Le dará O (1) tiempo de búsqueda.
El siguiente código asume que puede reservar el valor 0 como un valor ''vacío'', es decir, que no ocurre 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 esta implementación de ejemplo, el tiempo de búsqueda normalmente será muy bajo, pero en el peor de los casos puede ser hasta la cantidad de entradas almacenadas. Para una aplicación en tiempo real, puede considerar también una implementación utilizando árboles binarios, que tendrá un tiempo de búsqueda más predecible.
I''m a great fan of hashing. The problem of course is to find an efficient algorithm that is both fast and uses a minimum amount of memory (especially on an embedded processor).
If you know beforehand the values that may occur you can create a program that runs through a multitude of algorithms to find the best one - or, rather, the best parameters for your data.
I created such a program that you can read about in this post and achieved some very fast results. 16000 entries translates roughly to 2^14 or an average of 14 comparisons to find the value using a binary search. I explicitly aimed for very fast lookups - on average finding the value in <=1.5 lookups - which resulted in greater RAM requirements. I believe that with a more conservative average value (say <=3) a lot of memory could be saved. By comparison the average case for a binary search on your 256 or 1024 entries would result in an average number of comparisons of 8 and 10, respectively.
My average lookup required around 60 cycles (on a laptop with an intel i5) with a generic algorithm (utilizing one division by a variable) and 40-45 cycles with a specialized (probably utilizing a multiplication). This should translate into sub-microsecond lookup times on your MCU, depending of course on the clock frequency it executes at.
It can be real-life-tweaked further if the entry array keeps track of how many times an entry was accessed. If the entry array is sorted from most to least accessed before the indeces are computed then it''ll find the most commonly occuring values with a single comparison.
This is more like an addendum than an answer.
I''ve had a simillar case in the past, but my array was constant over a considerable number of searches.
In half of them, the searched value was NOT present in array. Then I realized I could apply a "filter" before doing any search.
This "filter" is just a simple integer number, calculated ONCE and used in each search.
It''s in java, but it''s pretty simple:
binaryfilter = 0;
for (int i = 0; i < array.length; i++)
{
// just apply "Binary OR Operator" over values.
binaryfilter = binaryfilter | array[i];
}
So, before do a binary search, I check 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 ...
}
You can use a ''better'' hash algorithm, but this can be very fast, specially for large numbers. May be this could save you even more cycles.