什么循环更有效？

Question

我想知道哪种代码效率更高，我有两个选择。你会说哪个更有效率，为什么？谢谢。选项Aarray1 size is 1000array2 size is 2000for(int i = 0; i < array1.size(); i++){    for(int j = 0; j < array2.size(); j++) {        if(array1[i].method() == array2[j].method()) // CHECKS IF THERE'S AN EQUAL IN BOTH ARRAYS        {            doSomething();            break;        }        if(j == array2.size()-1) // CHECKS IF ARRAY1 DID NOT FIND A MATCH        {            doSomething();            break;        }        for(k = 0; k < array1.size(); k++)        {            if(array1[k].method() == array2[j].method()) // CHECKS IF THERE'S AN EQUAL IN BOTH ARRAYS            {                // BUT DOES NOTHING BECAUSE IT WAS DONE ALREADY UPSIDE                break;            }            if(k == array1.size()-1) // CHECKS IF ARRAY2 DID NOT FIND A MATCH            {                doSomething();                break;            }        }    }}选项Barray1 size is 1000array2 size is 2000    for(int i = 0; i < array1.size(); i++)    {        for(int j = 0; j < array2.size(); j++) {            if(array1[i].method() == array2[j].method()) // CHECKS IF THERE'S AN EQUAL IN BOTH ARRAYS            {                doSomething();                break;            }            if(j == array2.size-1)  // CHECKS IF ARRAY1 HAS NO ARRAY2 MATCH            {                doSomething();                break;            }        }    }    for(int j = 0; j < array2.size(); j++)    {        for(int i = 0; i < array1.size(); i++) {            if(array2[j].method() == array1[i].method()) // CHECKS IF THERE'S AN EQUAL IN BOTH ARRAYS            {                // BUT DOES NOTHING BECAUSE IT WAS DONE ALREADY UPSIDE                break;            }            if(i == array1.size-1) // CHECKS IF ARRAY2 HAS NO ARRAY1 MATCH            {                doSomething();                break;            }        }    }我目前已经实施了选项 B，我想知道我是否应该转向选项 A，因为尽管选项 A 可能需要更多时间，但我不知道是执行两个循环还是执行所有迭代需要更多时间。或者也许是一样的，我真的不知道。

Answer 1

选项 A是 O(x^2*y) 选项 B是 O(x*y) 在您的情况下，选项 A 最多需要 2,000,000,000 次迭代，而 B 最多需要 4,000,000 次迭代。这当然不包括休息或继续。我可能会坚持 B。

Answer 2

你也会从循环中的函数调用中获得很多收获，例如

int n= array.size()

for(int i=0; i<n; i++)

而不是

 for(int i=0; i<array.size(); i++)

除非您在循环内修改数组大小，否则重复的函数调用是一种浪费。

Answer 3

我确实想知道是否有某种编译器机制可以发现这样一个事实，即循环初始化中 size() 的返回值可能是常量，因此可以替换为“有效最终”常量. 因此，我运行了以下两个循环，第一个没有手动持续优化：

int n1=a1.size();

for(int i=0; i<a1.size(); i++) {

    int n2=a2.size();

    for(int j=0; j<a2.size(); j++) {

        int n3=a3.size();

        for(int k=0; k<a3.size(); k++) {

            int candidate=a1.get(i)*a2.get(j)*a3.get(k);

            candidate+=n1*n2*n3;

            func(candidate);

        }//k

    }//j

}//i

第二个是手动不断优化：

int n1=a1.size();

for(int i=0; i<n1; i++) {

    int n2=a2.size();

    for(int j=0; j<n2; j++) {

        int n3=a3.size();

        for(int k=0; k<n3; k++) {

            int candidate=a1.get(i)*a2.get(j)*a3.get(k);

            candidate+=n1*n2*n3;

            func(candidate);

        }//k

    }//j

}//i

然后，我使用 a1.size()=100、a2.size()=200 和 a3.size()=300 运行这些循环 10 次以获得时间，并计算每个变量的 100 次的平均误差和标准误差具有 200 次运行顺序的循环是随机的。

整个过程在单个作业（即 JVM 的一次调用）中重复 10 次，以获得 10 对均值和标准误差（一对来自优化运行的成员，另一个来自未优化运行的成员）。在所有 10 个案例中，优化的平均时间都比未优化的平均时间快得多。在每种情况下，平均值之间的差异都超过标准误差的 6.9 倍，并且在 10 个案例中的 7 个案例中，平均值之间的差异超过 15 个标准误差。数据如下。为循环生成的字节码是不同的，虽然我不声称会说字节码，但还有对 a*.size() 的额外 invokevirtual 调用，我认为这是造成两个循环版本性能差异的原因。

因此，考虑到 @Turing85 的评论，我想知道在什么情况下可以忽略“在这个级别上”的优化？

openjdk 版本“11” 2018-09-25 OpenJDK Runtime Environment 18.9 (build 11+28) OpenJDK 64-Bit Server VM 18.9 (build 11+28, mixed mode)

======数据======

优化循环运行 100 次平均每次耗时 6.412 秒，标准误差为 0.013；100 次未优化的循环运行平均每次耗时 6.502 秒，标准误差为 0.013

优化循环运行 100 次平均每次耗时 5.143 秒，标准误差为 0.004；100 次未优化的循环运行平均每次耗时 5.232 秒，标准误差为 0.005

优化循环的 100 次运行平均每次耗时 6.090 秒，标准误差为 0.006；100 次未优化的循环运行平均每次耗时 6.175 秒，标准误差为 0.006

优化循环的 100 次运行平均每次耗时 5.739 秒，标准误差为 0.005；100 次未优化的循环运行平均每次耗时 5.827 秒，标准误差为 0.005

优化循环的 100 次运行平均每次耗时 5.613 秒，标准误差为 0.005；100 次未优化的循环运行平均每次耗时 5.697 秒，标准误差为 0.004

100 次优化循环运行平均每次耗时 6.045 秒，标准误差 0.004；100 次未优化的循环运行平均每次耗时 6.121 秒，标准误差为 0.004

100 次优化循环运行平均每次耗时 5.333 秒，标准误差 0.003；100 次未优化的循环运行平均每次耗时 5.415 秒，标准误差为 0.003

100 次优化循环运行平均每次耗时 5.903 秒，标准误差为 0.009；100 次未优化的循环运行平均每次耗时 5.972 秒，标准误差为 0.007

优化循环的 100 次运行平均每次耗时 5.770 秒，标准误差为 0.005；100 次未优化的循环运行平均每次耗时 5.851 秒，标准误差为 0.005

100 次优化循环运行平均每次耗时 4.975 秒，标准误差为 0.004；100 次未优化的循环运行平均每次耗时 5.052 秒，标准误差为 0.004