Je pense qu'il veut compter les chiffres dans le nombre.
Alberto Zaccagni
3
Les réponses que les gens vous donnent sont correctes ... elles vous donnent la longueur de votre entier sans le convertir en chaîne ... mais pourquoi ne voulez-vous pas le convertir en chaîne? Est-ce une question de vitesse? Si c'est le cas, je ne suis pas convaincu que ces méthodes seront plus rapides ... vous voudrez peut-être faire des tests (ou décider si cela importe.)
Beska
3
@ptomli les chiffres hexadécimaux sont toujours des chiffres, juste dans un système de base différent.
Mark Pim
2
@Ptomli Bien sûr, mais dans la fonction Integer.toString et dans la conversation générale, la décimale est la valeur par défaut. Lorsque la banque me dit: "Écrivez le montant de votre chèque dans cette case", je ne leur demande pas si je dois l'écrire en décimal, hex ou octal. Nous supposons décimal, sauf indication contraire ou appelées par le contexte.
Jay
Réponses:
349
Votre solution basée sur String est parfaitement OK, il n'y a rien de "non soigné" à ce sujet. Vous devez réaliser que mathématiquement, les nombres n'ont pas de longueur, ni de chiffres. La longueur et les chiffres sont les deux propriétés d'une représentation physique d'un nombre dans une base spécifique, c'est-à-dire une chaîne.
Une solution basée sur un logarithme fait (certaines) les mêmes choses que celle basée sur une chaîne, et le fait probablement (de manière insignifiante) plus rapidement car elle ne produit que la longueur et ignore les chiffres. Mais je ne le considérerais pas plus clairement dans l'intention - et c'est le facteur le plus important.
+1 pour tenir compte de l'intention du code lors de la sélection d'un moyen de résoudre un problème
pupeno
5
Point de données: sur ma machine, la méthode log semble fonctionner un peu moins de deux fois plus vite que les méthodes de longueur de chaîne. Je n'appellerais pas cela insignifiant si la méthode est appelée beaucoup ou dans une section de code à temps critique.
CPerkins
1
Voir mon test unitaire de référence ci-dessous (qui peut aussi être imparfait, je ne suis pas un expert de référence). Sur un grand nombre de runs (100 000 000), la vitesse est de 11s à 8s sur ma machine à peine deux fois plus rapide.
Jean
5
@CPerkins. Optimisation prématurée. Vous connaissez le spiel.
Michael Borgwardt
11
Quelques ajouts (assez tardifs): cela peut ne pas fonctionner correctement pour les valeurs négatives, selon que vous vous attendez à ce que le "-" soit un chiffre ou non. L'ajout Math.abs()corrigera cependant cela.
Et est-ce plus rapide ou meilleur que d'utiliser ma variante?
TVPN
+1 Vous m'avez battu d'une seconde, et votre réponse était juste, là où la mienne était légèrement décalée. Notez, cependant, que le compilateur se plaindra en raison d'une distribution manquante à int
Dirk
2
@Tom Pourquoi supposeriez-vous que c'est cher? On pourrait supposer que le coprocesseur mathématique l'exécuterait, il pourrait donc être proche de la vitesse d'un ajout. Même si java n'utilise pas le coprocesseur maintenant, c'est une bonne hypothèse que cela pourrait ... (Nous ignorerons simplement votre implication encore plus peu instruite que Java est lent parce que vous n'êtes probablement pas intéressé par les preuves - ou si vous étiez, vous iriez sur shootout.alioth.debian.org et vous découvririez par vous-même)
Bill K
8
Fonctionne ... sauf si la valeur que vous vérifiez = 0, ce qui vous donnera des résultats étranges (-2147483647). API Math.log10: "Si l'argument est un zéro positif ou un zéro négatif, le résultat est l'infini négatif."
mujimu
2
+1 Présentation d'une méthode qui n'implique pas d'allocations de mémoire d'objets, ce qui est indispensable pour maximiser la réutilisation afin d'éviter les collections GC.
Michael Wojcik
159
L'approche la plus rapide: diviser pour mieux régner.
En supposant que votre plage est comprise entre 0 et MAX_INT, vous disposez de 1 à 10 chiffres. Vous pouvez approcher cet intervalle à l'aide de diviser pour régner, avec jusqu'à 4 comparaisons pour chaque entrée. Tout d'abord, vous divisez [1..10] en [1..5] et [6..10] avec une comparaison, puis chaque intervalle de longueur 5 que vous divisez en utilisant une comparaison en un intervalle de longueur 3 et un intervalle de longueur 2. L'intervalle de longueur 2 nécessite une comparaison supplémentaire (total de 3 comparaisons), l'intervalle de longueur 3 peut être divisé en intervalle de longueur 1 (solution) et un intervalle de longueur 2. Donc, vous avez besoin de 3 ou 4 comparaisons.
Pas de divisions, pas d'opérations en virgule flottante, pas de logarithmes coûteux, seulement des comparaisons entières.
Code (long mais rapide):
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;}}}
Benchmark (après échauffement JVM) - voir le code ci-dessous pour voir comment le benchmark a été exécuté:
méthode de référence (avec String.length): 2145 ms
méthode log10: 711 ms = 3,02 fois plus rapide que la ligne de base
division répétée: 2797 ms = 0,77 fois plus rapide que la ligne de base
diviser pour mieux régner: 74 ms = 28,99
fois plus rapide que la ligne de base
Code complet:
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;}
Encore une fois, référence:
méthode de référence (avec String.length): 2145 ms
méthode log10: 711 ms = 3,02 fois plus rapide que la ligne de base
division répétée: 2797 ms = 0,77 fois plus rapide que la ligne de base
diviser pour mieux régner: 74 ms = 28,99
fois plus rapide que la ligne de base
Edit:
Après avoir écrit le benchmark, j'ai pris un aperçu de Integer.toString à partir de Java 6, et j'ai trouvé qu'il utilise:
ça a l'air super. vous pourriez l'écrire un peu plus compact en utilisant l'opérateur?: pour obtenir plus d'acceptation
André Pareis
88
parler d'optimisation prématurée: D
Gordon Gustafson
2
Je l'aime! Que diriez-vous d'un bloc de commutation au lieu de si-elseses si imbriqués?
Kebman
2
Je ne savais pas tout cela si les instructions else seraient tellement plus rapides que de convertir l'int en String puis d'appeler .length. +1
Ogen
15
En utilisant l'opérateur ternaire, il ramène à 101 caractères: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
Deux commentaires sur votre benchmark: Java est un environnement complexe, avec une compilation juste à temps et un garbage collection et ainsi de suite, donc pour obtenir une comparaison juste, chaque fois que je lance un benchmark, je toujours: (a) joignent les deux tests dans une boucle qui les exécute en séquence 5 ou 10 fois. Très souvent, le temps d'exécution lors du deuxième passage dans la boucle est assez différent du premier. Et (b) Après chaque "approche", je fais un System.gc () pour essayer de déclencher un garbage collection. Sinon, la première approche peut générer un tas d'objets, mais pas assez pour forcer un garbage collection, puis la deuxième approche crée quelques objets, le tas est épuisé et le garbage collection s'exécute. Ensuite, la deuxième approche est «facturée» pour avoir ramassé les ordures laissées par la première approche. C'est vraiment injuste!
Cela dit, aucun des éléments ci-dessus n'a fait de différence significative dans cet exemple.
Avec ou sans ces modifications, j'ai obtenu des résultats très différents de vous. Lorsque j'ai exécuté cela, oui, l'approche toString a donné des temps d'exécution de 6400 à 6600 millis, tandis que l'approche log topok de 20 000 à 20 400 millis. Au lieu d'être légèrement plus rapide, l'approche log était 3 fois plus lente pour moi.
Notez que les deux approches impliquent des coûts très différents, donc ce n'est pas totalement choquant: l'approche toString créera beaucoup d'objets temporaires qui doivent être nettoyés, tandis que l'approche log prend un calcul plus intense. Alors peut-être la différence est que sur une machine avec moins de mémoire, toString nécessite plus de cycles de collecte de déchets, tandis que sur une machine avec un processeur plus lent, le calcul supplémentaire du journal serait plus douloureux.
J'ai également essayé une troisième approche. J'ai écrit cette petite fonction:
Cela a fonctionné en 1600 à 1900 millis - moins de 1/3 de l'approche toString et 1/10 de l'approche log sur ma machine.
Si vous aviez un large éventail de nombres, vous pouvez l'accélérer davantage en commençant par diviser par 1 000 ou 1 000 000 pour réduire le nombre de fois dans la boucle. Je n'ai pas joué avec ça.
Avez-vous essayé de modifier l'entrée? Sinon, la machine virtuelle du hotspot pourrait optimiser ce graphique, ce qui entraînerait de mauvais repères, car elle renvoie à chaque fois la même chose précalculée.
Erik Aigner
11
Utiliser Java
int nDigits =Math.floor(Math.log10(Math.abs(the_integer)))+1;
Cool. mais je pense qu'il a besoin d'abs (nombre) et aussi "0" est un cas spécial aussi?
DmitryK
Oui. Si vous devez tenir compte du signe, vous devrez faire quelque chose comme 1 + (int) Math.floor (Math.log10 (Math.abs (nombre))) + ((number <0)? 1: 0)
Dirk
5
C'est Math.floorun peu redondant, non? Le casting de l'arrêtera de inttoute façon.
CompuChip
5
La solution de Marian est adaptée pour les numéros de type long (jusqu'à 9 223 372 036 854 775 807), au cas où quelqu'un voudrait le copier-coller. Dans le programme, j'ai écrit cela pour que les nombres jusqu'à 10000 étaient beaucoup plus probables, alors j'ai fait une branche spécifique pour eux. De toute façon, cela ne fera pas de différence significative.
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;}}}}}
L'avez-vous testé? Vous savez que, même si cela a du sens pour un point de vue humain, cela ne fonctionne pas vraiment de la même façon avec la "façon de penser" de la machine, non? --- Permettez-moi de proposer une chose: créez un tableau de deux millions de nombres, de préférence Long.MAX_VALUE, qui est le pire cas de complexité de votre code, et utilisez-le System.nanoTime()pour effectuer un essai de synchronisation contre les pires cas de complexité de l'autre solution. ++ En fait, essayez avec un tableau rempli par un ensemble randomizer à la plage de 0à Long.MAX_VALUEtrop, juste pour la « complexité moyenne » test ++ Vous pouvez trouver les résultats ... très choquant.
XenoRo
@thelima Cela ne fonctionne pas correctement pour zéro ou négatifs, mais c'est un bug mineur. Le principe me semble correct. De quel résultat "choquant" parlez-vous?
Jay
Disons simplement que les ordinateurs ... Eh bien ... Ils n'aiment pas diviser. Et dans les cas où de grandes "files d'attente" de grands nombres doivent être traitées, et chaque chiffre de chaque numéro traité nécessitera une division ... Eh bien ... Les choses "commencent à devenir très lentes très rapidement" ... Si vous attrapez mon ce qui signifie ... --- C'est pourquoi vous voyez beaucoup de réponses ici en utilisant des codes basés sur le test et la comparaison avec chaque chiffre décimal en utilisant des "si" plutôt que des divisions: si ce n'est pas plus rapide, au moins il maintient la plupart de sa vitesse indépendamment de ses pires cas. --- Faites un test entre l'utilisation des divisions et le logarithme sur de grands nombres ...
XenoRo
@TheLima de quoi tu parles? Pour une int,boucle, cette boucle s'exécute au maximum 11 fois. Avez-vous des preuves de vos affirmations?
Marquis de Lorne
@EJP Du point de vue matériel, la division est un processus itératif. L'algorithme de division le plus rapide que je connaisse est radix4, qui génère 4 bits par itération; une division 32 bits nécessite donc au moins 8 itérations. Les multiplications, par exemple, peuvent être effectuées en parallèle et également être décomposées en multiplications plus simples; soit au niveau du bit (ne nécessitant que 5 opérations), soit avec une ventilation partielle plus une table de consultation à la fin (compromis de vitesse VS classique). Il ne s'agit pas seulement de "combien d'itérations"; le problème avec les divisions réside dans "ce que chaque itération implique / fait, au niveau matériel"
Maintenant, je me demande si mon benchmark signifie vraiment quelque chose mais j'obtiens des résultats cohérents (variations en quelques ms) sur plusieurs exécutions du benchmark lui-même ... :) Il semble inutile d'essayer d'optimiser cela ...
edit: suite au commentaire de ptomli, j'ai remplacé 'number' par 'i' dans le code ci-dessus et j'ai obtenu les résultats suivants sur 5 runs du banc:
Je n'appellerais pas une ligne pour boucle avec un corps vide simple. Ni modulo une puissance de 10 pour voir si vous obtenez la même chose (ne pouvez-vous pas simplement utiliser une comparaison?).
Teepeemm du
0
Ou plutôt la longueur que vous pouvez vérifier si le nombre est plus grand ou plus petit que le nombre souhaité.
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);}}
Je ne comprends pas. Il semble que vous répondiez à une autre question.
Teepeemm
0
Je n'ai pas encore vu de solution basée sur la multiplication. Le logarithme, la division et les solutions basées sur des chaînes deviendront plutôt difficiles à gérer contre des millions de cas de test, alors en voici un pour 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 base 10, cela fonctionne parce que n est essentiellement comparé à 9, 99, 999 ... car min est 9, 90, 900 ... et n est soustrait de 9, 90, 900 ...
Malheureusement, ce n'est pas portable longen remplaçant simplement chaque instance de intdue à un débordement. D'autre part, il se trouve, il va travailler pour les bases 2 et 10 (mais échoue mal pour la plupart des autres bases). Vous aurez besoin d'une table de recherche pour les points de débordement (ou d'un test de division ... 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;}
Avec design (basé sur le problème). C'est une alternative de diviser pour mieux régner. Nous allons d'abord définir une énumération (en considérant que ce n'est que pour un entier non signé).
Une division et conquête commencerait au milieu et diviserait la zone de recherche restante. Cela a un temps d'exécution linéaire. Mais cela n'aura pas d'importance pour seulement 9 comparaisons. Mais cela ne gâchera-t-il pas si num>=Nine.getValue()?
Teepeemm
0
On veut le faire principalement parce qu'il / elle veut le "présenter", ce qui signifie surtout qu'il doit finalement être "toString-ed" (ou transformé d'une autre manière) explicitement ou implicitement de toute façon; avant de pouvoir être présenté (imprimé par exemple).
Si tel est le cas, essayez simplement de rendre explicite le "toString" nécessaire et comptez les bits.
Je vois des gens utiliser des bibliothèques de chaînes ou même utiliser la classe Integer. Rien de mal à cela, mais l'algorithme pour obtenir le nombre de chiffres n'est pas si compliqué. J'utilise un long dans cet exemple mais cela fonctionne aussi bien avec un int.
privatestaticint getLength(long num){int count =1;while(num >=10){
num = num /10;
count++;}return count;}
pas d'API String, pas d'utilitaires, pas de conversion de type, juste une pure itération java ->
publicstaticint getNumberOfDigits(int input){int numOfDigits =1;int base =1;while(input >= base *10){
base = base *10;
numOfDigits++;}return numOfDigits;}
Vous pouvez aller longtemps pour de plus grandes valeurs si vous le souhaitez.
Vous devriez probablement le tester ensuite (et vous assurer qu'il est Java valide et correctement formaté). Mais une approche récursive "diviser par 10" a été publiée par Jedi Dula il y a 3 ans.
Teepeemm
-2
Vous pouvez utiliser les chiffres par division successive par dix:
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);
Une approche "diviser par 10" a été publiée pour la première fois par Sinista il y a 3 ans. C'est la seule raison pour laquelle je peux penser que vous avez obtenu un downvote.
Teepeemm
-2
Entrez le numéro et créez un Arraylist, et la boucle while enregistrera tous les chiffres dans le Arraylist. Ensuite, nous pouvons supprimer la taille du tableau, qui sera la longueur de la valeur entière que vous avez entrée.
ArrayList<Integer> a=newArrayList<>();while(number >0){
remainder = num %10;
a.add(remainder);
number = number /10;}int m=a.size();
La façon dont cela fonctionne avec la variable de compteur de nombres est que 10 = 1 espace numérique. Par exemple .1 = 1 dixième => 1 chiffre d'espace. Par conséquent, si vous en avez, int number = 103342;vous obtiendrez 6, car cela équivaut à 0,00001 espace en arrière. Est-ce que quelqu'un a un meilleur nom de variable pour numberCounter? Je ne vois rien de mieux.
Edit: Je viens de penser à une meilleure explication. Essentiellement, ce que fait cette boucle, c'est que vous divisez votre nombre par 10, jusqu'à ce qu'il soit inférieur à un. Essentiellement, lorsque vous divisez quelque chose par 10, vous le déplacez d'un espace numérique, vous le divisez donc simplement par 10 jusqu'à ce que vous atteigniez <1 pour le nombre de chiffres de votre nombre.
Voici une autre version qui peut compter le nombre de décimales:
Réponses:
Votre solution basée sur String est parfaitement OK, il n'y a rien de "non soigné" à ce sujet. Vous devez réaliser que mathématiquement, les nombres n'ont pas de longueur, ni de chiffres. La longueur et les chiffres sont les deux propriétés d'une représentation physique d'un nombre dans une base spécifique, c'est-à-dire une chaîne.
Une solution basée sur un logarithme fait (certaines) les mêmes choses que celle basée sur une chaîne, et le fait probablement (de manière insignifiante) plus rapidement car elle ne produit que la longueur et ignore les chiffres. Mais je ne le considérerais pas plus clairement dans l'intention - et c'est le facteur le plus important.
la source
Math.abs()
corrigera cependant cela.Le logarithme est votre ami:
NB: valable uniquement pour n> 0.
la source
L'approche la plus rapide: diviser pour mieux régner.
En supposant que votre plage est comprise entre 0 et MAX_INT, vous disposez de 1 à 10 chiffres. Vous pouvez approcher cet intervalle à l'aide de diviser pour régner, avec jusqu'à 4 comparaisons pour chaque entrée. Tout d'abord, vous divisez [1..10] en [1..5] et [6..10] avec une comparaison, puis chaque intervalle de longueur 5 que vous divisez en utilisant une comparaison en un intervalle de longueur 3 et un intervalle de longueur 2. L'intervalle de longueur 2 nécessite une comparaison supplémentaire (total de 3 comparaisons), l'intervalle de longueur 3 peut être divisé en intervalle de longueur 1 (solution) et un intervalle de longueur 2. Donc, vous avez besoin de 3 ou 4 comparaisons.
Pas de divisions, pas d'opérations en virgule flottante, pas de logarithmes coûteux, seulement des comparaisons entières.
Code (long mais rapide):
Benchmark (après échauffement JVM) - voir le code ci-dessous pour voir comment le benchmark a été exécuté:
fois plus rapide que la ligne de base
Code complet:
Encore une fois, référence:
fois plus rapide que la ligne de base
Edit: Après avoir écrit le benchmark, j'ai pris un aperçu de Integer.toString à partir de Java 6, et j'ai trouvé qu'il utilise:
Je l'ai comparé à ma solution diviser pour mieux régner:
Le mien est environ 4x plus rapide que la solution Java 6.
la source
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
Deux commentaires sur votre benchmark: Java est un environnement complexe, avec une compilation juste à temps et un garbage collection et ainsi de suite, donc pour obtenir une comparaison juste, chaque fois que je lance un benchmark, je toujours: (a) joignent les deux tests dans une boucle qui les exécute en séquence 5 ou 10 fois. Très souvent, le temps d'exécution lors du deuxième passage dans la boucle est assez différent du premier. Et (b) Après chaque "approche", je fais un System.gc () pour essayer de déclencher un garbage collection. Sinon, la première approche peut générer un tas d'objets, mais pas assez pour forcer un garbage collection, puis la deuxième approche crée quelques objets, le tas est épuisé et le garbage collection s'exécute. Ensuite, la deuxième approche est «facturée» pour avoir ramassé les ordures laissées par la première approche. C'est vraiment injuste!
Cela dit, aucun des éléments ci-dessus n'a fait de différence significative dans cet exemple.
Avec ou sans ces modifications, j'ai obtenu des résultats très différents de vous. Lorsque j'ai exécuté cela, oui, l'approche toString a donné des temps d'exécution de 6400 à 6600 millis, tandis que l'approche log topok de 20 000 à 20 400 millis. Au lieu d'être légèrement plus rapide, l'approche log était 3 fois plus lente pour moi.
Notez que les deux approches impliquent des coûts très différents, donc ce n'est pas totalement choquant: l'approche toString créera beaucoup d'objets temporaires qui doivent être nettoyés, tandis que l'approche log prend un calcul plus intense. Alors peut-être la différence est que sur une machine avec moins de mémoire, toString nécessite plus de cycles de collecte de déchets, tandis que sur une machine avec un processeur plus lent, le calcul supplémentaire du journal serait plus douloureux.
J'ai également essayé une troisième approche. J'ai écrit cette petite fonction:
Cela a fonctionné en 1600 à 1900 millis - moins de 1/3 de l'approche toString et 1/10 de l'approche log sur ma machine.
Si vous aviez un large éventail de nombres, vous pouvez l'accélérer davantage en commençant par diviser par 1 000 ou 1 000 000 pour réduire le nombre de fois dans la boucle. Je n'ai pas joué avec ça.
la source
Utiliser Java
utiliser
import java.lang.Math.*;
au débutUtilisation de C
utiliser
inclue math.h
au débutla source
the_integer
c'est le cas0
, alors vérifiez cela.Je ne peux pas encore laisser de commentaire, je posterai donc une réponse séparée.
La solution basée sur le logarithme ne calcule pas le nombre correct de chiffres pour les très grands entiers longs, par exemple:
La solution basée sur le logarithme calcule un nombre incorrect de chiffres dans les grands entiers
la source
Étant donné que le nombre de chiffres de la base 10 d'un entier n'est que de 1 + tronqué (log10 (nombre)) , vous pouvez faire:
Modifié car ma dernière modification a corrigé l'exemple de code, mais pas la description.
la source
Math.floor
un peu redondant, non? Le casting de l'arrêtera deint
toute façon.La solution de Marian est adaptée pour les numéros de type long (jusqu'à 9 223 372 036 854 775 807), au cas où quelqu'un voudrait le copier-coller. Dans le programme, j'ai écrit cela pour que les nombres jusqu'à 10000 étaient beaucoup plus probables, alors j'ai fait une branche spécifique pour eux. De toute façon, cela ne fera pas de différence significative.
la source
Une autre approche de chaîne. Court et doux - pour tout entier
n
.la source
n
et zéro. Peut utiliser("" + Math.abs(n)).length()
pour obtenir la longueur d'un entier négatif.Puis-je essayer? ;)
basé sur la solution de Dirk
la source
Que diriez-vous de vieilles mathématiques simples? Divisez par 10 jusqu'à ce que vous atteigniez 0.
la source
Long.MAX_VALUE
, qui est le pire cas de complexité de votre code, et utilisez-leSystem.nanoTime()
pour effectuer un essai de synchronisation contre les pires cas de complexité de l'autre solution. ++ En fait, essayez avec un tableau rempli par un ensemble randomizer à la plage de0
àLong.MAX_VALUE
trop, juste pour la « complexité moyenne » test ++ Vous pouvez trouver les résultats ... très choquant.int,
boucle, cette boucle s'exécute au maximum 11 fois. Avez-vous des preuves de vos affirmations?Marian's Solution, maintenant avec Ternary:
Parce que nous le pouvons.
la source
Curieux, j'ai essayé de le comparer ...
les résultats sont:
Maintenant, je me demande si mon benchmark signifie vraiment quelque chose mais j'obtiens des résultats cohérents (variations en quelques ms) sur plusieurs exécutions du benchmark lui-même ... :) Il semble inutile d'essayer d'optimiser cela ...
edit: suite au commentaire de ptomli, j'ai remplacé 'number' par 'i' dans le code ci-dessus et j'ai obtenu les résultats suivants sur 5 runs du banc:
la source
Et cette méthode récursive?
la source
solution simple:
la source
Une solution vraiment simple:
la source
Ou plutôt la longueur que vous pouvez vérifier si le nombre est plus grand ou plus petit que le nombre souhaité.
}
la source
Je n'ai pas encore vu de solution basée sur la multiplication. Le logarithme, la division et les solutions basées sur des chaînes deviendront plutôt difficiles à gérer contre des millions de cas de test, alors en voici un pour
ints
:En base 10, cela fonctionne parce que n est essentiellement comparé à 9, 99, 999 ... car min est 9, 90, 900 ... et n est soustrait de 9, 90, 900 ...
Malheureusement, ce n'est pas portable
long
en remplaçant simplement chaque instance deint
due à un débordement. D'autre part, il se trouve, il va travailler pour les bases 2 et 10 (mais échoue mal pour la plupart des autres bases). Vous aurez besoin d'une table de recherche pour les points de débordement (ou d'un test de division ... ew)la source
Avec design (basé sur le problème). C'est une alternative de diviser pour mieux régner. Nous allons d'abord définir une énumération (en considérant que ce n'est que pour un entier non signé).
Nous allons maintenant définir une classe qui passe par les valeurs de l'énumération et comparer et renvoyer la longueur appropriée.
Le temps d'exécution de cette solution est identique à l'approche diviser pour régner.
la source
num>=Nine.getValue()
?On veut le faire principalement parce qu'il / elle veut le "présenter", ce qui signifie surtout qu'il doit finalement être "toString-ed" (ou transformé d'une autre manière) explicitement ou implicitement de toute façon; avant de pouvoir être présenté (imprimé par exemple).
Si tel est le cas, essayez simplement de rendre explicite le "toString" nécessaire et comptez les bits.
la source
Nous pouvons y parvenir en utilisant une boucle récursive
la source
J'ai écrit cette fonction après avoir regardé
Integer.java
le code source.la source
Je vois des gens utiliser des bibliothèques de chaînes ou même utiliser la classe Integer. Rien de mal à cela, mais l'algorithme pour obtenir le nombre de chiffres n'est pas si compliqué. J'utilise un long dans cet exemple mais cela fonctionne aussi bien avec un int.
la source
pas d'API String, pas d'utilitaires, pas de conversion de type, juste une pure itération java ->
Vous pouvez aller longtemps pour de plus grandes valeurs si vous le souhaitez.
la source
la source
Manière récursive facile
pas testé
la source
Vous pouvez utiliser les chiffres par division successive par dix:
la source
Entrez le numéro et créez un
Arraylist
, et la boucle while enregistrera tous les chiffres dans leArraylist
. Ensuite, nous pouvons supprimer la taille du tableau, qui sera la longueur de la valeur entière que vous avez entrée.la source
Voici une méthode très simple que j'ai faite qui fonctionne pour n'importe quel nombre:
La façon dont cela fonctionne avec la variable de compteur de nombres est que 10 = 1 espace numérique. Par exemple .1 = 1 dixième => 1 chiffre d'espace. Par conséquent, si vous en avez,
int number = 103342;
vous obtiendrez 6, car cela équivaut à 0,00001 espace en arrière. Est-ce que quelqu'un a un meilleur nom de variable pournumberCounter
? Je ne vois rien de mieux.Edit: Je viens de penser à une meilleure explication. Essentiellement, ce que fait cette boucle, c'est que vous divisez votre nombre par 10, jusqu'à ce qu'il soit inférieur à un. Essentiellement, lorsque vous divisez quelque chose par 10, vous le déplacez d'un espace numérique, vous le divisez donc simplement par 10 jusqu'à ce que vous atteigniez <1 pour le nombre de chiffres de votre nombre.
Voici une autre version qui peut compter le nombre de décimales:
la source
Essayez de convertir l' int en chaîne , puis obtenez la longueur de la chaîne . Cela devrait avoir la longueur de la int .
la source
number
est négatif.