11

一种） for(int i = 100000; i > 0; i--) {}

b) for(int i = 1; i < 100001; i++) {}

答案就在这个网站上（问题 3）。我就是想不通为什么？来自网站：

3.一个

4

16 回答 16

69

当您进入最低级别时（机器代码，但我将使用汇编，因为它主要是一对一映射），递减到 0 的空循环和递增到 50（例如）的空循环之间的差异通常是行：

      ld  a,50                ld  a,0
loop: dec a             loop: inc a
      jnz loop                cmp a,50
                              jnz loop

这是因为当你达到零时，大多数理智的 CPU 中的零标志是由递减指令设置的。当增量指令达到 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，否则根本不需要循环)，你应该选择更自然的版本。

如果你需要数数，数数。如果需要倒计时，请倒计时。

于 2009-11-01T06:27:40.843 回答
23

在许多编译器上，为向后循环发出的机器指令更有效，因为测试零（因此将寄存器归零）比立即加载常量值更快。

另一方面，一个好的优化编译器应该能够检查循环内部并确定向后运行不会导致任何副作用......

顺便说一句，在我看来，这是一个糟糕的面试问题。除非您谈论的是运行 1000 万次的循环，并且您已经确定重新创建前向循环值 (n - i) 的许多实例不会超过轻微的增益，否则任何性能增益都将是最小的。

与往常一样，不要在没有性能基准测试的情况下进行微优化，并且以更难理解的代码为代价。

于 2009-11-01T05:59:21.807 回答
17

这类问题在很大程度上是一种无关紧要的干扰，有些人对此很着迷。将其称为微优化崇拜或任何您喜欢的东西，但循环向上或向下循环更快吗？严重地？你使用适合你正在做的事情的任何一个。您不会为了节省两个时钟周期或其他任何方式编写代码。

让编译器做它的用途并让你的意图清晰（编译器和读者）。另一个常见的 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:bvsMath.max(a,b)呢？我知道我宁愿阅读第二个，所以我真的不在乎第一个不会产生函数调用开销。

这个列表中有一些有用的东西，比如知道一个finally块没有被调用System.exit()是可能有用的。知道将浮点数除以 0.0 不会引发异常是很有用的。

但是除非它真的很重要（我敢打赌你有 99.99% 的时间它不重要），否则不要对编译器进行第二次猜测。

于 2009-11-01T06:11:03.747 回答
13

一个更好的问题是；

哪个更容易理解/使用？

这比性能上的名义差异重要得多。就个人而言，我会指出，性能不应该是这里确定差异的标准。如果他们不喜欢我挑战他们对此的假设，我不会因为没有得到这份工作而感到不高兴。;)

于 2009-11-01T09:06:32.397 回答
10

在现代 Java 实现中，这是不正确的。将多达 10 亿的数字加起来作为基准：

Java(TM) SE 运行时环境 1.6.0_05-b13
Java HotSpot(TM) 服务器虚拟机 10.0-b19
向上 1000000000：1817ms 1.817ns/迭代（总和 499999999500000000）
向上 1000000000：1786ms 1.786ns/迭代（总和 499999999500000000）
向上 1000000000：1778ms 1.778ns/迭代（总和 499999999500000000）
向上 1000000000：1769ms 1.769ns/迭代（总和 499999999500000000）
向上 1000000000：1769ms 1.769ns/迭代（总和 499999999500000000）
向上 1000000000：1766ms 1.766ns/迭代（总和 499999999500000000）
向上 1000000000：1776ms 1.776ns/迭代（总和 499999999500000000）
向上 1000000000：1768ms 1.768ns/迭代（总和 499999999500000000）
向上 1000000000：1771ms 1.771ns/迭代（总和 499999999500000000）
向上 1000000000：1768ms 1.768ns/迭代（总和 499999999500000000）
下降 1000000000：1847ms 1.847ns/迭代（总和 499999999500000000）
下降 1000000000：1842ms 1.842ns/迭代（总和 499999999500000000）
下降 1000000000：1838ms 1.838ns/迭代（总和 499999999500000000）
下降 1000000000：1832ms 1.832ns/迭代（总和 499999999500000000）
下降 1000000000：1842ms 1.842ns/迭代（总和 499999999500000000）
下降 1000000000：1838ms 1.838ns/迭代（总和 499999999500000000）
下降 1000000000：1838ms 1.838ns/迭代（总和 499999999500000000）
下降 1000000000：1847ms 1.847ns/迭代（总和 499999999500000000）
下降 1000000000：1839ms 1.839ns/迭代（总和 499999999500000000）
下降 1000000000：1838ms 1.838ns/迭代（总和 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 大约快三倍，但随后 sum 溢出。使用 BigInteger 会慢 50 倍以上：

BigInteger up 1000000000: 105943ms 105.943ns/iteration (sum 499999999500000000)
于 2009-11-01T08:08:06.397 回答
6

通常，实际代码向上计数会运行得更快。这有几个原因：

  • 处理器针对向前读取内存进行了优化。
  • HotSpot（可能还有其他字节码->本机编译器）对前向循环进行了大量优化，但不要为后向循环而烦恼，因为它们很少发生。
  • 向上通常更明显，更简洁的代码通常更快。

因此，愉快地做正确的事通常会更快。不必要的微优化是邪恶的。自从对 6502 汇编程序进行编程后，我就没有刻意编写反向循环。

于 2009-11-01T12:24:57.770 回答
6

实际上只有两种方法可以回答这个问题。

  1. 告诉你这真的，真的没关系，你甚至在浪费时间思考。

  2. 告诉您，唯一知道的方法是在您关心的实际生产硬件、操作系统和 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

