La forma más rápida de determinar si un entero está entre dos enteros (inclusive) con conjuntos de valores conocidos

¿Hay una manera más rápida que x >= start && x <= end en C o C ++ para probar si un entero está entre dos enteros?

ACTUALIZACIÓN : Mi plataforma específica es iOS. Esto es parte de una función de desenfoque de cuadro que restringe los píxeles a un círculo en un cuadrado dado.

ACTUALIZACIÓN : Después de intentar la respuesta aceptada , obtuve una aceleración de orden de magnitud en la línea de código sobre hacerlo de la manera normal x >= start && x <= end .

ACTUALIZACIÓN : Aquí está el código de antes y después con el ensamblador de XCode:

NUEVA MANERA

 // diff = (end - start) + 1 #define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff) Ltmp1313: ldr r0, [sp, #176] @ 4-byte Reload ldr r1, [sp, #164] @ 4-byte Reload ldr r0, [r0] ldr r1, [r1] sub.w r0, r9, r0 cmp r0, r1 blo LBB44_30 

VIEJA FORMA

 #define POINT_IN_RANGE_AND_INCREMENT(p, range) (p = range.start) Ltmp1301: ldr r1, [sp, #172] @ 4-byte Reload ldr r1, [r1] cmp r0, r1 bls LBB44_32 mov r6, r0 b LBB44_33 LBB44_32: ldr r1, [sp, #188] @ 4-byte Reload adds r6, r0, #1 Ltmp1302: ldr r1, [r1] cmp r0, r1 bhs LBB44_36 

Es bastante sorprendente cómo reducir o eliminar las ramificaciones puede proporcionar una velocidad tan dramática.

Hay un viejo truco para hacer esto con solo una comparación / twig. Si esto realmente puede mejorar la velocidad puede ser cuestionable, e incluso si lo hace, es probable que sea demasiado poco para darse cuenta o preocuparse, pero cuando solo se comienza con dos comparaciones, las posibilidades de una gran mejora son bastante remotas. El código se ve así:

 // use a < for an inclusive lower bound and exclusive upper bound // use <= for an inclusive lower bound and inclusive upper bound // alternatively, if the upper bound is inclusive and you can pre-calculate // upper-lower, simply add + 1 to upper-lower and use the < operator. if ((unsigned)(number-lower) <= (upper-lower)) in_range(number); 

Con una computadora típica y moderna (es decir, cualquier cosa que use dos complementos), la conversión a unsigned es realmente un nop, solo un cambio en cómo se ven los mismos bits.

Tenga en cuenta que en un caso típico, puede precomputar la parte upper-lower fuera de un bucle (supuesto), por lo que normalmente no contribuye con un tiempo significativo. Además de reducir el número de instrucciones de bifurcación, esto también (generalmente) mejora la predicción de bifurcación. En este caso, se toma la misma bifurcación si el número está por debajo del extremo inferior o por encima del límite superior del rango.

En cuanto a cómo funciona esto, la idea básica es bastante simple: un número negativo, cuando se ve como un número sin signo, será más grande que cualquier cosa que comenzó como un número positivo.

En la práctica, este método traduce el number y el intervalo al punto de origen y verifica si el number está en el intervalo [0, D] , donde D = upper - lower . Si el number por debajo del límite inferior: negativo , y si está por encima del límite superior: mayor que D

Depende de cuántas veces quiera realizar la prueba sobre la misma información.

Si realiza la prueba una sola vez, probablemente no haya una forma significativa de acelerar el algoritmo.

Si está haciendo esto para un conjunto de valores muy finitos, entonces podría crear una tabla de búsqueda. Realizar la indexación puede ser más costoso, pero si puede colocar toda la tabla en caché, puede eliminar todas las ramificaciones del código, lo que debería acelerar las cosas.

Para sus datos, la tabla de búsqueda sería 128 ^ 3 = 2,097,152. Si puede controlar una de las tres variables para que considere todas las instancias donde start = N a la vez, entonces el tamaño del conjunto de trabajo desciende a 128^2 = 16432 bytes, lo que debería encajar bien en la mayoría de las cachés modernas.

Todavía tendría que comparar el código real para ver si una tabla de búsqueda sin sucursales es suficientemente más rápida que las comparaciones obvias.

Es raro poder hacer optimizaciones significativas para codificar en una escala tan pequeña. Las grandes ganancias de rendimiento provienen de observar y modificar el código desde un nivel superior. Puede eliminar por completo la necesidad de la prueba de rango, o solo hacer O (n) de ellos en lugar de O (n ^ 2). Es posible que pueda volver a ordenar las pruebas para que siempre quede implícito un lado de la desigualdad. Incluso si el algoritmo es ideal, es más probable que surjan ganancias cuando vea cómo este código hace la prueba de rango 10 millones de veces y encuentra una forma de combinarlas y usar SSE para realizar muchas pruebas en paralelo.

Esta respuesta es para informar sobre una prueba realizada con la respuesta aceptada. Realicé una prueba de rango cerrado en un gran vector de entero aleatorio ordenado y para mi sorpresa el método básico de (bajo <= num && num <= alto) es de hecho más rápido que la respuesta aceptada arriba. La prueba se realizó en HP Pavilion g6 (AMD A6-3400APU con 6 GB de ram. Aquí está el código central utilizado para las pruebas:

 int num = rand(); // num to compare in consecutive ranges. chrono::time_point start, end; auto start = chrono::system_clock::now(); int inBetween1{ 0 }; for (int i = 1; i < MaxNum; ++i) { if (randVec[i - 1] <= num && num <= randVec[i]) ++inBetween1; } auto end = chrono::system_clock::now(); chrono::duration elapsed_s1 = end - start; 

en comparación con el siguiente, que es la respuesta aceptada anteriormente:

 int inBetween2{ 0 }; for (int i = 1; i < MaxNum; ++i) { if (static_cast(num - randVec[i - 1]) <= (randVec[i] - randVec[i - 1])) ++inBetween2; } 

Preste atención que randVec es un vector ordenado. Para cualquier tamaño de MaxNum, ¡el primer método supera al segundo en mi máquina!

¿No es posible simplemente realizar una operación bit a bit en el entero?

Como tiene que estar entre 0 y 128, si el octavo bit está establecido (2 ^ 7) es 128 o más. Sin embargo, el caso límite será doloroso, ya que desea una comparación inclusiva.