c++ - library - ¿Cómo evaluar cero establece rápido?

sort function

Question

Este reciente código de publicación de golf le preguntó a las posibilidades de rápida implementación en C lo siguiente (suponiendo que n es un entero sin signo):

if (n==6 || n==8 || n==10 || n==12 || n==14 || n==16 || n==18 || n==20)

Una posible simplificación es observar que los números a[]={6,8,10,12,14,16,18,20} forman una progresión aritmética , por lo que se cambia el rango y luego se utilizan algunos trucos en forma de bits.

if (((n - 6) & 14) + 6 == n)

conduce a una implementación más corta (y probablemente más eficiente), según la answered de John Bollinger.

Ahora me pregunto cuál es la implementación análogamente elegante (y con suerte igualmente eficiente) de

if (n==3 || n==5 || n==11 || n==29 || n==83 || n==245 || n==731 || n==2189)

Sugerencia: esta vez los números a[k] forman una progresión geométrica : a[k]=2+3^k .

Supongo que, en el caso general, no se puede hacer nada mejor que ordenar los números a[k] y luego hacer una búsqueda logarítmica para probar si n es un miembro de la matriz ordenada.

Answer 1

Sugerencia: esta vez los números a[k] forman una progresión geométrica: a[k]=2+3^k .

n = 2 + 3^k
n - 2 = 3^k

(n - 2) / 3^k = 1
(n - 2) % 3^k = 0

k = 0 ~ n-2 = 3^0 = 1, n = 3
k = 1 ~ n-2 = 3^1 = 3, n = 5
k = 2 ~ n-2 = 3^3 = 9, n = 11

if (n > 2 && isPow(n-2, 3))

con la definición de función isPow(x,y)

bool isPow(unsigned long x, unsigned int y)
{
    while (x % y == 0)
    {
        x /= y;
    }

    return x == 1;
}

n = n  ~ n-2 = 3^k/3 = 3^(k-1)/3 = .. = 3^1/3 = 1%3 != 0
n = 11 ~ n-2 = 9/3 = 3/3 = 1%3 != 0
n = 5  ~ n-2 = 3/3 = 1%3 != 0
n = 3  ~ n-2 = 1%3 != 0

De manera similar, podemos deducir k ..

int k = findK(n-2, 3);

int findK(unsigned long x, unsigned int y)
{
    unsigned int k = 0;

    while (x % y == 0)
    {
        x /= y;
        k++;
    }

    if (x == 1) return k;
    else return (-1);
}

n - 2 = 3 * 3^(k-1)       for k > 0
(n - 2) / 3 = 3^(k-1)
(n - 2) / 3 / 3 = 3^(k-2)
(n - 2) / 3 / 3 / 3 = 3^(k-3)
(n - 2) / 3 / 3 / 3 / 3 = 3^(k-4)
..
(n - 2) / 3 / 3 / ..i times = 3^(k-i)
..
(n - 2) / 3 / 3 / ..k times = 3^0 = 1

Answer 2

Esto es lo que se me ocurrió:

bool b;
if (n >= 3 && n <= 2189)
{
    double d = std::log(n - 2)/std::log(3); // log₃(n - 2)
    b = std::trunc(d) == d; // Checks to see if this is an integer
    // If ‘b’ then ‘n == a[log₃(n - 2)]’
}
else b = false;

if (b)
{
    // your code
}

Como el número n es un número entero pequeño, las imprecisiones de coma flotante no deberían ser un problema.

Por supuesto, no será tan rápido como la aritmética de enteros, y no se ajusta cómodamente a una expresión, probablemente sea más rápido que algún tipo de búsqueda de matriz, especialmente si aumenta el valor máximo de n .

EDITAR He probado mi código (sin optimizaciones habilitadas) y en promedio (para todo n menor que o igual a 2189) mi versión tomó 185.849 ns cuando el || la versión tomó 116.546 ns, (ejecutar mi programa varias veces arrojó resultados similares) por lo que no es más rápido. También por alguna extraña razón, establece b como false cuando n == 245 , (debería ser cierto).

Answer 3

Esto es muy similar al reconocimiento de una potencia de tres , y puede adaptar, por ejemplo, esta solución :

bool test(unsigned x) {
    x -= 2;
    if (x > 2187)
        return 0;
    if (x > 243)
        x *= 0xd2b3183b;
    return x <= 243 && ((x * 0x71c5) & 0x5145) == 0x5145;
}

Con el rango dado, esto se puede simplificar aún más (encontrado por la fuerza bruta):

bool test2(unsigned x) {
  x -= 2;
  return x <= 2187 && (((x * 0x4be55) & 0xd2514105) == 5);
}

Answer 4

Se ha encontrado un problema similar en una publicación relacionada: puede usar std::find

bool found = (std::find(my_var.begin(), my_var.end(), my_variable) != my_var.end());
// my_var is a list of elements.

(asegúrese de incluir <algorithm>).

Para este tipo de cosas, en el 99% de los casos, hay una biblioteca que hace el trabajo por usted.

Answer 5

Una forma muy eficiente de hacer este tipo de cosas es con un conjunto, especialmente un conjunto unordered_set . Como una tabla hash, la búsqueda es constante promedio, peor lineal. También es mucho más elegante que una serie de condiciones y escalas.

Simplemente inserte los valores que desea comparar y count el valor en el conjunto. Si se encuentra, es uno de los valores probados.

std::unordered_set< int > values;
values.insert( 3 );
values.insert( 5 );
values.insert( 11 );
values.insert( 29 );
values.insert( 83 );
values.insert( 245 );
values.insert( 731 );
values.insert( 2189 );

...

if( values.count( input ) )
    std::cout << "Value is in set./n";
else
    std::cout << "Value is NOT in set./n";

Answer 6

if ((n > 2) && (2187 % (n - 2) == 0))

Comprueba si (n - 2) es una potencia de 3 y es menor o igual a 2187 (3 a la potencia de 7)

Como generalización, para verificar si un entero sin signo n es una potencia del número primo k , puede verificar si n divide la mayor potencia de k que puede almacenarse en un entero sin signo.