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

¿Existe una forma más rápida que x >= start && x <= enden 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 determinado.

ACTUALIZACIÓN : Después de probar la respuesta aceptada , obtuve un orden de magnitud de aceleración en la línea de código por hacerlo de la x >= start && x <= endmanera normal .

ACTUALIZACIÓN : Aquí está el código anterior y anterior 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.end && 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 sorprendente cómo reducir o eliminar la ramificación puede proporcionar una velocidad tan dramática.

Hay un viejo truco para hacer esto con solo una comparación / rama. Si realmente mejorará la velocidad puede ser cuestionable, e incluso si lo hace, probablemente sea demasiado poco para darse cuenta o preocuparse, pero cuando solo 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 la forma en que se ven los mismos bits.

Tenga en cuenta que, en un caso típico, puede realizar un cálculo previo upper-lowerfuera de un ciclo (presunto), por lo que normalmente no contribuye con un tiempo significativo. Junto con la reducción del número de instrucciones de ramificación, esto también (generalmente) mejora la predicción de ramificación. En este caso, se toma la misma rama si el número está por debajo del extremo inferior o por encima del extremo 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 se traduce numbery el intervalo al punto de origen y comprueba si numberestá en el intervalo [0, D], dónde D = upper - lower. Si está numberpor debajo del límite inferior: negativo , y si está por encima del límite superior: mayor queD .

Es raro poder hacer optimizaciones significativas para codificar a una escala tan pequeña. Grandes ganancias de rendimiento provienen de observar y modificar el código desde un nivel superior. Es posible que pueda eliminar la necesidad de la prueba de rango por completo, o solo hacer O (n) de ellos en lugar de O (n ^ 2). Es posible que pueda reordenar las pruebas para que siempre se implique un lado de la desigualdad. Incluso si el algoritmo es ideal, es más probable que obtenga ganancias cuando vea cómo este código hace la prueba de rango 10 millones de veces y encuentra una manera de agruparlas y usar SSE para hacer muchas pruebas en paralelo.

Depende de cuántas veces desee realizar la prueba con los mismos datos.

Si está realizando la prueba una sola vez, probablemente no haya una manera significativa de acelerar el algoritmo.

Si está haciendo esto para un conjunto de valores muy finito, podría crear una tabla de búsqueda. Realizar la indexación puede ser más costoso, pero si puede ajustar toda la tabla en la memoria 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, por lo que considera todas las instancias en las que start = Nal mismo tiempo, el tamaño del conjunto de trabajo se reduce a 128^2 = 16432bytes, lo que debería encajar bien en la mayoría de las memorias caché modernas.

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

Esta respuesta es informar sobre una prueba realizada con la respuesta aceptada. ¡Realicé una prueba de rango cerrado en un vector grande 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<chrono::system_clock> 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<double> elapsed_s1 = end - start;

en comparación con lo siguiente, que es la respuesta aceptada arriba:

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

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

Para cualquier comprobación de rango variable:

if (x >= minx && x <= maxx) ...

Es más rápido usar la operación de bits:

if ( ((x - minx) | (maxx - x)) >= 0) ...

Esto reducirá dos ramas en una.

Si te importa el tipo seguro:

if ((int32_t)(((uint32_t)x - (uint32_t)minx) | ((uint32_t)maxx - (uint32_t)x)) > = 0) ...

Puede combinar más comprobaciones de rango variable juntas:

if (( (x - minx) | (maxx - x) | (y - miny) | (maxy - y) ) >= 0) ...

Esto reducirá 4 ramas en 1.

Es 3.4 veces más rápido que el anterior en gcc:

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

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