Las respuestas que la gente te da son correctas ... te dan la longitud de tu int sin convertirlo en una cadena ... pero ¿por qué no quieres convertirlo en una cadena? ¿Es una cosa de velocidad? Si es así, no estoy convencido de que estos métodos serán más rápido ... es posible que desee hacer algunas pruebas (o incluso decidir si importa.)
Beska
3
@ptomli los dígitos hexadecimales siguen siendo dígitos, solo en un sistema base diferente.
Mark Pim
2
@Ptomli Claro, pero tanto en la función Integer.toString como en la conversación general, el decimal es el valor predeterminado. Cuando el banco me dice: "Escriba el monto de su cheque en este cuadro", no les pregunto si debo escribirlo en decimal, hexadecimal u octal. Asumimos decimal a menos que se especifique lo contrario o se solicite por contexto.
Jay
Respuestas:
349
Su solución basada en cadenas está perfectamente bien, no hay nada "descuidado" al respecto. Tienes que darte cuenta de que matemáticamente, los números no tienen una longitud, ni tienen 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 logaritmo hace (algunas de) las mismas cosas que la basada en String 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.
+1 para considerar la intención del código al elegir una forma de resolver un problema
pupeno
55
Punto de datos: en mi máquina, el método de registro parece ejecutarse un poco menos del doble de rápido que los métodos de longitud de cadena. No llamaría a eso insignificante si el método se llama mucho o en una sección de código de tiempo crítico.
CPerkins el
1
Vea mi prueba de unidad de referencia a continuación (que también puede ser defectuosa, no soy un experto de referencia). En un gran número de carreras (100 000 000), la velocidad es de 11 a 8 segundos en mi máquina, apenas el doble de rápido.
Jean
55
@CPerkins. Optimización prematura. Conoces el spiel.
Michael Borgwardt
11
Una adición (bastante tardía): puede que no funcione correctamente para valores negativos, dependiendo de si espera que el "-" sea un dígito o no. Math.abs()Sin embargo, agregar arreglará esto.
¿Y es esto más rápido o mejor que usar mi variante?
Primero
+1 Me ganaste por un segundo, y tu respuesta fue correcta, donde la mía estaba ligeramente apagada. Sin embargo, tenga en cuenta que el compilador se quejará debido a un reparto perdido en int
Dirk
2
@ Tom ¿Por qué asumirías que es caro? Se podría suponer que el coprocesador matemático lo ejecutaría, por lo que podría estar cerca de la velocidad de una adición. Incluso si Java no usa el coprocesador ahora, es una buena suposición de que podría ... (Ignoraremos su implicación aún más inculta de que Java es lento porque probablemente no le interesen las pruebas, o si fueras, irías a shootout.alioth.debian.org y lo descubrirías por ti mismo)
Bill K
8
Funciona ... a menos que el valor que esté comprobando = 0, lo que le dará resultados impares (-2147483647). Math.log10 API: "Si el argumento es cero positivo o cero negativo, entonces el resultado es infinito negativo".
mujimu
2
+1 Presentar un método que no implique asignaciones de memoria de objetos, que es imprescindible para maximizar la reutilización para evitar colecciones de GC.
Michael Wojcik
159
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. Puede acercarse a este intervalo utilizando 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 que divide mediante una comparación en un intervalo de longitud 3 y uno de longitud 2. El intervalo de longitud 2 requiere una comparación más (total 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 coma flotante, sin costosos logaritmos, solo comparaciones enteras.
Código (largo pero rápido):
if(n <100000){// 5 or lessif(n <100){// 1 or 2if(n <10)return1;elsereturn2;}else{// 3 or 4 or 5if(n <1000)return3;else{// 4 or 5if(n <10000)return4;elsereturn5;}}}else{// 6 or moreif(n <10000000){// 6 or 7if(n <1000000)return6;elsereturn7;}else{// 8 to 10if(n <100000000)return8;else{// 9 or 10if(n <1000000000)return9;elsereturn10;}}}
Punto de referencia (después del calentamiento de JVM): consulte el código a continuación para ver cómo se ejecutó el punto de referencia:
método de línea de base (con String.length): 2145 ms
Método log10: 711ms = 3.02 veces más rápido que la línea de base
división repetida: 2797 ms = 0,77 veces más rápido que la línea de base
divide y vencerás: 74 ms = 28,99
veces más rápido que la línea de base
Código completo:
publicstaticvoid main(String[] args)throwsException{// 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 benchmarkChronometer c;
c =newChronometer(true);
allMethod1();
c.stop();long baseline = c.getValue();System.out.println(c);
c =newChronometer(true);
allMethod2();
c.stop();System.out.println(c +" = "+StringTools.formatDouble((double)baseline / c.getValue(),"0.00")+" times as fast as baseline");
c =newChronometer(true);
allMethod3();
c.stop();System.out.println(c +" = "+StringTools.formatDouble((double)baseline / c.getValue(),"0.00")+" times as fast as baseline");
c =newChronometer(true);
allMethod4();
c.stop();System.out.println(c +" = "+StringTools.formatDouble((double)baseline / c.getValue(),"0.00")+" times as fast as baseline");}privatestaticint method1(int n){returnInteger.toString(n).length();}privatestaticint method2(int n){if(n ==0)return1;return(int)(Math.log10(n)+1);}privatestaticint method3(int n){if(n ==0)return1;int l;for(l =0; n >0;++l)
n /=10;return l;}privatestaticint method4(int n){if(n <100000){// 5 or lessif(n <100){// 1 or 2if(n <10)return1;elsereturn2;}else{// 3 or 4 or 5if(n <1000)return3;else{// 4 or 5if(n <10000)return4;elsereturn5;}}}else{// 6 or moreif(n <10000000){// 6 or 7if(n <1000000)return6;elsereturn7;}else{// 8 to 10if(n <100000000)return8;else{// 9 or 10if(n <1000000000)return9;elsereturn10;}}}}privatestaticint 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;}privatestaticint 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;}privatestaticint 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;}privatestaticint 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;}
De nuevo, punto de referencia:
método de línea de base (con String.length): 2145 ms
Método log10: 711ms = 3.02 veces más rápido que la línea de base
división repetida: 2797 ms = 0,77 veces más rápido que la línea de base
divide y vencerás: 74 ms = 28,99
veces más rápido que la línea de base
Editar:
Después de escribir el punto de referencia, eché un vistazo a Integer.toString desde Java 6, y descubrí que usa:
Esto se ve genial. podrías escribirlo un poco más compacto usando el operador?: para obtener más aceptación
André Pareis
88
hablar acerca de la optimización prematura: D
Gordon Gustafson
2
¡Me gusta! ¿Qué tal un bloque de interruptores en lugar de if-elseses anidados?
Kebman
2
No me di cuenta de todo esto si las declaraciones de lo contrario serían MUCHO más rápido que convertir el int a String y luego llamar a .length. +1
Ogen
15
Usando el operador ternario, lo reduce a 101 caracteres:n<100000?n<100?n<10?1:2:n<1000?3:n<10000?4:5:n<10000000?n<1000000?6:7:n<100000000?8:n<1000000000?9:10
Jonathan Gawrych
13
Dos comentarios sobre su punto de referencia: Java es un entorno complejo, con compilación justo a tiempo y recolección de basura, etc., para obtener una comparación justa, cada vez que ejecuto un punto de referencia, siempre: (a) adjunto las dos pruebas en un bucle que los ejecuta en secuencia 5 o 10 veces. Muy a menudo, el tiempo de ejecución en el segundo paso a través del bucle es bastante diferente del primero. Y (b) Después de cada "enfoque", hago un System.gc () para intentar desencadenar una recolección de basura. De lo contrario, el primer enfoque podría generar un montón de objetos, pero no lo suficiente como para forzar una recolección de basura, luego el segundo enfoque crea algunos objetos, el montón se agota y se ejecuta la recolección de basura. Luego, el segundo enfoque se "carga" por recoger la basura que deja el primer enfoque. ¡Muy injusto!
Dicho esto, ninguno de los anteriores hizo una diferencia significativa en este ejemplo.
Con o sin esas modificaciones, obtuve resultados muy diferentes a los de usted. Cuando ejecuté esto, sí, el enfoque toString dio tiempos de ejecución de 6400 a 6600 millis, mientras que el enfoque de registro topok 20,000 a 20,400 millis. En lugar de ser un poco más rápido, el enfoque de registro fue 3 veces más lento para mí.
Tenga en cuenta que los dos enfoques implican costos muy diferentes, por lo que esto no es totalmente impactante: el enfoque toString creará muchos objetos temporales que deben limpiarse, mientras que el enfoque de registro requiere un cálculo más intenso. Entonces, tal vez la diferencia es que en una máquina con menos memoria, toString requiere más rondas de recolección de basura, mientras que en una máquina con un procesador más lento, el cálculo adicional del registro sería más doloroso.
También probé un tercer enfoque. Escribí esta pequeña función:
Eso funcionó en 1600 a 1900 milis, menos de 1/3 del enfoque toString y 1/10 del enfoque de registro en mi máquina.
Si tuviera un amplio rango de números, podría acelerarlo aún más dividiendo entre 1,000 o 1,000,000 para reducir el número de veces a través del ciclo. No he jugado con eso.
¿Has intentado variar la entrada? La máquina virtual de punto de acceso podría optimizar este gráfico de lo contrario, lo que daría como resultado puntos de referencia incorrectos, ya que está devolviendo lo mismo precalculado cada vez.
Erik Aigner
11
Usando Java
int nDigits =Math.floor(Math.log10(Math.abs(the_integer)))+1;
Frio. pero creo que necesita abs (número) y también "0" es un caso especial también?
DmitryK
Si. Si necesita tener en cuenta el signo, tendrá que hacer algo como 1 + (int) Math.floor (Math.log10 (Math.abs (number))) + ((number <0)? 1: 0)
Dirk
55
El Math.floores un poco redundante, ¿no? Lanzarlo intlo redondeará de todos modos.
CompuChip
5
La solución de Marian se adaptó para números de tipo largos (hasta 9,223,372,036,854,775,807), en caso de que alguien quiera copiarlo y pegarlo. En el programa escribí esto para números hasta 10000 que eran mucho más probables, así que hice una rama específica para ellos. De todos modos, no hará una diferencia significativa.
publicstaticint numberOfDigits (long n){// Guessing 4 digit numbers will be more probable.// They are set in the first branch.if(n <10000L){// from 1 to 4if(n <100L){// 1 or 2if(n <10L){return1;}else{return2;}}else{// 3 or 4if(n <1000L){return3;}else{return4;}}}else{// from 5 a 20 (albeit longs can't have more than 18 or 19)if(n <1000000000000L){// from 5 to 12if(n <100000000L){// from 5 to 8if(n <1000000L){// 5 or 6if(n <100000L){return5;}else{return6;}}else{// 7 u 8if(n <10000000L){return7;}else{return8;}}}else{// from 9 to 12if(n <10000000000L){// 9 or 10if(n <1000000000L){return9;}else{return10;}}else{// 11 or 12if(n <100000000000L){return11;}else{return12;}}}}else{// from 13 to ... (18 or 20)if(n <10000000000000000L){// from 13 to 16if(n <100000000000000L){// 13 or 14if(n <10000000000000L){return13;}else{return14;}}else{// 15 or 16if(n <1000000000000000L){return15;}else{return16;}}}else{// from 17 to ...¿20?if(n <1000000000000000000L){// 17 or 18if(n <100000000000000000L){return17;}else{return18;}}else{// 19? Can it be?// 10000000000000000000L is'nt a valid long.return19;}}}}}
¿Lo has probado? Sabes que, incluso si tiene sentido para un punto de vista humano, realmente no funciona igual con la "forma de pensar" de la máquina, ¿verdad? --- Permítanme proponer una cosa: haga una matriz de dos millones de números, preferiblemente Long.MAX_VALUE, cuál es el peor caso de complejidad de su código, y úselo System.nanoTime()para hacer una prueba de reloj contra los peores casos de complejidad de la otra solución. ++ En realidad, pruébelo con una matriz llena por un aleatorizador establecido en el rango de 0a Long.MAX_VALUEtambién, solo para la prueba de "complejidad promedio" ++ Puede encontrar los resultados ... muy impactantes.
XenoRo
@thelima Esto no funciona correctamente para cero o negativos, pero es un error menor. El principio me parece correcto. ¿A qué resultado "impactante" te refieres?
Jay
Digamos que las computadoras ... Bueno ... no les gusta dividir. Y en los casos en que las "colas" grandes de números grandes necesitan ser procesadas, y cada dígito en cada número procesado requerirá una división ... Bueno ... Las cosas "comienzan a ser realmente lentas, muy rápidas" ... Si captan mi es decir ... --- Es por eso que ves muchas de las respuestas aquí usando códigos basados en la prueba y la comparación con cada dígito decimal usando 'si', en lugar de divisiones: si no es más rápido, al menos mantiene la mayor parte de su velocidad independientemente de los peores casos. --- Haga una prueba entre usar divisiones y logaritmos en números grandes ...
XenoRo
@TheLima, ¿de qué estás hablando? Para int,este bucle se ejecuta un máximo de 11 veces. ¿Tienes alguna evidencia de tus afirmaciones?
Marqués de Lorne
@EJP Desde el punto de vista del hardware, la división es un proceso iterativo. El algoritmo de división más rápido que conozco es radix4, que genera 4 bits por iteración; así que una división de 32 bits necesita 8 iteraciones al menos. Las multiplicaciones, por ejemplo, se pueden hacer en paralelo, y también se pueden dividir en multiplicaciones más simples; ya sea hasta el nivel de bits (que requiere solo 5 operaciones), o con un desglose parcial más una tabla de búsqueda al final (compensación de velocidad VS de tamaño clásico). No se trata solo de "cuántas iteraciones"; El problema con las divisiones radica en "lo que cada iteración implica / hace, a nivel de hardware"
Tiempo de ejecución 1: 6765
s: 400000000
Tiempo de ejecución 2: 6000
s: 400000000
Ahora me pregunto si mi punto de referencia realmente significa algo, pero obtengo resultados consistentes (variaciones dentro de un ms) en varias ejecuciones del punto de referencia en sí ... :) Parece que es inútil tratar de optimizar esto ...
editar: siguiendo el comentario de ptomli, reemplacé 'número' por 'i' en el código anterior y obtuve los siguientes resultados en 5 ejecuciones del banco:
Tiempo de ejecución 1: 11500
s: 788888890
Tiempo de ejecución 2: 8547
s: 788888890
Tiempo de ejecución 1: 11485
s: 788888890
Tiempo de ejecución 2: 8547
s: 788888890
Tiempo de ejecución 1: 11469
s: 788888890
Tiempo de ejecución 2: 8547
s: 788888890
Tiempo de ejecución 1: 11500
s: 788888890
Tiempo de ejecución 2: 8547
s: 788888890
Tiempo de ejecución 1: 11484
s: 788888890
Tiempo de ejecución 2: 8547
s: 788888890
No llamaría a un bucle de una línea con un cuerpo vacío simple. Tampoco modulo una potencia de 10 para ver si recuperas lo mismo (¿no puedes usar una comparación?).
Teepeemm
0
O, en cambio, la longitud que puede verificar si el número es mayor o menor que el número deseado.
publicvoid createCard(int cardNumber,int cardStatus,int customerId)throwsSQLException{if(cardDao.checkIfCardExists(cardNumber)==false){if(cardDao.createCard(cardNumber, cardStatus, customerId)==true){System.out.println("Card created successfully");}else{}}else{System.out.println("Card already exists, try with another Card Number");do{System.out.println("Enter your new Card Number: ");
scan =newScanner(System.in);int inputCardNumber = scan.nextInt();
cardNumber = inputCardNumber;}while(cardNumber <95000000);
cardDao.createCard(cardNumber, cardStatus, customerId);}}
No entiendo. Parece que estás respondiendo una pregunta diferente.
Teepeemm
0
Todavía no he visto una solución basada en la multiplicación. Las soluciones basadas en logaritmos, divisiones y cadenas se volverán bastante difíciles de manejar en millones de casos de prueba, así que aquí hay una para ints:
/**
* Returns the number of digits needed to represents an {@code int} value in
* the given radix, disregarding any sign.
*/publicstaticint len(int n,int radix){
radixCheck(radix);// if you want to establish some limitation other than radix > 2
n =Math.abs(n);int len =1;long min = radix -1;while(n > min){
n -= min;
min *= radix;
len++;}return len;}
En la base 10, esto funciona porque n se compara esencialmente con 9, 99, 999 ... como min es 9, 90, 900 ... yn se resta por 9, 90, 900 ...
Desafortunadamente, esto no es portátil longsimplemente reemplazando cada instancia intdebido a un desbordamiento. Por otro lado, da la casualidad de que va a trabajar para las bases 2 y 10 (pero mal no para la mayoría de las otras bases). Necesitará una tabla de búsqueda para los puntos de desbordamiento (o una prueba de división ... ew)
/**
* For radices 2 &le r &le Character.MAX_VALUE (36)
*/privatestaticlong[] overflowpt ={-1,-1,4611686018427387904L,8105110306037952534L,3458764513820540928L,5960464477539062500L,3948651115268014080L,3351275184499704042L,8070450532247928832L,1200757082375992968L,9000000000000000000L,5054470284992937710L,2033726847845400576L,7984999310198158092L,2022385242251558912L,6130514465332031250L,1080863910568919040L,2694045224950414864L,6371827248895377408L,756953702320627062L,1556480000000000000L,3089447554782389220L,5939011215544737792L,482121737504447062L,839967991029301248L,1430511474609375000L,2385723916542054400L,3902460517721977146L,6269893157408735232L,341614273439763212L,513726300000000000L,762254306892144930L,1116892707587883008L,1617347408439258144L,2316231840055068672L,3282671350683593750L,4606759634479349760L};publicstaticint len(long n,int radix){
radixCheck(radix);
n = abs(n);int len =1;long min = radix -1;while(n > min){
len++;if(min == overflowpt[radix])break;
n -= min;
min *= radix;}return len;}
Con diseño (basado en el problema). Esta es una alternativa de divide y vencerás. Primero definiremos una enumeración (considerando que es solo para un int sin signo).
Un divide y vencerás comenzaría en el medio y dividiría el área de búsqueda restante. Esto tiene un tiempo de ejecución lineal. Pero no importará solo por 9 comparaciones. ¿Pero esto no lo arruinará si num>=Nine.getValue()?
Teepeemm
0
Uno quiere hacer esto principalmente porque quiere "presentarlo", lo que significa que finalmente debe ser "toString-ed" (o transformado de otra manera) explícita o implícitamente de todos modos; antes de que pueda ser presentado (impreso, por ejemplo).
Si ese es el caso, simplemente intente hacer explícita la "toString" necesaria y cuente los bits.
Veo personas que usan bibliotecas de cadenas o incluso usan la clase Integer. No tiene nada de malo, pero el algoritmo para obtener el número de dígitos no es tan complicado. Estoy usando un largo en este ejemplo, pero funciona igual de bien con un int.
privatestaticint getLength(long num){int count =1;while(num >=10){
num = num /10;
count++;}return count;}
sin String API, sin utilidades, sin conversión de tipo, solo pura iteración de Java ->
publicstaticint getNumberOfDigits(int input){int numOfDigits =1;int base =1;while(input >= base *10){
base = base *10;
numOfDigits++;}return numOfDigits;}
Probablemente debería probarlo entonces (y asegurarse de que sea Java válido y esté formateado correctamente). Pero un enfoque recursivo de "divide por 10" fue publicado por Jedi Dula hace 3 años.
Teepeemm
-2
Podrías los dígitos usando la división sucesiva por diez:
int a=0;if(no <0){
no =-no;}elseif(no ==0){
no =1;}while(no >0){
no = no /10;
a++;}System.out.println("Number of digits in given number is: "+a);
Sinista publicó por primera vez un enfoque de "divide por 10" hace 3 años. Esa es la única razón por la que puedo pensar que tienes un voto negativo.
Teepeemm
-2
Ingrese el número y cree un Arraylist, y el ciclo while registrará todos los dígitos en el Arraylist. Luego podemos extraer el tamaño de la matriz, que será la longitud del valor entero que ingresó.
ArrayList<Integer> a=newArrayList<>();while(number >0){
remainder = num %10;
a.add(remainder);
number = number /10;}int m=a.size();
La forma en que funciona es con la variable del contador de números es que 10 = 1 dígito de espacio. Por ejemplo .1 = 1 décimo => espacio de 1 dígito. Por lo tanto, si tiene int number = 103342;, obtendrá 6, porque ese es el equivalente de .000001 espacios de vuelta. Además, ¿alguien tiene un mejor nombre de variable paranumberCounter ? No se me ocurre nada mejor.
Editar: solo pensé en una mejor explicación. Esencialmente, lo que está haciendo este ciclo while es hacer que divida su número entre 10, hasta que sea menor que uno. Esencialmente, cuando divide algo por 10, lo mueve hacia atrás un espacio numérico, por lo que simplemente lo divide por 10 hasta llegar a <1 para la cantidad de dígitos en su número.
Aquí hay otra versión que puede contar la cantidad de números en un decimal:
Respuestas:
Su solución basada en cadenas está perfectamente bien, no hay nada "descuidado" al respecto. Tienes que darte cuenta de que matemáticamente, los números no tienen una longitud, ni tienen 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 logaritmo hace (algunas de) las mismas cosas que la basada en String 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.
fuente
Math.abs()
Sin embargo, agregar arreglará esto.El logaritmo es tu amigo:
NB: solo válido para n> 0.
fuente
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. Puede acercarse a este intervalo utilizando 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 que divide mediante una comparación en un intervalo de longitud 3 y uno de longitud 2. El intervalo de longitud 2 requiere una comparación más (total 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 coma flotante, sin costosos logaritmos, solo comparaciones enteras.
Código (largo pero rápido):
Punto de referencia (después del calentamiento de JVM): consulte el código a continuación para ver cómo se ejecutó el punto de referencia:
veces más rápido que la línea de base
Código completo:
De nuevo, punto de referencia:
veces más rápido que la línea de base
Editar: Después de escribir el punto de referencia, eché un vistazo a Integer.toString desde Java 6, y descubrí que usa:
Lo comparé con mi solución de divide y vencerás:
El mío es aproximadamente 4 veces más rápido que la solución Java 6.
fuente
n<100000?n<100?n<10?1:2:n<1000?3:n<10000?4:5:n<10000000?n<1000000?6:7:n<100000000?8:n<1000000000?9:10
Dos comentarios sobre su punto de referencia: Java es un entorno complejo, con compilación justo a tiempo y recolección de basura, etc., para obtener una comparación justa, cada vez que ejecuto un punto de referencia, siempre: (a) adjunto las dos pruebas en un bucle que los ejecuta en secuencia 5 o 10 veces. Muy a menudo, el tiempo de ejecución en el segundo paso a través del bucle es bastante diferente del primero. Y (b) Después de cada "enfoque", hago un System.gc () para intentar desencadenar una recolección de basura. De lo contrario, el primer enfoque podría generar un montón de objetos, pero no lo suficiente como para forzar una recolección de basura, luego el segundo enfoque crea algunos objetos, el montón se agota y se ejecuta la recolección de basura. Luego, el segundo enfoque se "carga" por recoger la basura que deja el primer enfoque. ¡Muy injusto!
Dicho esto, ninguno de los anteriores hizo una diferencia significativa en este ejemplo.
Con o sin esas modificaciones, obtuve resultados muy diferentes a los de usted. Cuando ejecuté esto, sí, el enfoque toString dio tiempos de ejecución de 6400 a 6600 millis, mientras que el enfoque de registro topok 20,000 a 20,400 millis. En lugar de ser un poco más rápido, el enfoque de registro fue 3 veces más lento para mí.
Tenga en cuenta que los dos enfoques implican costos muy diferentes, por lo que esto no es totalmente impactante: el enfoque toString creará muchos objetos temporales que deben limpiarse, mientras que el enfoque de registro requiere un cálculo más intenso. Entonces, tal vez la diferencia es que en una máquina con menos memoria, toString requiere más rondas de recolección de basura, mientras que en una máquina con un procesador más lento, el cálculo adicional del registro sería más doloroso.
También probé un tercer enfoque. Escribí esta pequeña función:
Eso funcionó en 1600 a 1900 milis, menos de 1/3 del enfoque toString y 1/10 del enfoque de registro en mi máquina.
Si tuviera un amplio rango de números, podría acelerarlo aún más dividiendo entre 1,000 o 1,000,000 para reducir el número de veces a través del ciclo. No he jugado con eso.
fuente
Usando Java
usar
import java.lang.Math.*;
al principioUsando C
usar
inclue math.h
al principiofuente
the_integer
es0
así, así que verifique eso.No puedo dejar un comentario todavía, así que lo publicaré como una respuesta separada.
La solución basada en logaritmo no calcula el número correcto de dígitos para enteros largos muy grandes, por ejemplo:
La solución basada en logaritmo calcula el número incorrecto de dígitos en enteros grandes
fuente
Como el número de dígitos en la base 10 de un entero es solo 1 + truncado (log10 (número)) , puede hacer:
Editado porque mi última edición solucionó el código de ejemplo, pero no la descripción.
fuente
Math.floor
es un poco redundante, ¿no? Lanzarloint
lo redondeará de todos modos.La solución de Marian se adaptó para números de tipo largos (hasta 9,223,372,036,854,775,807), en caso de que alguien quiera copiarlo y pegarlo. En el programa escribí esto para números hasta 10000 que eran mucho más probables, así que hice una rama específica para ellos. De todos modos, no hará una diferencia significativa.
fuente
Otro enfoque de cuerda. Corto y dulce, para cualquier número entero
n
.fuente
n
y cero. Se puede usar("" + Math.abs(n)).length()
para obtener la longitud del entero negativo.¿Puedo intentar? ;)
basado en la solución de Dirk
fuente
¿Qué hay de las viejas matemáticas simples? Divide entre 10 hasta llegar a 0.
fuente
Long.MAX_VALUE
, cuál es el peor caso de complejidad de su código, y úseloSystem.nanoTime()
para hacer una prueba de reloj contra los peores casos de complejidad de la otra solución. ++ En realidad, pruébelo con una matriz llena por un aleatorizador establecido en el rango de0
aLong.MAX_VALUE
también, solo para la prueba de "complejidad promedio" ++ Puede encontrar los resultados ... muy impactantes.int,
este bucle se ejecuta un máximo de 11 veces. ¿Tienes alguna evidencia de tus afirmaciones?La solución de Marian, ahora con Ternary:
Porque podemos
fuente
Curioso, traté de compararlo ...
los resultados son:
Ahora me pregunto si mi punto de referencia realmente significa algo, pero obtengo resultados consistentes (variaciones dentro de un ms) en varias ejecuciones del punto de referencia en sí ... :) Parece que es inútil tratar de optimizar esto ...
editar: siguiendo el comentario de ptomli, reemplacé 'número' por 'i' en el código anterior y obtuve los siguientes resultados en 5 ejecuciones del banco:
fuente
¿Qué pasa con este método recursivo?
fuente
Solución simple:
fuente
Una solución realmente simple:
fuente
O, en cambio, la longitud que puede verificar si el número es mayor o menor que el número deseado.
}
fuente
Todavía no he visto una solución basada en la multiplicación. Las soluciones basadas en logaritmos, divisiones y cadenas se volverán bastante difíciles de manejar en millones de casos de prueba, así que aquí hay una para
ints
:En la base 10, esto funciona porque n se compara esencialmente con 9, 99, 999 ... como min es 9, 90, 900 ... yn se resta por 9, 90, 900 ...
Desafortunadamente, esto no es portátil
long
simplemente reemplazando cada instanciaint
debido a un desbordamiento. Por otro lado, da la casualidad de que va a trabajar para las bases 2 y 10 (pero mal no para la mayoría de las otras bases). Necesitará una tabla de búsqueda para los puntos de desbordamiento (o una prueba de división ... ew)fuente
Con diseño (basado en el problema). Esta es una alternativa de divide y vencerás. Primero definiremos una enumeración (considerando que es solo para un int sin signo).
Ahora definiremos una clase que pasa por los valores de la enumeración y compara y devuelve la longitud adecuada.
El tiempo de ejecución de esta solución es el mismo que el enfoque de divide y vencerás.
fuente
num>=Nine.getValue()
?Uno quiere hacer esto principalmente porque quiere "presentarlo", lo que significa que finalmente debe ser "toString-ed" (o transformado de otra manera) explícita o implícitamente de todos modos; antes de que pueda ser presentado (impreso, por ejemplo).
Si ese es el caso, simplemente intente hacer explícita la "toString" necesaria y cuente los bits.
fuente
Podemos lograr esto usando un bucle recursivo
fuente
Escribí esta función después de buscar el
Integer.java
código fuente.fuente
Veo personas que usan bibliotecas de cadenas o incluso usan la clase Integer. No tiene nada de malo, pero el algoritmo para obtener el número de dígitos no es tan complicado. Estoy usando un largo en este ejemplo, pero funciona igual de bien con un int.
fuente
sin String API, sin utilidades, sin conversión de tipo, solo pura iteración de Java ->
Puede optar por valores más grandes si lo desea.
fuente
fuente
Manera recursiva fácil
no probado
fuente
Podrías los dígitos usando la división sucesiva por diez:
fuente
Ingrese el número y cree un
Arraylist
, y el ciclo while registrará todos los dígitos en elArraylist
. Luego podemos extraer el tamaño de la matriz, que será la longitud del valor entero que ingresó.fuente
Aquí hay un método realmente simple que hice que funciona para cualquier número:
La forma en que funciona es con la variable del contador de números es que 10 = 1 dígito de espacio. Por ejemplo .1 = 1 décimo => espacio de 1 dígito. Por lo tanto, si tiene
int number = 103342;
, obtendrá 6, porque ese es el equivalente de .000001 espacios de vuelta. Además, ¿alguien tiene un mejor nombre de variable paranumberCounter
? No se me ocurre nada mejor.Editar: solo pensé en una mejor explicación. Esencialmente, lo que está haciendo este ciclo while es hacer que divida su número entre 10, hasta que sea menor que uno. Esencialmente, cuando divide algo por 10, lo mueve hacia atrás un espacio numérico, por lo que simplemente lo divide por 10 hasta llegar a <1 para la cantidad de dígitos en su número.
Aquí hay otra versión que puede contar la cantidad de números en un decimal:
fuente
Intente convertir el int en una cadena y luego obtenga la longitud de la cadena . Eso debería obtener la longitud de la int .
fuente
number
sea negativo.