Nombre de chiffres dans un entier en Java

1. Introduction

Dans ce rapide didacticiel, nous explorerons différentes façons d'obtenir le nombre de chiffres dans un entier en Java.

Nous analyserons également ces différentes méthodes et déterminerons quel algorithme conviendrait le mieux à notre situation.

2. Nombre de chiffres dans un entier

Pour les méthodes discutées ici, nous ne considérons que des entiers positifs. Si nous attendons une entrée négative, nous pouvons d'abord utiliser Math.abs (nombre) avant d'utiliser l'une de ces méthodes.

2.1. Solution basée sur les chaînes

Le moyen le plus simple d'obtenir le nombre de chiffres d'un Integer est peut-être de le convertir en String et d'appeler la méthode length () . Cela renverra la longueur de la représentation String de notre nombre:

int length = String.valueOf(number).length();

Mais cela peut être une approche sous-optimale, car cette instruction implique l'allocation de mémoire pour une chaîne, pour chaque évaluation . La JVM doit d'abord analyser notre numéro et copier ses chiffres dans une chaîne distincte et effectuer également un certain nombre d'opérations différentes (comme conserver des copies temporaires, gérer les conversions Unicode, etc.).

Si nous n'avons que quelques chiffres à évaluer, alors nous pouvons clairement opter pour cette solution - car la différence entre cette approche et toute autre approche sera négligeable même pour les grands nombres.

2.2. Approche logarithmique

Pour les nombres représentés sous forme décimale, si nous prenons leur journal en base 10 et l'arrondissons, nous obtiendrons le nombre de chiffres de ce nombre:

int length = (int) (Math.log10(number) + 1);

Notez que le journal 10 0 de n'importe quel nombre n'est pas défini. Donc, si nous attendons une entrée avec la valeur 0 , nous pouvons également vérifier cela.

L'approche logarithmique est nettement plus rapide que l' approche basée sur les chaînes car elle n'a pas à passer par le processus de conversion de données. Il s'agit simplement d'un calcul simple et direct sans aucune initialisation d'objet supplémentaire ni aucune boucle.

2.3. Multiplication répétée

Dans cette méthode, nous prendrons une variable temporaire (initialisée à 1) et la multiplierons continuellement par 10 jusqu'à ce qu'elle devienne supérieure à notre nombre. Au cours de ce processus, nous utiliserons également une variable de longueur qui gardera une trace de la longueur du nombre:

int length = 0; long temp = 1; while (temp <= number) { length++; temp *= 10; } return length;

Dans ce code, la ligne temp * = 10 est identique à l'écriture de temp = (temp << 3) + (temp << 1) . Étant donné que la multiplication est généralement une opération plus coûteuse sur certains processeurs par rapport aux opérateurs de décalage, ces derniers peuvent être un peu plus efficaces.

2.4. Diviser avec des pouvoirs de deux

Si nous connaissons la plage de notre nombre, alors nous pouvons utiliser une variation qui réduira davantage nos comparaisons. Cette méthode divise le nombre par des puissances de deux (par exemple 1, 2, 4, 8 etc.):

Cette méthode divise le nombre par des puissances de deux (par exemple 1, 2, 4, 8 etc.):

int length = 1; if (number >= 100000000) { length += 8; number /= 100000000; } if (number >= 10000) { length += 4; number /= 10000; } if (number >= 100) { length += 2; number /= 100; } if (number >= 10) { length += 1; } return length;

Il tire parti du fait que n'importe quel nombre peut être représenté par l'addition de puissances de 2. Par exemple, 15 peut être représenté par 8 + 4 + 2 + 1, qui sont toutes des puissances de 2.

Pour un nombre à 15 chiffres, nous ferions 15 comparaisons dans notre approche précédente, que nous avons réduite à seulement 4 dans cette méthode.

2.5. Diviser et conquérir

C'est peut-être l'approche la plus volumineuse par rapport à toutes les autres décrites ici, mais il va sans dire que celle-ci est la plus rapide car nous n'effectuons aucun type de conversion, multiplication, addition ou initialisation d'objet.

Nous obtenons notre réponse en seulement trois ou quatre déclarations if simples :

if (number < 100000) { if (number < 100) { if (number < 10) { return 1; } else { return 2; } } else { if (number < 1000) { return 3; } else { if (number < 10000) { return 4; } else { return 5; } } } } else { if (number < 10000000) { if (number < 1000000) { return 6; } else { return 7; } } else { if (number < 100000000) { return 8; } else { if (number < 1000000000) { return 9; } else { return 10; } } } }

Semblable à l'approche précédente, nous ne pouvons utiliser cette méthode que si nous connaissons la plage de notre nombre.

3. Analyse comparative

Maintenant que nous avons une bonne compréhension des solutions potentielles, faisons maintenant un benchmarking simple de toutes nos méthodes en utilisant le Java Microbenchmark Harness (JMH).

Le tableau suivant indique le temps de traitement moyen de chaque opération (en nanosecondes):

Benchmark Mode Cnt Score Error Units Benchmarking.stringBasedSolution avgt 200 32.736 ± 0.589 ns/op Benchmarking.logarithmicApproach avgt 200 26.123 ± 0.064 ns/op Benchmarking.repeatedMultiplication avgt 200 7.494 ± 0.207 ns/op Benchmarking.dividingWithPowersOf2 avgt 200 1.264 ± 0.030 ns/op Benchmarking.divideAndConquer avgt 200 0.956 ± 0.011 ns/op

La solution basée sur String , qui est la plus simple, est également l'opération la plus coûteuse, car c'est la seule qui nécessite la conversion de données et l'initialisation de nouveaux objets.

L'approche logarithmique est nettement plus efficace que la solution précédente, car elle n'implique aucune conversion de données. Et, étant une solution à une seule ligne, cela peut être une bonne alternative à l' approche basée sur les chaînes .

La multiplication répétée implique une simple multiplication, proportionnellement à la longueur du nombre; par exemple, si un nombre comporte quinze chiffres, cette méthode impliquera quinze multiplications.

Cependant, la méthode suivante tire parti du fait que chaque nombre peut être représenté par des puissances de deux (l'approche similaire à BCD), et réduit la même chose à 4 opérations de division, donc elle est encore plus efficace que la première.

Enfin, comme nous pouvons le déduire, l'algorithme le plus efficace est l'implémentation détaillée de Divide and Conquer - qui fournit la réponse en seulement trois ou quatre instructions if simples. Nous pouvons l'utiliser si nous avons un grand ensemble de données à analyser.

4. Conclusion

Dans ce bref article, nous avons décrit certaines des façons de trouver le nombre de chiffres dans un entier et nous avons comparé l'efficacité de chaque approche.

Et, comme toujours, vous pouvez trouver le code complet sur GitHub.