英文:
Does dividing an array into halfs improve performance or processing time?
问题
我对此感到好奇。
我理解遍历数组中的所有项将会花费O(n)的时间。将数组分成下面所示的两半，是否会在任何方面提高性能呢？
final int[] array = new int[] {1, 2, 3, 4, 5, 6, 7};
for (int frontIndex = 0, rareIndex = array.length - 1; frontIndex <= array.length / 2; ++frontIndex, --rareIndex) {
if (frontIndex != rareIndex) {
int rearValue = array[rareIndex];
System.out.println(rearValue);
}
int frontValue = array[frontIndex];
System.out.println(frontValue);
}
英文:
I'm curious about this.
I understand it will cost O(n) time to iterate through all the items in an array. Will dividing the array into half as shown below, improve the performance in any way?
final int[] array = new int[] {1, 2, 3, 4, 5, 6, 7};
for (int frontIndex = 0, rareIndex = array.length - 1; frontIndex <= array.length / 2; ++frontIndex, --rearIndex) {
if (frontIndex != rearIndex) {
int rearValue = array[rearIndex];
System.out.println(rearValue);
}
int frontValue = array[frontIndex];
System.out.println(frontValue);
}
答案1
得分: 3
以下是翻译好的内容：
-
如果你将你的版本中的增量、测试和数组获取的次数相加，并将其与代码简化版本中的等效次数进行比较，我认为你会得到相同的数字...或者足够接近，以至于几乎没有什么区别。
-
你的代码的更复杂版本可能会更难让JIT编译器进行优化。例如，JIT编译器更不太可能决定展开循环。
-
不同的内存访问模式可能会导致更多的缓存未命中，更多的流水线停顿，从而降低性能。
需要注意的是，对上述情况的分析需要仔细详细地检查JIT编译器生成的本机代码。这需要很多工作。
我不同意@VLAZ的评论，即这是O(n/2)与O(n)的比较。首先，它们是同一件事。其次，这取决于您将什么视为计算的单位。VLAZ似乎在计算循环迭代次数，但他忽视了循环体的工作量是简化版本的两倍多。
接下来，这可能是过早优化的表现。标准建议是将优化留给编译器。首先确保代码功能完整并正常工作。然后测量性能。只有在测量显示出性能问题时，才手动优化代码。然后使用分析器找出热点/性能瓶颈。优化瓶颈，不要费力优化对性能影响很小的代码。（做点数学运算！）
最后，唯一确定的方法是编写微基准测试，以比较两个版本的性能。如果你要这样做：
-
不要在循环中放置打印语句。（打印N个数字所花费的时间远远大于循环。）
-
使用现有的基准测试框架，比如JMH。
-
阅读：https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java ... 以避免在第一次进行这种操作时通常会犯的尴尬错误。
英文:
It is unlikely to make the code faster.
-
If you add up the number of increments, tests and array fetches in your version and compare them with equivalent counts in the simpler version of the code, I think that you will get the same numbers ... or close enough that it makes very little difference.
-
Your more complicated version of the code is likely to be harder for a JIT compiler to optimize. For example it is less likely for the JIT compiler to decide that it could unroll the loop.
-
It is possible that the different memory access pattern could lead to more cache misses, more pipeline stalls and therefore reduced performance.
Note that analysis of the above would need careful and detailed examination of the native code generated by the JIT compiler. Too much work.
<sup>I disagree with @VLAZ's comment that this is O(n/2) vs O(n). Firstly, they are the same thing. Secondly, it depends on what you count as a unit of computation. VLAZ seems to be counting loop iterations, but he is missing the fact that the loop body is doing more than twice the work as in the simple version.</sup>
Next, this smells of premature optimization. Standard advice is to leave the optimization to the compiler. First get the code function complete and working. Then measure the performance. Only hand optimize your code if the measurement shows that you do have a performance problem. Then use a profiler to figure out the hotspots / performance bottlenecks. Then optimize the bottlenecks, and don't bother optimizing code that has minimal effect on performance. (Do the math!)
Finally, the only way to know for sure is to write a micro-benchmark to compare the performance of the two versions. If you are going to do that:
-
Don't put print statements in the loop. (The time taken to print N numbers is many orders of magnitude larger than the looping.)
-
Use an existing benchmarking framework like JMH.
-
Read: https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java ... to avoid the embarrassing mistakes that people typically make when they doing this kind of thing for the first time.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论