向后循环对任何人来说都像是一场胜利吗？

于 2010-01-06T18:14:54.947 回答
3

你确定问这样一个问题的面试官希望得到一个直接的答案（“第一更快”或“第二更快”），或者如果问这个问题是为了引发讨论，就像人们在回答中所发生的那样给这里？

一般来说，不能说哪个更快，因为它很大程度上取决于 Java 编译器、JRE、CPU 和其他因素。在你的程序中使用一个或另一个只是因为你认为这两者中的一个更快而不了解最低级别的细节是迷信的编程。即使一个版本在您的特定环境中比另一个版本更快，那么差异很可能是如此之小以至于它是无关紧要的。

编写清晰的代码而不是试图变得聪明。

于 2009-11-01T09:34:04.527 回答
3

此类问题的基础是旧的最佳实践建议。一切都是为了比较：众所周知，与 0 比较更快。几年前，这可能被视为非常重要。如今，尤其是使用 Java，我宁愿让编译器和 VM 完成它们的工作，我会专注于编写易于维护和理解的代码。

除非有其他理由这样做。请记住，Java 应用程序并不总是在 HotSpot 和/或快速硬件上运行。

于 2009-11-01T14:45:30.780 回答
2

关于在 JVM 中测试零：显然可以使用ifeq来完成，而测试其他任何东西都需要if_icmpeq，这还涉及在堆栈上放置一个额外的值。

> 0与问题一样，可以使用ifgt测试for ，而测试 for 则< 100001需要if_icmplt。

于 2009-11-01T06:46:29.680 回答
2

这是关于我见过的最愚蠢的问题。循环体为空。如果编译器有任何好处，它根本不会发出任何代码。它不做任何事情，不能抛出异常，也不会修改其范围之外的任何内容。

假设您的编译器不是那么聪明，或者您实际上没有空循环体：“向后循环计数器”参数对于某些汇编语言是有意义的（它可能对 java 字节码也有意义，我不知道）具体不知道）。但是，编译器通常能够将循环转换为使用递减计数器。除非您有明确使用 i 值的循环体，否则编译器可以执行此转换。所以你经常看到没有区别。

于 2009-11-01T08:29:23.517 回答
2

我决定咬死线。

这两个循环都被 JVM 忽略为无操作。所以基本上即使其中一个循环到 10 并且另一个循环到 10000000，也不会有任何区别。

循环回零是另一回事（对于 jne 指令，但同样，它不是那样编译的），链接的站点很奇怪（而且是错误的）。

这种类型的问题不适合任何 JVM（也不适合任何其他可以优化的编译器）。

于 2011-01-18T16:52:02.320 回答
1

循环是相同的，除了一个关键部分：

我 > 0; 我 < 100001;

大于零检查是通过检查计算机的 NZP（通常称为条件代码或负零或正位）位来完成的。

每当诸如加载、与、加法等操作时，都会设置 NZP 位。执行。

大于检查不能直接利用该位（因此需要更长的时间......）一般的解决方案是使其中一个值为负（通过按位 NOT 然后加 1），然后将其添加到比较值. 如果结果为零，则它们相等。正数，则第二个值（不是负数）更大。负数，则第一个值（neg）更大。此检查比直接 nzp 检查花费的时间稍长。

我不是 100% 确定这是它背后的原因，但这似乎是一个可能的原因......

于 2009-11-01T06:27:28.020 回答
0

答案是（正如您可能在网站上发现的那样）

我认为原因是i > 0终止循环的条件测试速度更快。

于 2009-11-01T06:00:15.767 回答
0

底线是，对于任何非性能关键应用程序，差异可能是无关紧要的。正如其他人指出的那样，有时使用 ++i 而不是 i++ 可能会更快，但是，尤其是在 for 循环中，任何现代编译器都应该优化这种区别。

也就是说，差异可能与为比较生成的底层指令有关。测试一个值是否等于 0 只是一个NAND NOR 门。而测试一个值是否等于任意常数需要将该常数加载到寄存器中，然后比较两个寄存器。（这可能需要一两个额外的门延迟。）也就是说，对于流水线和现代 ALU，如果一开始的区别很重要，我会感到惊讶。

于 2009-11-01T06:08:21.083 回答
0

我已经进行了大约 15 分钟的测试，以防万一，除了 eclipse 之外什么都没有运行，我看到了真正的不同，你可以试试。

当我尝试计时 java 需要多长时间“什么都不做”时，大约需要 500 纳秒才能有一个想法。

for然后我测试了运行增加的语句需要多长时间：

for(i=0;i<100;i++){}

然后五分钟后，我尝试了“向后”的一个：

for(i=100;i>0;i--)

我在第一个和第二个for语句之间有 16% 的巨大差异（在极小的水平上），后者快了 16%。

for在 2000 次测试期间运行“increasing”语句的平均时间： 1838 n/s

for在 2000 次测试期间运行“递减”语句的平均时间： 1555 n/s

用于此类测试的代码：

public static void main(String[] args) {
    long time = 0;  
    for(int j=0; j<100; j++){
    long startTime = System.nanoTime();
    int i;
        /*for(i=0;i<100;i++){

        }*/
        for(i=100;i>0;i--){

        }
    long endTime = System.nanoTime();
    time += ((endTime-startTime));
    }
    time = time/100;
    System.out.print("Time: "+time);
}

结论： 差异基本上没有，与语句测试有关的“无”已经需要大量的“无” for，使得它们之间的差异可以忽略不计，只是导入诸如java.util之类的库所花费的时间.Scanner加载比运行for语句要多得多，它不会显着提高应用程序的性能，但知道它仍然很酷。

于 2015-12-10T19:13:34.880 回答