Existe-t-il un moyen plus simple d'obtenir la longueur d'un int?
int length = String.valueOf(1000).length();
Réponses
Trop de publicités?
Votre Chaîne solution est parfaitement OK, il n'y a rien "de l'onu-soigné". Vous vous rendez compte que sur le plan mathématique, les nombres n'ont pas une longueur, ni ont-ils des chiffres. La longueur et les chiffres sont à la fois les propriétés d'une représentation physique d'un nombre dans une base, c'est à dire une Chaîne de caractères.
Un logarithme à base de solution de (certains de) les mêmes choses de la Chaîne on n'en interne, et probablement le fait (faiblement) plus rapide car elle ne produit que de la longueur et ignore les chiffres. Mais je ne serait pas effectivement envisager plus clairement dans l'intention - et c'est le facteur le plus important.
Dmitry Brant
Points
2567
Marian
Points
968
L'approche plus rapide: diviser pour régner.
En supposant que votre gamme de 0 à MAX_INT, alors vous avez de 1 à 10 chiffres. Vous pouvez vous approcher de cet intervalle à l'aide de diviser pour régner, avec jusqu'à 4 comparaisons pour chaque entrée. Tout d'abord, vous divisez [1..10] [1..5] et [6..10] avec une comparaison, et puis, chacun d'une longueur de 5 intervalle de vous diviser à l'aide d'une comparaison sur une longueur de 3 et une longueur de 2 intervalle. La longueur de l'intervalle de 2 nécessite une comparaison (total 3 comparaisons), la longueur de 3 intervalle peut être divisé en intervalle de longueur 1 (solution) et d'une longueur de 2 intervalle. Donc, vous avez besoin de 3 ou 4 comparaisons.
Pas de divisions, pas d'opérations en virgule flottante, pas cher et les logarithmes, les entiers comparaisons.
Code (long mais rapide):
if (n < 100000)
{
// 5 or less
if (n < 100)
{
// 1 or 2
if (n < 10)
return 1;
else
return 2;
}
else
{
// 3 or 4 or 5
if (n < 1000)
return 3;
else
{
// 4 or 5
if (n < 10000)
return 4;
else
return 5;
}
}
}
else
{
// 6 or more
if (n < 10000000)
{
// 6 or 7
if (n < 1000000)
return 6;
else
return 7;
}
else
{
// 8 to 10
if (n < 100000000)
return 8;
else
{
// 9 or 10
if (n < 1000000000)
return 9;
else
return 10;
}
}
}
Indice de référence (après JVM ver-up) - voir code ci-dessous pour voir comment le test a été exécuté:
- référence de la méthode (avec de la Ficelle.la longueur): 2145ms
- log10 méthode: 711ms = 3.02 fois plus rapide que la ligne de base
- répété diviser: 2797ms = 0.77 fois plus rapide que la ligne de base
- divide-and-conquer: 74ms = 28.99
fois plus rapide que la ligne de base
Code complet:
public static void main(String[] args)
throws Exception
{
// validate methods:
for (int i = 0; i < 1000; i++)
if (method1(i) != method2(i))
System.out.println(i);
for (int i = 0; i < 1000; i++)
if (method1(i) != method3(i))
System.out.println(i + " " + method1(i) + " " + method3(i));
for (int i = 333; i < 2000000000; i += 1000)
if (method1(i) != method3(i))
System.out.println(i + " " + method1(i) + " " + method3(i));
for (int i = 0; i < 1000; i++)
if (method1(i) != method4(i))
System.out.println(i + " " + method1(i) + " " + method4(i));
for (int i = 333; i < 2000000000; i += 1000)
if (method1(i) != method4(i))
System.out.println(i + " " + method1(i) + " " + method4(i));
// work-up the JVM - make sure everything will be run in hot-spot mode
allMethod1();
allMethod2();
allMethod3();
allMethod4();
// run benchmark
Chronometer c;
c = new Chronometer(true);
allMethod1();
c.stop();
long baseline = c.getValue();
System.out.println(c);
c = new Chronometer(true);
allMethod2();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times faster than baseline");
c = new Chronometer(true);
allMethod3();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times faster than baseline");
c = new Chronometer(true);
allMethod4();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times faster than baseline");
}
private static int method1(int n)
{
return Integer.toString(n).length();
}
private static int method2(int n)
{
if (n == 0)
return 1;
return (int)(Math.log10(n) + 1);
}
private static int method3(int n)
{
if (n == 0)
return 1;
int l;
for (l = 0 ; n > 0 ;++l)
n /= 10;
return l;
}
private static int method4(int n)
{
if (n < 100000)
{
// 5 or less
if (n < 100)
{
// 1 or 2
if (n < 10)
return 1;
else
return 2;
}
else
{
// 3 or 4 or 5
if (n < 1000)
return 3;
else
{
// 4 or 5
if (n < 10000)
return 4;
else
return 5;
}
}
}
else
{
// 6 or more
if (n < 10000000)
{
// 6 or 7
if (n < 1000000)
return 6;
else
return 7;
}
else
{
// 8 to 10
if (n < 100000000)
return 8;
else
{
// 9 or 10
if (n < 1000000000)
return 9;
else
return 10;
}
}
}
}
private static int allMethod1()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method1(i);
for (int i = 1000; i < 100000; i += 10)
x = method1(i);
for (int i = 100000; i < 1000000; i += 100)
x = method1(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method1(i);
return x;
}
private static int allMethod2()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method2(i);
for (int i = 1000; i < 100000; i += 10)
x = method2(i);
for (int i = 100000; i < 1000000; i += 100)
x = method2(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method2(i);
return x;
}
private static int allMethod3()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method3(i);
for (int i = 1000; i < 100000; i += 10)
x = method3(i);
for (int i = 100000; i < 1000000; i += 100)
x = method3(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method3(i);
return x;
}
private static int allMethod4()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method4(i);
for (int i = 1000; i < 100000; i += 10)
x = method4(i);
for (int i = 100000; i < 1000000; i += 100)
x = method4(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method4(i);
return x;
}
Encore une fois, référence:
- référence de la méthode (avec de la Ficelle.la longueur): 2145ms
- log10 méthode: 711ms = 3.02 fois plus rapide que la ligne de base
- répété diviser: 2797ms = 0.77 fois plus rapide que la ligne de base
- divide-and-conquer: 74ms = 28.99
fois plus rapide que la ligne de base
Edit: Après, j'ai écrit à l'indice de référence, j'ai pris un coup d'oeil en Entier.toString de la version 6 de Java, et j'ai trouvé qu'il utilise:
final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999, Integer.MAX_VALUE };
// Requires positive x
static int stringSize(int x) {
for (int i=0; ; i++)
if (x <= sizeTable[i])
return i+1;
}
Je comparés contre ma divide-and-conquer solution:
- divide-and-conquer: 104ms
- Java 6 de la solution de parcourir et de comparer: 406ms
La mienne est 4x plus rapide.
Jay
Points
14781
Deux commentaires à faire sur votre référence: Java est un environnement complexe, avec juste-à-temps de la compilation et de la collecte des ordures et ainsi de suite, de sorte à obtenir une comparaison équitable, à chaque fois que je lance un test, j'ai toujours: (a) joindre les deux tests qui tourne en boucle dans l'ordre, 5 ou 10 fois. Très souvent, le moteur d'exécution sur le deuxième passage dans la boucle est assez différente de la première. Et (b) Après chaque "approche", je fais un Système.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 un peu d'objets, le tas est épuisé, et la collecte des ordures s'exécute. Ensuite, la deuxième approche est "chargé" pour ramasser les déchets laissés par la première approche. Très injuste!
Cela dit, ni de ce qui fait une différence significative dans cet exemple.
Avec ou sans ces modifications, j'ai obtenu des résultats très différents que vous l'avez fait. Quand j'ai couru ce, oui, le toString approche a donné des temps d'exécution de 6400 à 6600 millis, tandis que le journal de l'approche topok de 20 000 à 20 400 millis. Au lieu d'être légèrement plus rapide, le journal de l'approche a été 3 fois plus lent pour moi.
A noter que les deux approches impliquent des coûts différents, donc ce n'est pas totalement choquant: La toString approche permettra de créer un grand nombre d'objets temporaires qui doivent être nettoyés, tandis que le journal de l'approche prend de plus en plus intense calcul. Alors peut-être que la différence est que sur une machine avec moins de mémoire, toString nécessite plus de la collecte des ordures tours, alors que sur une machine avec un processeur plus lent, le supplément de calcul de journal serait de plus en plus douloureux.
J'ai aussi essayé une troisième approche. J'ai écrit ce petit fonction:
static int numlength(int n)
{
int l;
n=Math.abs(n);
for (l=0;n>0;++l)
n/=10;
return l;
}
Qui a couru en 1600 à 1900 millis -- moins de 1/3 de la toString approche, et 1/10 le journal de l'approche sur ma machine.
Si vous aviez une large gamme de nombres, vous pourriez accélérer davantage en commençant par les divisant par 1 000 ou 1 000 000 de réduire le nombre de fois la boucle. Je n'ai pas joué avec ça.
Dirk
Points
17809
