java - 为什么当一遍又一遍地运行相同的函数(使用递增的值)时，我的处理时间会下降？

Question

我正在测试一种新方法来替换我的旧方法，并做了一些速度测试。 当我现在查看图表时，我发现每次迭代所需的时间急剧下降。

现在我想知道为什么会这样。 我的问题是，我的显卡接管了繁重的工作，但第一个函数迭代 n 次，第二个函数(蓝色函数)没有单次迭代，而是使用 double 进行“繁重”计算工作。

如果需要系统详细信息: 操作系统:Mac OS X 10.10.4 核心:2.8 GHz Intel Core i7 (4x) GPU:AMD Radeon R9 M370X 2048 MB

如果您需要这两个功能:

新的:

private static int sumOfI(int i) {
    int factor;
    float factor_ = (i + 1) / 2;

    factor = (int) factor_;

    return (i % 2 == 0) ? i * factor + i / 2 : i * factor;
}

旧的:

private static int sumOfIOrdinary(int j) {
    int result = 0;
    for (int i = 1; i <= j; i++) {
        result += i;
    }
    return result;
}

为了澄清我的问题: 为什么处理时间会大幅下降？

编辑: 我至少对成本之类的事情有一点了解。我可能没有很好地解释我的测试方法。我有一个简单的 for 循环，在这个测试中从 0 计数到 1000，我将每个值提供给 1 个方法并记录它所花费的时间(整个循环执行)，然后我对另一个方法做了同样的事情。

因此，在循环达到大约 500 次之后，相同方法的执行时间显着减少。

Answer 1

Java 没有在显卡上计算任何内容(没有其他框架或类的帮助)。另外，您认为的“繁重”计算对于当今的CPU来说有点容易(即使除法有点棘手)。因此，速度取决于生成的字节码和运行程序时的 Java 优化，并且主要取决于 Big-O 表示法。

你的方法sumOfI只是执行x个语句，所以这是O(1)，无论你的i有多大，它总是只有这个x语句。但是 sumOfIOrdinary 使用一个循环，其 O(n) 时间复杂度将根据输入使用 y 语句 + i 语句。

因此从理论上讲，在最坏的种姓中 sumOfI 总是比 sumOfIOrdinary 更快。 您还可以在字节码 View 中看到这个问题。 sumOfI 只是对 cpu 的一些 load 和 add 和 multiply 调用。但对于循环，字节码还使用 goto 并且需要返回到较旧的地址，并且需要再次执行行，这将花费时间。

在我的 i=500000 的虚拟机上，第一个方法需要 <1 毫秒，而第二个方法需要 2-4 毫秒，因为循环需要 2-4 毫秒。

解释 Big-O-Notation 的链接:

1. Simple Big O Notation
2. A beginner's guide to Big O notation