As respostas que as pessoas estão dando a você estão corretas ... elas fornecem o comprimento de você int sem convertê-lo em uma string ... mas por que você não deseja convertê-lo em uma string? É uma coisa de velocidade? Se assim for, não estou convencido de que esses métodos será mais rápido ... você pode querer fazer alguns testes (ou decidir se ele ainda importa.)
Beska
3
Os dígitos hexadecimais do @ptomli ainda são dígitos, apenas em um sistema base diferente.
Mark Pim
2
@Ptomli Claro, mas tanto na função Integer.toString quanto na conversa geral, decimal é o padrão. Quando o banco me diz: "Escreva o valor do seu cheque nesta caixa", não pergunto se devo escrevê-lo em decimal, hexadecimal ou octal. Assumimos decimal, a menos que especificado de outra forma ou chamado por contexto.
Jay
Respostas:
349
Sua solução baseada em String está perfeitamente bem, não há nada "arrumado" nela. Você deve perceber que matematicamente, os números não têm comprimento nem têm dígitos. Comprimento e dígitos são propriedades de uma representação física de um número em uma base específica, isto é, uma String.
Uma solução baseada em logaritmo faz (algumas) as mesmas coisas que uma baseada em String faz internamente, e provavelmente o faz (insignificantemente) mais rapidamente porque produz apenas o comprimento e ignora os dígitos. Mas eu realmente não consideraria isso mais claro em termos de intenção - e esse é o fator mais importante.
+1 para considerar intenção do código ao escolher uma maneira de resolver um problema
pupeno
5
Datapoint: Na minha máquina, o método log parece ser executado apenas duas vezes mais rápido que os métodos de comprimento de string. Eu não chamaria isso de insignificante se o método for chamado muito ou em uma seção de código de tempo crítico.
cperkins
11
Veja meu teste unitário de benchmark abaixo (que também pode ter falhas, eu não sou especialista em benchmark). Em um grande número de execuções (100.000.000), a velocidade é de 11s a 8s na minha máquina quase o dobro da velocidade.
Jean
5
@CPerkins. Otimização prematura. Você conhece o discurso.
22610 Michael Borgwardt
11
Alguns (bastante tarde) adição: pode não funcionar corretamente para valores negativos, dependendo se você espera que o "-" seja um dígito ou não. A adição Math.abs()corrigirá isso, no entanto.
E isso é mais rápido ou melhor do que usar minha variante?
fnst 20/08/09
+1 Você me venceu por um segundo e sua resposta estava certa, onde a minha estava um pouco fora. Note, porém, que o compilador vai reclamar devido a um elenco que faltava para int
Dirk
2
@ Tom Por que você acha que é caro? Pode-se supor que o co-processador matemático o executaria, portanto, pode estar próximo da velocidade de uma adição. Mesmo que o java não use o co-processador agora, é uma boa suposição de que ele possa ... (Vamos ignorar sua implicação ainda mais instruída de que o Java é lento porque você provavelmente não está interessado em evidências - ou se você fosse você iria para shootout.alioth.debian.org e descobrir por si mesmo)
Bill K
8
Funciona ... a menos que o valor que você está verificando = 0, o que fornecerá resultados ímpares (-2147483647). API Math.log10: "Se o argumento for zero positivo ou zero negativo, o resultado será infinito negativo".
22312 mujimu
2
+1 Apresentando um método que não envolve alocações de memória de objeto, que é essencial para maximizar a reutilização para evitar coleções de GC.
Michael Wojcik
159
A abordagem mais rápida: dividir e conquistar.
Supondo que seu intervalo seja de 0 a MAX_INT, você tem de 1 a 10 dígitos. Você pode abordar esse intervalo usando dividir e conquistar, com até 4 comparações por cada entrada. Primeiro, você divide [1..10] em [1..5] e [6..10] com uma comparação e, em seguida, a cada intervalo 5, você divide usando uma comparação em um intervalo 3 e um comprimento 2. O intervalo de comprimento 2 requer mais uma comparação (total de 3 comparações), o intervalo de comprimento 3 pode ser dividido em intervalo de comprimento 1 (solução) e um intervalo de duração 2. Então, você precisa de 3 ou 4 comparações.
Sem divisões, operações de ponto flutuante, logaritmos dispendiosos, apenas comparações de números inteiros.
Código (longo mas 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;}}}
Referência (após o aquecimento da JVM) - veja o código abaixo para ver como a referência foi executada:
método de linha de base (com String.length): 2145ms
método log10: 711ms = 3,02 vezes mais rápido que a linha de base
divisão repetida: 2797ms = 0,77 vezes mais rápido que a linha de base
dividir e conquistar: 74ms = 28,99
vezes mais rápido que a linha 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;}
Mais uma vez, benchmark:
método de linha de base (com String.length): 2145ms
método log10: 711ms = 3,02 vezes mais rápido que a linha de base
divisão repetida: 2797ms = 0,77 vezes mais rápido que a linha de base
dividir e conquistar: 74ms = 28,99
vezes mais rápido que a linha de base
Edit:
Depois que escrevi o benchmark, dei uma espiada no Integer.toString do Java 6 e descobri que ele usa:
isso parece ótimo. você poderia escrevê-lo um pouco mais compacta usando o operador?: para obter mais aceitação
André Pareis
88
falar sobre otimização prematura: D
Gordon Gustafson
2
Eu gosto disso! Que tal um bloco de switch em vez de if-elseses tão aninhados?
Kebman #
2
Eu não percebi todas essas instruções if else seriam MUITO mais rápidas do que converter o int em String e depois chamar .length. +1
Ogen
15
Usando o operador ternário, traz para baixo 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
Dois comentários sobre seu benchmark: Java é um ambiente complexo, com compilação e coleta de lixo just-in-time e assim por diante, para obter uma comparação justa, sempre que executo um benchmark, sempre: (a) coloque os dois testes em um loop que os executa na sequência 5 ou 10 vezes. Muitas vezes, o tempo de execução na segunda passagem pelo loop é bem diferente da primeira. E (b) Após cada "abordagem", faço um System.gc () para tentar acionar uma coleta de lixo. Caso contrário, a primeira abordagem pode gerar um monte de objetos, mas não o suficiente para forçar uma coleta de lixo; a segunda abordagem cria alguns objetos, o heap está esgotado e a coleta de lixo é executada. Em seguida, a segunda abordagem é "cobrada" pela coleta do lixo deixado pela primeira abordagem. Muito injusto!
Dito isto, nenhum dos itens acima fez uma diferença significativa neste exemplo.
Com ou sem essas modificações, obtive resultados muito diferentes dos resultados obtidos. Quando eu executei isso, sim, a abordagem toString forneceu tempos de execução de 6400 a 6600 millis, enquanto a abordagem de log ultrapassou 20.000 a 20.400 millis. Em vez de ser um pouco mais rápida, a abordagem do log foi três vezes mais lenta para mim.
Observe que as duas abordagens envolvem custos muito diferentes, portanto, isso não é totalmente chocante: a abordagem toString criará muitos objetos temporários que precisam ser limpos, enquanto a abordagem de log exige uma computação mais intensa. Portanto, talvez a diferença seja que em uma máquina com menos memória, o toString requer mais rodadas de coleta de lixo, enquanto em uma máquina com um processador mais lento, o cálculo extra do log seria mais doloroso.
Eu também tentei uma terceira abordagem. Eu escrevi esta pequena função:
Isso foi executado entre 1600 e 1900 milissegundos - menos de 1/3 da abordagem toString e 1/10 da abordagem de log na minha máquina.
Se você tivesse uma ampla variedade de números, poderia acelerar ainda mais, dividindo por 1.000 ou 1.000.000 para reduzir o número de vezes no loop. Eu não brinquei com isso.
Você já tentou variar a entrada? Caso contrário, a VM do hotspot poderia otimizar esse gráfico, resultando em benchmarks errados, pois sempre retornava a mesma coisa pré-computada.
Erik Aigner
11
Usando Java
int nDigits =Math.floor(Math.log10(Math.abs(the_integer)))+1;
Legal. mas acho que precisa de abs (número) e também "0" é um caso especial também?
DmitryK
Sim. Se você precisar dar conta do sinal, precisará fazer algo como 1 + (int) Math.floor (Math.log10 (Math.abs (número))) + ((número <0)? 1: 0)
Dirk
5
O Math.flooré um pouco redundante, não é? A transmissão para intarredondará para baixo de qualquer maneira.
CompuChip
5
A solução da Marian adaptada para números longos (até 9.223.372.036.854.775.807), caso alguém queira copiá-lo e colá-lo. No programa que escrevi para números até 10000 eram muito mais prováveis, então criei um ramo específico para eles. De qualquer forma, não fará uma diferença 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;}}}}}
Você já testou? Você sabe que, por mais difícil que faça sentido para um ponto de vista humano, na verdade não funciona da mesma maneira com o "modo de pensar" da máquina, certo? --- Deixe-me propor uma coisa: faça uma matriz de dois milhões de números, de preferência Long.MAX_VALUE, qual é o pior caso de complexidade do seu código e use-o System.nanoTime()para fazer um teste de clock contra os piores casos de complexidade da outra solução. ++ Na verdade, tente com uma matriz preenchida por um randomizador definido como também 0para Long.MAX_VALUE, apenas para o teste de "complexidade média" ++ Você pode encontrar os resultados ... muito chocantes.
XenoRo 11/10/12
@ thelima Isso não funciona corretamente para zero ou negativos, mas é um bug menor. O princípio parece correto para mim. A que resultado "chocante" você está se referindo?
Jay
Digamos apenas que os computadores ... Bem ... Eles não gostam de se dividir. E nos casos em que grandes "filas" de grandes números precisam ser processadas, e cada dígito em cada número processado exigirá uma divisão ... Bem ... As coisas "começam a ficar muito lentas muito rápido" ... Se você pegar o meu significado ... --- É por isso que você vê muitas das respostas aqui usando códigos baseados em teste e comparação com cada dígito decimal usando 'if's, em vez de divisões: se não for mais rápido, pelo menos mantém a maior parte da velocidade, independentemente dos piores casos. --- Faça um teste entre o uso de divisões e logaritmo em grandes números ...
XenoRo 6/14
@TheLima do que você está falando? Para int,esse loop, ele executa no máximo 11 vezes. Você tem alguma evidência para suas afirmações?
Marquês de Lorne
@EJP Do ponto de vista do hardware, a divisão é um processo iterativo. O algoritmo de divisão mais rápido que conheço é o radix4, que gera 4 bits por iteração; portanto, uma divisão de 32 bits precisa de pelo menos 8 iterações. Multiplicações, por exemplo, podem ser feitas em paralelo e também divididas em multiplicações mais simples; no nível de bit (exigindo apenas 5 operações) ou com quebra parcial mais uma tabela de consulta no final (troca de velocidade VS de tamanho clássico). Não se trata apenas de "quantas iterações"; o problema com divisões mentiras com "o que cada iteração implica / faz, a um nível de hardware"
Tempo de execução 1: 6765
s: 400000000
Tempo de execução 2: 6000
s: 400000000
Agora, fico me perguntando se meu benchmark realmente significa alguma coisa, mas eu obtenho resultados consistentes (variações dentro de um ms) em várias execuções do próprio benchmark ... :) Parece que é inútil tentar otimizar isso ...
edit: após o comentário de ptomli, substitui 'number' por 'i' no código acima e obtive os seguintes resultados em 5 execuções do banco:
Tempo de execução 1: 11500
s: 788888890
Tempo de execução 2: 8547
s: 788888890
Tempo de execução 1: 11485
s: 788888890
Tempo de execução 2: 8547
s: 788888890
Tempo de execução 1: 11469
s: 788888890
Tempo de execução 2: 8547
s: 788888890
Tempo de execução 1: 11500
s: 788888890
Tempo de execução 2: 8547
s: 788888890
Tempo de execução 1: 11484
s: 788888890
Tempo de execução 2: 8547
s: 788888890
Eu não chamaria uma linha de loop simples com um corpo vazio. Nem module uma potência de 10 para ver se você recebe a mesma coisa de volta (você não pode simplesmente usar uma comparação?).
Teepeemm
0
Ou então o comprimento que você pode verificar se o número é maior ou menor que o número desejado.
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);}}
Eu não entendo Parece que você está respondendo a uma pergunta diferente.
Teepeemm
0
Ainda não vi uma solução baseada em multiplicação. As soluções baseadas em logaritmo, divisão e cadeia de caracteres tornar-se-ão difíceis de manejar contra milhões de casos de teste, então aqui está um 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;}
Na base 10, isso funciona porque n é essencialmente comparado a 9, 99, 999 ... como min é 9, 90, 900 ... en é subtraído por 9, 90, 900 ...
Infelizmente, isso não é portátil longapenas substituindo todas as instâncias do intdevido ao estouro. Por outro lado, acontece que ele irá trabalhar para bases 2 e 10 (mas mal não para a maioria das outras bases). Você precisará de uma tabela de pesquisa para os pontos de estouro (ou um teste de divisão ... 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;}
Com design (baseado no problema). Esta é uma alternativa de dividir e conquistar. Primeiro, definiremos uma enumeração (considerando que é apenas para um int não assinado).
Uma divisão e conquista começaria no meio e dividiria a área de pesquisa restante. Isso tem um tempo de execução linear. Mas isso não importa para apenas 9 comparações. Mas isso não vai atrapalhar se num>=Nine.getValue()?
Teepeemm
0
Quer-se fazer isso principalmente porque ele / ela quer "apresentá-lo", o que geralmente significa que ele finalmente precisa ser "editado por strings" (ou transformado de outra maneira) explícita ou implicitamente; antes de poder ser apresentado (impresso por exemplo).
Se for esse o caso, tente explicitar o "toString" necessário e conte os bits.
Eu vejo pessoas usando bibliotecas de String ou mesmo usando a classe Integer. Nada de errado com isso, mas o algoritmo para obter o número de dígitos não é tão complicado. Estou usando um longo neste exemplo, mas funciona tão bem com um int.
privatestaticint getLength(long num){int count =1;while(num >=10){
num = num /10;
count++;}return count;}
API sem String, sem utilitários, sem conversão de tipo, apenas iteração java pura ->
publicstaticint getNumberOfDigits(int input){int numOfDigits =1;int base =1;while(input >= base *10){
base = base *10;
numOfDigits++;}return numOfDigits;}
Provavelmente você deve testá-lo (e verifique se ele é Java válido e formatado corretamente). Mas uma abordagem recursiva de "dividir por 10" foi publicada por Jedi Dula há 3 anos.
Teepeemm
-2
Você poderia os dígitos usando a divisão sucessiva por dez:
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);
Uma abordagem de "dividir por 10" foi publicada pela Sinista há 3 anos. Essa é a única razão pela qual consigo pensar que você recebeu um voto negativo.
Teepeemm
-2
Digite o número e crie um Arraylist, e o loop while registrará todos os dígitos no Arraylist. Então podemos tirar o tamanho da matriz, que será o comprimento do valor inteiro que você digitou.
ArrayList<Integer> a=newArrayList<>();while(number >0){
remainder = num %10;
a.add(remainder);
number = number /10;}int m=a.size();
O modo como funciona é com a variável do contador numérico é o espaço de 10 = 1 dígito. Por exemplo .1 = 1 décimo => espaço de 1 dígito. Portanto, se você tiver, int number = 103342;receberá 6, porque isso equivale a 0,00001 espaços de volta. Além disso, alguém tem um nome de variável melhor paranumberCounter ? Não consigo pensar em nada melhor.
Edit: Apenas pensei em uma explicação melhor. Essencialmente, o que esse loop while está fazendo é fazer com que você divida seu número por 10, até que seja menor que um. Essencialmente, quando você divide algo por 10, você está movendo-o para trás um espaço numérico, então você simplesmente o divide por 10 até chegar a <1 para a quantidade de dígitos no seu número.
Aqui está outra versão que pode contar a quantidade de números em um decimal:
Respostas:
Sua solução baseada em String está perfeitamente bem, não há nada "arrumado" nela. Você deve perceber que matematicamente, os números não têm comprimento nem têm dígitos. Comprimento e dígitos são propriedades de uma representação física de um número em uma base específica, isto é, uma String.
Uma solução baseada em logaritmo faz (algumas) as mesmas coisas que uma baseada em String faz internamente, e provavelmente o faz (insignificantemente) mais rapidamente porque produz apenas o comprimento e ignora os dígitos. Mas eu realmente não consideraria isso mais claro em termos de intenção - e esse é o fator mais importante.
fonte
Math.abs()
corrigirá isso, no entanto.O logaritmo é seu amigo:
NB: válido apenas para n> 0.
fonte
A abordagem mais rápida: dividir e conquistar.
Supondo que seu intervalo seja de 0 a MAX_INT, você tem de 1 a 10 dígitos. Você pode abordar esse intervalo usando dividir e conquistar, com até 4 comparações por cada entrada. Primeiro, você divide [1..10] em [1..5] e [6..10] com uma comparação e, em seguida, a cada intervalo 5, você divide usando uma comparação em um intervalo 3 e um comprimento 2. O intervalo de comprimento 2 requer mais uma comparação (total de 3 comparações), o intervalo de comprimento 3 pode ser dividido em intervalo de comprimento 1 (solução) e um intervalo de duração 2. Então, você precisa de 3 ou 4 comparações.
Sem divisões, operações de ponto flutuante, logaritmos dispendiosos, apenas comparações de números inteiros.
Código (longo mas rápido):
Referência (após o aquecimento da JVM) - veja o código abaixo para ver como a referência foi executada:
vezes mais rápido que a linha de base
Código completo:
Mais uma vez, benchmark:
vezes mais rápido que a linha de base
Edit: Depois que escrevi o benchmark, dei uma espiada no Integer.toString do Java 6 e descobri que ele usa:
Comparei-o com a minha solução de dividir e conquistar:
O meu é cerca de 4x mais rápido que a solução Java 6.
fonte
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
Dois comentários sobre seu benchmark: Java é um ambiente complexo, com compilação e coleta de lixo just-in-time e assim por diante, para obter uma comparação justa, sempre que executo um benchmark, sempre: (a) coloque os dois testes em um loop que os executa na sequência 5 ou 10 vezes. Muitas vezes, o tempo de execução na segunda passagem pelo loop é bem diferente da primeira. E (b) Após cada "abordagem", faço um System.gc () para tentar acionar uma coleta de lixo. Caso contrário, a primeira abordagem pode gerar um monte de objetos, mas não o suficiente para forçar uma coleta de lixo; a segunda abordagem cria alguns objetos, o heap está esgotado e a coleta de lixo é executada. Em seguida, a segunda abordagem é "cobrada" pela coleta do lixo deixado pela primeira abordagem. Muito injusto!
Dito isto, nenhum dos itens acima fez uma diferença significativa neste exemplo.
Com ou sem essas modificações, obtive resultados muito diferentes dos resultados obtidos. Quando eu executei isso, sim, a abordagem toString forneceu tempos de execução de 6400 a 6600 millis, enquanto a abordagem de log ultrapassou 20.000 a 20.400 millis. Em vez de ser um pouco mais rápida, a abordagem do log foi três vezes mais lenta para mim.
Observe que as duas abordagens envolvem custos muito diferentes, portanto, isso não é totalmente chocante: a abordagem toString criará muitos objetos temporários que precisam ser limpos, enquanto a abordagem de log exige uma computação mais intensa. Portanto, talvez a diferença seja que em uma máquina com menos memória, o toString requer mais rodadas de coleta de lixo, enquanto em uma máquina com um processador mais lento, o cálculo extra do log seria mais doloroso.
Eu também tentei uma terceira abordagem. Eu escrevi esta pequena função:
Isso foi executado entre 1600 e 1900 milissegundos - menos de 1/3 da abordagem toString e 1/10 da abordagem de log na minha máquina.
Se você tivesse uma ampla variedade de números, poderia acelerar ainda mais, dividindo por 1.000 ou 1.000.000 para reduzir o número de vezes no loop. Eu não brinquei com isso.
fonte
Usando Java
use
import java.lang.Math.*;
no começoUsando C
use
inclue math.h
no começofonte
the_integer
for0
, então verifique isso.Não é possível deixar um comentário ainda, então postarei como uma resposta separada.
A solução baseada em logaritmo não calcula o número correto de dígitos para números inteiros muito grandes, por exemplo:
Solução baseada em logaritmo calcula número incorreto de dígitos em números inteiros grandes
fonte
Como o número de dígitos na base 10 de um número inteiro é apenas 1 + truncado (log10 (número)) , você pode:
Editado porque minha última edição corrigiu o exemplo de código, mas não a descrição.
fonte
Math.floor
é um pouco redundante, não é? A transmissão paraint
arredondará para baixo de qualquer maneira.A solução da Marian adaptada para números longos (até 9.223.372.036.854.775.807), caso alguém queira copiá-lo e colá-lo. No programa que escrevi para números até 10000 eram muito mais prováveis, então criei um ramo específico para eles. De qualquer forma, não fará uma diferença significativa.
fonte
Outra abordagem de string. Curto e doce - para qualquer número inteiro
n
.fonte
n
e zero. Pode ser usado("" + Math.abs(n)).length()
para obter comprimento inteiro negativo.Posso tentar? ;)
com base na solução de Dirk
fonte
Que tal matemática antiga? Divida por 10 até chegar a 0.
fonte
Long.MAX_VALUE
, qual é o pior caso de complexidade do seu código e use-oSystem.nanoTime()
para fazer um teste de clock contra os piores casos de complexidade da outra solução. ++ Na verdade, tente com uma matriz preenchida por um randomizador definido como também0
paraLong.MAX_VALUE
, apenas para o teste de "complexidade média" ++ Você pode encontrar os resultados ... muito chocantes.int,
esse loop, ele executa no máximo 11 vezes. Você tem alguma evidência para suas afirmações?Solução da Marian, agora com Ternary:
Porque nós podemos.
fonte
Curioso, tentei compará-lo ...
os resultados são:
Agora, fico me perguntando se meu benchmark realmente significa alguma coisa, mas eu obtenho resultados consistentes (variações dentro de um ms) em várias execuções do próprio benchmark ... :) Parece que é inútil tentar otimizar isso ...
edit: após o comentário de ptomli, substitui 'number' por 'i' no código acima e obtive os seguintes resultados em 5 execuções do banco:
fonte
E esse método recursivo?
fonte
solução simples:
fonte
Uma solução realmente simples:
fonte
Ou então o comprimento que você pode verificar se o número é maior ou menor que o número desejado.
}
fonte
Ainda não vi uma solução baseada em multiplicação. As soluções baseadas em logaritmo, divisão e cadeia de caracteres tornar-se-ão difíceis de manejar contra milhões de casos de teste, então aqui está um para
ints
:Na base 10, isso funciona porque n é essencialmente comparado a 9, 99, 999 ... como min é 9, 90, 900 ... en é subtraído por 9, 90, 900 ...
Infelizmente, isso não é portátil
long
apenas substituindo todas as instâncias doint
devido ao estouro. Por outro lado, acontece que ele irá trabalhar para bases 2 e 10 (mas mal não para a maioria das outras bases). Você precisará de uma tabela de pesquisa para os pontos de estouro (ou um teste de divisão ... ew)fonte
Com design (baseado no problema). Esta é uma alternativa de dividir e conquistar. Primeiro, definiremos uma enumeração (considerando que é apenas para um int não assinado).
Agora vamos definir uma classe que passa pelos valores da enumeração, comparar e retornar o comprimento apropriado.
O tempo de execução dessa solução é o mesmo da abordagem de dividir e conquistar.
fonte
num>=Nine.getValue()
?Quer-se fazer isso principalmente porque ele / ela quer "apresentá-lo", o que geralmente significa que ele finalmente precisa ser "editado por strings" (ou transformado de outra maneira) explícita ou implicitamente; antes de poder ser apresentado (impresso por exemplo).
Se for esse o caso, tente explicitar o "toString" necessário e conte os bits.
fonte
Podemos conseguir isso usando um loop recursivo
fonte
Eu escrevi essa função depois de procurar o
Integer.java
código fonte.fonte
Eu vejo pessoas usando bibliotecas de String ou mesmo usando a classe Integer. Nada de errado com isso, mas o algoritmo para obter o número de dígitos não é tão complicado. Estou usando um longo neste exemplo, mas funciona tão bem com um int.
fonte
API sem String, sem utilitários, sem conversão de tipo, apenas iteração java pura ->
Você pode comprar valores maiores, se quiser.
fonte
fonte
Maneira fácil recursiva
não testado
fonte
Você poderia os dígitos usando a divisão sucessiva por dez:
fonte
Digite o número e crie um
Arraylist
, e o loop while registrará todos os dígitos noArraylist
. Então podemos tirar o tamanho da matriz, que será o comprimento do valor inteiro que você digitou.fonte
Aqui está um método realmente simples que eu criei que funciona para qualquer número:
O modo como funciona é com a variável do contador numérico é o espaço de 10 = 1 dígito. Por exemplo .1 = 1 décimo => espaço de 1 dígito. Portanto, se você tiver,
int number = 103342;
receberá 6, porque isso equivale a 0,00001 espaços de volta. Além disso, alguém tem um nome de variável melhor paranumberCounter
? Não consigo pensar em nada melhor.Edit: Apenas pensei em uma explicação melhor. Essencialmente, o que esse loop while está fazendo é fazer com que você divida seu número por 10, até que seja menor que um. Essencialmente, quando você divide algo por 10, você está movendo-o para trás um espaço numérico, então você simplesmente o divide por 10 até chegar a <1 para a quantidade de dígitos no seu número.
Aqui está outra versão que pode contar a quantidade de números em um decimal:
fonte
Tente converter o int em uma sequência e obtenha o comprimento da sequência . Isso deve ter a duração do int .
fonte
number
é negativo.