¿Manera de obtener la cantidad de dígitos en un int?
¿Existe una forma más sencilla de obtener el número de dígitos en un int que este método?
int numDigits = String.valueOf(1000).length();
Su solución basada en String está perfectamente bien, no tiene nada de "desordenado". Tienes que darte cuenta de que matemáticamente los números no tienen longitud ni dígitos. La longitud y los dígitos son propiedades de una representación física de un número en una base específica, es decir, una cadena.
Una solución basada en logaritmos hace (algunas de) las mismas cosas que la basada en cadenas hace internamente, y probablemente lo hace (insignificantemente) más rápido porque solo produce la longitud e ignora los dígitos. Pero en realidad no lo consideraría más claro en su intención, y ese es el factor más importante.
El logaritmo es tu amigo:
int n = 1000;
int length = (int)(Math.log10(n)+1);
NB: sólo válido para n > 0.
El enfoque más rápido: divide y vencerás.
Suponiendo que su rango es de 0 a MAX_INT, entonces tiene de 1 a 10 dígitos. Puedes abordar este intervalo usando divide y vencerás, con hasta 4 comparaciones por cada entrada. Primero, divide [1..10] en [1..5] y [6..10] con una comparación, y luego cada intervalo de longitud 5 se divide usando una comparación en un intervalo de longitud 3 y un intervalo de longitud 2. El intervalo de longitud 2 requiere una comparación más (un total de 3 comparaciones), el intervalo de longitud 3 se puede dividir en un intervalo de longitud 1 (solución) y un intervalo de longitud 2. Entonces, necesitas 3 o 4 comparaciones.
Sin divisiones, sin operaciones de punto flotante, sin costosos logaritmos, sólo comparaciones de números enteros.
Código (largo pero rápido):
if (n < 100000) { // 1 to 5
if (n < 100) { // 1 or 2
if (n < 10) return 1;
return 2;
}
else { // 3, 4 or 5
if (n < 1000) return 3;
if (n < 10000) return 4;
return 5;
}
}
else { // 6 to 7
if (n < 10000000) { // 6 or 7
if (n < 1000000) return 6;
return 7;
}
else { // 8, 9 or 10
if (n < 100000000) return 8;
if (n < 1000000000) return 9;
return 10;
}
}
Prueba comparativa (después del calentamiento de JVM): consulte el código a continuación para ver cómo se ejecutó la prueba comparativa:
- método de línea base (con String.length): 2145ms
- Método log10: 711 ms = 3,02 veces más rápido que el valor inicial
- división repetida: 2797 ms = 0,77 veces más rápido que el valor inicial
- divide y vencerás: 74 ms = 28,99
veces más rápido que el valor inicial
Código completo:
public static void main(String[] args) throws Exception {
// validate methods:
for (int i = 0; i < 1000; i++)
if (method1(i) != method2(i))
System.out.println(i);
for (int i = 0; i < 1000; i++)
if (method1(i) != method3(i))
System.out.println(i + " " + method1(i) + " " + method3(i));
for (int i = 333; i < 2000000000; i += 1000)
if (method1(i) != method3(i))
System.out.println(i + " " + method1(i) + " " + method3(i));
for (int i = 0; i < 1000; i++)
if (method1(i) != method4(i))
System.out.println(i + " " + method1(i) + " " + method4(i));
for (int i = 333; i < 2000000000; i += 1000)
if (method1(i) != method4(i))
System.out.println(i + " " + method1(i) + " " + method4(i));
// work-up the JVM - make sure everything will be run in hot-spot mode
allMethod1();
allMethod2();
allMethod3();
allMethod4();
// run benchmark
Chronometer c;
c = new Chronometer(true);
allMethod1();
c.stop();
long baseline = c.getValue();
System.out.println(c);
c = new Chronometer(true);
allMethod2();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
c = new Chronometer(true);
allMethod3();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
c = new Chronometer(true);
allMethod4();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times as fast as baseline");
}
private static int method1(int n) {
return Integer.toString(n).length();
}
private static int method2(int n) {
if (n == 0)
return 1;
return (int)(Math.log10(n) + 1);
}
private static int method3(int n) {
if (n == 0)
return 1;
int l;
for (l = 0 ; n > 0 ;++l)
n /= 10;
return l;
}
private static int method4(int n) {
if (n < 100000) {
// 5 or less
if (n < 100) {
// 1 or 2
if (n < 10)
return 1;
else
return 2;
} else {
// 3 or 4 or 5
if (n < 1000)
return 3;
else {
// 4 or 5
if (n < 10000)
return 4;
else
return 5;
}
}
} else {
// 6 or more
if (n < 10000000) {
// 6 or 7
if (n < 1000000)
return 6;
else
return 7;
} else {
// 8 to 10
if (n < 100000000)
return 8;
else {
// 9 or 10
if (n < 1000000000)
return 9;
else
return 10;
}
}
}
}
private static int allMethod1() {
int x = 0;
for (int i = 0; i < 1000; i++)
x = method1(i);
for (int i = 1000; i < 100000; i += 10)
x = method1(i);
for (int i = 100000; i < 1000000; i += 100)
x = method1(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method1(i);
return x;
}
private static int allMethod2() {
int x = 0;
for (int i = 0; i < 1000; i++)
x = method2(i);
for (int i = 1000; i < 100000; i += 10)
x = method2(i);
for (int i = 100000; i < 1000000; i += 100)
x = method2(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method2(i);
return x;
}
private static int allMethod3() {
int x = 0;
for (int i = 0; i < 1000; i++)
x = method3(i);
for (int i = 1000; i < 100000; i += 10)
x = method3(i);
for (int i = 100000; i < 1000000; i += 100)
x = method3(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method3(i);
return x;
}
private static int allMethod4() {
int x = 0;
for (int i = 0; i < 1000; i++)
x = method4(i);
for (int i = 1000; i < 100000; i += 10)
x = method4(i);
for (int i = 100000; i < 1000000; i += 100)
x = method4(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method4(i);
return x;
}
Nuevamente, punto de referencia:
- método de línea base (con String.length): 2145ms
- Método log10: 711 ms = 3,02 veces más rápido que el valor inicial
- división repetida: 2797 ms = 0,77 veces más rápido que el valor inicial
- divide y vencerás: 74 ms = 28,99 veces más rápido que el valor inicial
Editar
Después de escribir el punto de referencia, eché un vistazo a Integer.toString desde Java 6 y descubrí que usa:
final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999, Integer.MAX_VALUE };
// Requires positive x
static int stringSize(int x) {
for (int i=0; ; i++)
if (x <= sizeTable[i])
return i+1;
}
Lo comparé con mi solución de divide y vencerás:
- divide y vencerás: 104 ms
- Solución Java 6: iterar y comparar: 406 ms
La mía es aproximadamente 4 veces más rápida que la solución Java 6.
