翻翻过去那场雪
最快的方法：分而治之。假设您的范围是0到MAX_int，那么您就有1到10位数字。您可以使用“分而治之”来接近此间隔，每个输入最多可进行4次比较。首先，用一个比较将[1.10]划分为[1.5]和[6.10]，然后使用一个比较将每个长度5间隔划分为1长度3和1长度2区间。长度2间隔需要再进行一次比较(总计3次比较)，长度3间隔可分为长度1间隔(解)和长度2间隔。所以，你需要3或4个比较。没有除法，没有浮点运算，没有昂贵的对数，只有整数比较。代码(长但快)：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;
}
}
}基准测试(JVM预热之后)-参见下面的代码，以了解基准测试是如何运行的：基线方法(有字符串长度)：2145 mslog 10方法：711 ms=3.02倍于基线重复划分：2797 ms=0.77倍于基线分而治之：74ms=28.99比基线快几倍完整代码：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;}同样，基准：基线方法(有字符串长度)：2145 mslog 10方法：711 ms=3.02倍于基线重复划分：2797 ms=0.77倍于基线分而治之：74ms=28.99比基线快几倍编辑：在编写了基准测试之后，我从Java 6中偷偷地进入了Integer.toString，并发现它使用：final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999, Integer.MAX_VALUE };
// Requires positive xstatic int stringSize(int x) {
for (int i=0; ; i++)
if (x <= sizeTable[i])
return i+1;}我将其与分而治之的解决方案相对照：分而治之：104 msJava 6解决方案-迭代和比较：406 ms我的大约快4倍。