为什么使用循环从数组的开始迭代到结束比迭代开始到结束和结束到开始更快? [英] Why is using a loop to iterate from start of array to end faster than iterating both start to end and end to start?

问题描述

给定一个具有 .length 100 的数组，其中包含在相应索引处具有 0 到 99 值的元素，其中要求是找到等于 n 的数组元素:51.

Given an array having .length 100 containing elements having values 0 to 99 at the respective indexes, where the requirement is to find element of of array equal to n : 51.

为什么使用循环从数组的开始迭代到结束比迭代开始到结束和结束到开始更快?

Why is using a loop to iterate from start of array to end faster than iterating both start to end and end to start?

const arr = Array.from({length: 100}, (_, i) => i);
const n = 51;
const len = arr.length;

console.time("iterate from start");
for (let i = 0; i < len; i++) {
  if (arr[i] === n) break;
}
console.timeEnd("iterate from start");

const arr = Array.from({length: 100}, (_, i) => i);
const n = 51;
const len = arr.length;

console.time("iterate from start and end");
for (let i = 0, k = len - 1; i < len && k >= 0; i++, k--) {
  if (arr[i] === n || arr[k] === n) break;
}
console.timeEnd("iterate from start and end");

jsperf https://jsperf.com/iterate-from-start-iterate-from-start-and-end/1

推荐答案

答案很明显:

判断代码的速度时，看它会执行多少操作.只需一步一步计算它们.每条指令都将占用一个或多个 CPU 周期，并且运行时间越长.不同的指令占用不同数量的周期大多无关紧要 - 虽然数组查找可能比整数算术更昂贵，但它们基本上都需要恒定时间，如果有太多，它会主导我们算法的成本.

When judging the speed of code, you look at how many operations it will perform. Just step through and count them. Every instruction will take one or more CPU cycles, and the more there are the longer it will take to run. That different instructions take a different amount of cycles mostly does not matter - while an array lookup might be more costly than integer arithmetic, both of them basically take constant time and if there are too many, it dominates the cost of our algorithm.

在您的示例中，您可能希望单独计算几种不同类型的操作:

In your example, there are few different types of operations that you might want to count individually:

• 比较
• 递增/递减
• 数组查找
• 条件跳转

(我们可以更细化，例如计算变量获取和存储操作，但这些并不重要 - 反正一切都在寄存器中 - 它们的数量基本上与其他操作成线性关系).

(we could be more granular, such as counting variable fetch and store operations, but those hardly matter - everything is in registers anyway - and their number basically is linear to the others).

现在您的两个代码都迭代了大约 50 次 - 它们打破循环的元素位于数组的中间.忽略一些错误，这些是计数:

Now both of your codes iterate about 50 times - they element on which they break the loop is in the middle of the array. Ignoring off-by-a-few errors, those are the counts:

               |  forwards  | forwards and backwards
---------------+------------+------------------------
>=/===/<       |       100  |                   200
++/--          |        50  |                   100
a[b]           |        50  |                   100
&&/||/if/for   |       100  |                   200

考虑到这一点，并不意外做两次工作需要相当长的时间.

Given that, it's not unexpected that doing twice the works takes considerably longer.

我还会根据您的评论回答几个问题:

I'll also answer a few questions from your comments:

第二次对象查找需要额外的时间吗?

Is additional time needed for the second object lookup?

是的，每个单独的查找都很重要.它们不能一次执行，也不能优化为单个查找(可以想象，如果他们查找了相同的索引).

Yes, every individual lookup counts. It's not like they could be performed at once, or optimised into a single lookup (imaginable if they had looked up the same index).

每个开始到结束和结束到开始应该有两个单独的循环吗?

Should there be two separate loops for each start to end and end to start?

与操作数量无关，只与它们的顺序有关.

Doesn't matter for the number of operations, just for their order.

或者，换一种说法，在数组中查找元素的最快方法是什么?

Or, put differently still, what is the fastest approach to find an element in an array?

关于顺序没有最快"，如果您不知道元素在哪里(并且它们是均匀分布的)，您必须尝试每个索引.任何订单——甚至是随机订单——都一样.但是请注意，您的代码更糟糕，因为它会在未找到元素时查看每个索引两次 - 它不会停在中间.

There is no "fastest" regarding the order, if you don't know where the element is (and they are evenly distributed) you have to try every index. Any order - even random ones - would work the same. Notice however that your code is strictly worse, as it looks at each index twice when the element is not found - it does not stop in the middle.

但是，仍然有一些不同的方法可以对这样的循环进行微优化 - 检查 这些基准.

But still, there are a few different approaches at micro-optimising such a loop - check these benchmarks.

• let (仍然?)比 var 慢，请参阅 为什么在 Chrome 上的 `for` 循环中使用 `let` 这么慢? 和 为什么在 for 循环中 let 比 var 慢在 nodejs 中?.实际上，循环体范围的这种拆解(大约 50 次)确实支配了您的运行时 - 这就是为什么您的低效代码并非完全慢一倍.
• 与 0 比较比与长度比较快一点，这使得向后循环具有优势.请参阅为什么向后迭代数组比向前更快，JavaScript 循环性能 - 为什么将迭代器递减到 0 比递增更快 和 循环真的更快吗反过来?
• 一般来说，请参阅 在 JavaScript 中循环遍历数组的最快方法是什么?:它从引擎更新变为引擎更新.不要做任何奇怪的事情，编写惯用的代码，这样会得到更好的优化.

• let is (still?) slower than var, see Why is using `let` inside a `for` loop so slow on Chrome? and Why is let slower than var in a for loop in nodejs?. This tear-up and tear-down (about 50 times) of the loop body scope in fact does dominate your runtime - that's why your inefficient code isn't completely twice as slow.
• comparing against 0 is marginally faster than comparing against the length, which puts looping backwards at an advantage. See Why is iterating through an array backwards faster then forwards, JavaScript loop performance - Why is to decrement the iterator toward 0 faster than incrementing and Are loops really faster in reverse?
• in general, see What's the fastest way to loop through an array in JavaScript?: it changes from engine update to engine update. Don't do anything weird, write idiomatic code, that's what will get optimised better.

这篇关于为什么使用循环从数组的开始迭代到结束比迭代开始到结束和结束到开始更快?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！