¿La forma más rápida de calcular la longitud decimal de un entero? (.NET)

Question

Tengo un código que hace muchas comparaciones de enteros de 64 bits, sin embargo, debe tener en cuenta la longitud del número, como si estuviera formateado como una cadena. No puedo cambiar el código de llamada, solo la función.

La forma más fácil (. Además .ToString() Longitud) es:

(int)Math.Truncate(Math.Log10(x)) + 1; 

Sin embargo que realiza bastante mal. Desde mi aplicación sólo envía valores positivos, y las longitudes son más bien distribuido uniformemente entre 2 y 9 (con algún sesgo hacia 9), I precalculadas los valores y tener si declaraciones:

static int getLen(long x) { 
    if (x < 1000000) { 
     if (x < 100) return 2; 
     if (x < 1000) return 3; 
     if (x < 10000) return 4; 
     if (x < 100000) return 5; 
     return 6; 
    } else { 
     if (x < 10000000) return 7; 
     if (x < 100000000) return 8; 
     if (x < 1000000000) return 9; 
     return (int)Math.Truncate(Math.Log10(x)) + 1; // Very uncommon 
    } 
} 

Esto permite que la longitud pueden calcular con un promedio de 4 comparaciones.

Entonces, ¿hay otros trucos que pueda usar para hacer que esta función sea más rápida?

Editar: Esto se ejecutará como código de 32 bits (Silverlight).

Actualización:

Me tomó la sugerencia de Norman y cambió los ifs un poco para dar lugar a un promedio de sólo 3 compara. Según el comentario de Sean, eliminé Math.Truncate. Juntos, esto aumentó las cosas alrededor del 10%. ¡Gracias!

Answer 1

dos sugerencias:

1. perfil y poner en primer lugar los casos comunes.
2. Haga una búsqueda binaria para minimizar el número de comparaciones en el peor de los casos. Puedes elegir entre 8 alternativas usando exactamente tres comparaciones.

Esta combinación probablemente no le compre mucho a menos que la distribución sea muy sesgada.

Answer 2

no estoy seguro si esto es más rápido o no .. pero siempre se puede contar ...

static int getLen(long x) { 
    int len = 1; 
    while (x > 0) { 
     x = x/10; 
     len++ 
    }; 
    return len 
}

Answer 3

¿Qué quiere decir por la longitud? ¿Número de ceros o todo? This hace cifras significativas, pero se entiende la idea general

public static string SpecialFormat(int v, int sf) 
{ 
    int k = (int)Math.Pow(10, (int)(Math.Log10(v) + 1 - sf)); 
    int v2 = ((v + k/2)/k) * k; 
    return v2.ToString("0,0"); 
} 

Answer 4

Aquí hay una versión binaria de búsqueda, que he probado, que trabaja en enteros de 64 bits utilizando exactamente cinco comparaciones cada vez.

int base10len(uint64_t n) { 
    int len = 0; 
    /* n < 10^32 */ 
    if (n >= 10000000000000000ULL) { n /= 10000000000000000ULL; len += 16; } 
    /* n < 10^16 */ 
    if (n >= 100000000) { n /= 100000000; len += 8; } 
    /* n < 100000000 = 10^8 */ 
    if (n >= 10000) { n /= 10000; len += 4; } 
    /* n < 10000 */ 
    if (n >= 100) { n /= 100; len += 2; } 
    /* n < 100 */ 
    if (n >= 10) { return len + 2; } 
    else   { return len + 1; } 
} 

Dudo que esto vaya a ser más rápido que lo que ya está haciendo. Pero es predecible

Answer 5

Ha comentado en el código que 10 dígitos o más es muy poco común, por lo que su solución original no es malo

Answer 6

Hice algunas pruebas, y esto parece ser 2-4 veces más rápido que el código que tiene ahora :

static int getLen(long x) { 
    int len = 1; 
    while (x > 9999) { 
     x /= 10000; 
     len += 4; 
    } 
    while (x > 99) { 
     x /= 100; 
     len += 2; 
    } 
    if (x > 9) len++; 
    return len; 
} 

Editar:
Aquí está una versión que utiliza más operaciones Int32, que debería funcionar mejor si usted no tiene una aplicación de 64 bits:

