a) for(int i = 100000; i > 0; i--) {}
b) for(int i = 1; i < 100001; i++) {}
答案在此网站上(第3个问题)。我只是不明白为什么? 网站上的解释如下:
3. a
a) for(int i = 100000; i > 0; i--) {}
b) for(int i = 1; i < 100001; i++) {}
答案在此网站上(第3个问题)。我只是不明白为什么? 网站上的解释如下:
3. a
当你深入到最低层(机器码,但我将使用汇编语言,因为它大多数时候是一对一的映射)时,一个从零递减到0的空循环和一个从零递增到50(例如)的循环之间的区别通常在以下方面:
ld a,50 ld a,0
loop: dec a loop: inc a
jnz loop cmp a,50
jnz loop
那是因为大多数合理的 CPU 中,当您达到零时,减量指令会设置零标志位。而当增量指令达到50时通常不能说有同样的情况(因为50没有像零一样的特殊性)。因此,您需要将寄存器与50比较以设置零标志位。
然而,询问哪个循环:
for(int i = 100000; i > 0; i--) {}
for(int i = 1; i < 100001; i++) {}
在几乎任何环境下(包括Java),比较哪个更快是没有意义的,因为它们都没有做任何有用的事情。这两个循环中最快的版本是根本不需要循环的。我挑战任何人想出比这更快的版本 :-)
只有在你开始在大括号内执行一些有用的工作时,它们才会变得有用,此时工作将决定你应该使用哪个顺序。
例如,如果你需要从1计数到100,000,你应该使用第二个循环。这是因为倒计数的优点(如果有的话)可能会被每次需要使用它时都要评估100000-i
的事实淹没。在汇编方面,这将是以下代码之间的区别:
ld b,100000 dsw a
sub b,a
dsw b
(dsw
当然是臭名昭著的 do something with
汇编助记符)。
既然每次迭代只需进行一次递增循环的耗时,而至少每次迭代都需要进行一次减法(假设你将使用 i
,否则根本不需要循环),那么你应该选择更自然的版本。
如果你需要计数,就计数。如果你需要倒序计数,就倒序计数。
100000-i
的计算也几乎肯定会淹没您从反转循环中获得的任何小优势。 - paxdiablo在许多编译器上,向后循环的机器指令更有效率,因为测试是否为零(并因此将寄存器清零)比加载常量值要快。
另一方面,一个好的优化编译器应该能够检查循环内部,并确定向后循环不会产生任何副作用...
顺便说一句,我认为这是一个糟糕的面试问题。除非你在谈论一个运行10百万次并且已确定向后循环不会因多次重新创建前向循环值(n-i)而被权衡掉的循环,否则任何性能收益都是微不足道的。
一如既往地,不要在牺牲代码易读性的情况下进行微观优化,务必进行性能基准测试。
这类问题往往只是某些人过度纠结的无关紧要的分心。称其为微优化崇拜或其他任何你喜欢的名字吧,但是向上还是向下循环更快?说真的吗?你应该根据当前情况使用适合的方式,而不是为了节省两个时钟周期而编写代码。
让编译器发挥作用,明确你的意图(同时让编译器和读者都能理解)。另一个常见的Java慢化行为是:
public final static String BLAH = new StringBuilder().append("This is ").append(3).append(' text").toString();
因为过多的字符串拼接会导致内存碎片,但对于常量,编译器可以(并且会)进行优化:
public final static String BLAH = "This is a " + 3 + " test";
其中第一个不会被优化,第二个更易读。
(a>b)?a:b
和 Math.max(a,b)
呢?我知道我宁愿读第二个,所以我并不在意第一个没有引入函数调用的开销。
这个列表中有一些有用的东西,比如知道finally
块不会在System.exit()
上调用是可能有用的。知道浮点数除以0.0不会抛出异常也很有用。
但是除非真的很重要(我打赌99.99%的情况下都不是),不要费力地去猜测编译器。
for
循环,并为我赢得每 GHz 218 ips,宝贝。 - Jed Smith更好的问题是:
哪个更容易理解/使用?
这比性能上的概念差异更为重要。个人认为,性能不应成为确定两者区别的标准。如果他们不喜欢我对此做出挑战,我也不会因未得到工作而感到不满。 ;)
Java(TM) SE Runtime Environment 1.6.0_05-b13 Java HotSpot(TM) Server VM 10.0-b19 up 1000000000: 1817ms 1.817ns/iteration (sum 499999999500000000) up 1000000000: 1786ms 1.786ns/iteration (sum 499999999500000000) up 1000000000: 1778ms 1.778ns/iteration (sum 499999999500000000) up 1000000000: 1769ms 1.769ns/iteration (sum 499999999500000000) up 1000000000: 1769ms 1.769ns/iteration (sum 499999999500000000) up 1000000000: 1766ms 1.766ns/iteration (sum 499999999500000000) up 1000000000: 1776ms 1.776ns/iteration (sum 499999999500000000) up 1000000000: 1768ms 1.768ns/iteration (sum 499999999500000000) up 1000000000: 1771ms 1.771ns/iteration (sum 499999999500000000) up 1000000000: 1768ms 1.768ns/iteration (sum 499999999500000000) down 1000000000: 1847ms 1.847ns/iteration (sum 499999999500000000) down 1000000000: 1842ms 1.842ns/iteration (sum 499999999500000000) down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000) down 1000000000: 1832ms 1.832ns/iteration (sum 499999999500000000) down 1000000000: 1842ms 1.842ns/iteration (sum 499999999500000000) down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000) down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000) down 1000000000: 1847ms 1.847ns/iteration (sum 499999999500000000) down 1000000000: 1839ms 1.839ns/iteration (sum 499999999500000000) down 1000000000: 1838ms 1.838ns/iteration (sum 499999999500000000)请注意,时间差异是脆弱的,循环中的任何小变化都可能导致时间差异。 编辑: 基准循环为:
long sum = 0;
for (int i = 0; i < limit; i++)
{
sum += i;
}
和
long sum = 0;
for (int i = limit - 1; i >= 0; i--)
{
sum += i;
}
使用 int 类型的 sum 变量会快大约三倍,但是可能会发生溢出。 使用 BigInteger 则会慢超过 50 倍:
BigInteger up 1000000000: 105943ms 105.943ns/iteration (sum 499999999500000000)
回答这个问题实际上只有两种方法。
告诉你这真的不重要,你甚至在浪费时间思考。
告诉你唯一的方法是在你真正关心的生产硬件、操作系统和JRE安装上运行可信赖的基准测试来了解。
因此,我为您制作了一个可运行的基准测试,您可以在此处尝试:
http://code.google.com/p/caliper/source/browse/trunk/test/examples/LoopingBackwardsBenchmark.java
这个 Caliper 框架还不够成熟,所以可能不是完全明显该怎么做,但如果你真的很关心,你可以弄清楚。以下是它在我的 Linux 系统上给出的结果:
max benchmark ns
2 Forwards 4
2 Backwards 3
20 Forwards 9
20 Backwards 20
2000 Forwards 1007
2000 Backwards 1011
20000000 Forwards 9757363
20000000 Backwards 10303707