library - libreria eigen c++

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

Question

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

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

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

ACTUALIZACIÓN : Aquí está el código posterior 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 espectacular.

Answer 1

¿No es posible realizar simplemente una operación bitwise 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 extremo será un dolor, ya que usted quiere una comparación inclusiva.

Answer 2

Depende de cuántas veces desee realizar la prueba sobre 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, entonces podría crear una tabla de búsqueda. La realización de la indexación puede ser más costosa, pero si puede ajustar toda la tabla en la memoria caché, puede eliminar todas las ramificaciones del código, lo que debería acelerar el proceso.

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 donde start = N a la vez, entonces el tamaño del conjunto de trabajo se reduce a 128^2 = 16432 bytes, lo que debería encajar bien en la mayoría de las cachés modernas.

Aún tendría que hacer una prueba comparativa del código real para ver si una tabla de búsqueda sin sucursales es suficientemente más rápida que las comparaciones obvias.

Answer 3

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

Answer 4

Esta respuesta es para 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 anteriormente. La prueba se realizó en HP Pavilion g6 (AMD A6-3400APU con 6GB de ram. Aquí está el código principal utilizado para la prueba:

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;

Comparado 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;
}

Preste 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!

Answer 5

Hay un viejo truco para hacer esto con una sola comparación / rama. Si realmente mejorará la velocidad puede ser cuestionable, e incluso si lo hace, probablemente sea muy poco para darse cuenta o preocuparse, pero cuando solo está comenzando con dos comparaciones, las posibilidades de una gran mejora son bastante remotas. El código se ve como:

// 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 moderna y típica (es decir, cualquier cosa que use un complemento de dos), 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 de la parte upper-lower fuera de un bucle (presumiblemente), de modo que normalmente no contribuye un tiempo significativo. Junto con la reducción del número de instrucciones de rama, esto también (generalmente) mejora la predicción de rama. 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 no firmado, 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