static int getLen(long x) { 
    int len = 1; 
    while (x > 99999999) { 
     x /= 100000000; 
     len += 8; 
    } 
    int y = (int)x; 
    while (y > 999) { 
     y /= 1000; 
     len += 3; 
    } 
    while (y > 9) { 
     y /= 10; 
     len ++; 
    } 
    return len; 
} 

Answer 7

no he probado esto, pero el cambio de la ley de base dice:

Log10 (x) = log2 (x)/log2 (10)

log2 debería ser un poco más rápido que Log10 si se implementa derecho.

Answer 8

De Sean Anderson de Bit Twiddling Hacks:

base de Find registro de número entero 10 de un número entero

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of 
int r;   // result goes here 
int t;   // temporary 

static unsigned int const PowersOf10[] = 
    {1, 10, 100, 1000, 10000, 100000, 
    1000000, 10000000, 100000000, 1000000000}; 

t = (IntegerLogBase2(v) + 1) * 1233 >> 12; // (use a lg2 method from above) 
r = t - (v < PowersOf10[t]); 

La base de registro de número entero 10 se calcula por primero usando una de las técnicas anteriores para encontrar la base de registro 2. Por la relación log10 (v) = log2 (v)/ log2 (10), tenemos que multiplicarla por 1/log2 (10), que es aproximadamente 1233/4096, o 1233 seguido de un desplazamiento de 12. Se necesita agregar uno porque el IntegerLogBase2 redondea hacia abajo. Finalmente, como el valor t es solo una aproximación que puede estar desactivada en en uno, el valor exacto se encuentra en restando el resultado de v < PowersOf10 [t].

Este método realiza 6 operaciones más que IntegerLogBase2. Puede ser acelerado hasta (en máquinas con memoria rápida acceso) mediante la modificación de la base de registro Método 2 búsqueda en tabla anterior para que las entradas tienen lo que se calcula para t (es decir, antes de añadir, -mulitply, y -cambio). Hacerlo requeriría un total de solo 9 operaciones para encontrar la base de registro 10 de , suponiendo que se usaron 4 tablas ( ) (una para cada byte de v).

En cuanto al cálculo de IntegerLogBase2, hay varias alternativas presentadas en esa página. Es una gran referencia para todo tipo de operaciones enteras altamente optimizadas.

Una variante de su versión también está allí, excepto que asume los valores (en lugar de la base de registro 10 de los valores) están distribuidos de manera uniforme, y por lo tanto hace una búsqueda exponencialmente ordenado:

encontrar la base de registro de número entero 10 de un número entero de la manera obvia

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of 
int r;   // result goes here 

r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 : 
    (v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 : 
    (v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0; 

Este método funciona bien cuando la entrada se distribuye uniformemente sobre 32 bits valores PORQUE 76% de las entradas a re atrapado por la primera comparación, 21% son atrapados por la segunda comparación, 2% son atrapados por el tercero, y así sucesivamente (cortando el restante por 90% con cada comparación). Como resultado, se necesitan menos de 2.6 operaciones en promedio.

Answer 9

static int getDigitCount(int x) 
    { 
    int digits = (x < 0) ? 2 : 1; // '0' has one digit,negative needs space for sign 
    while(x > 9) // after '9' need more 
     { 
     x /= 10; // divide and conquer 
     digits++; 
     } 
    return digits; 
    } 

Answer 10

Es una manera sencilla.

private static int GetDigitCount(int number) 
{ 
    int digit = 0; 

    number = Math.Abs(number); 

    while ((int)Math.Pow(10, digit++) <= number); 

    return digit - 1; 
} 

Si el número no está firmado int, entonces "Math.Abs ​​(number)" no es necesario.

Hice el método de extensión con todos los tipos numéricos.

private static int GetDigitCount(dynamic number) 
    { 
     dynamic digit = 0; 

     number = Math.Abs(number); 

     while ((dynamic)Math.Pow(10, digit++) <= number) 
      ; 

     return digit - 1; 
    } 

    public static int GetDigit(this int number) 
    { 
     return GetDigitCount(number); 
    } 

    public static int GetDigit(this long number) 
    { 
     return GetDigitCount(number); 
    } 

continuación, se utiliza este.

int x = 100; 
int digit = x.GetDigit(); // 3 expected.