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

Question

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

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

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

Answer 1

答案很明显:

更多操作需要更多时间。

当判断代码的速度时，你会看它会执行多少个操作。只需逐步执行并数一下即可。每条指令都会占用一个或多个CPU周期，并且周期越多，运行时间就越长。不同的指令占用不同数量的周期通常并不重要 - 虽然数组查找可能比整数运算成本更高，但它们基本上都需要恒定的时间，如果太多，它就会主导我们算法的成本。

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

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

(我们可以更精细，例如计算变量获取和存储操作，但这些并不重要 - 无论如何，所有内容都在寄存器中 - 并且它们的数量基本上与其他数量呈线性)。

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

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

鉴于此，完成两倍的工作需要相当长的时间，这并不意外。

我还将回答您评论中的几个问题:

Is additional time needed for the second object lookup?

是的，每次单独的查找都很重要。它们不像可以立即执行，也不能优化为单次查找(可以想象，如果它们查找相同的索引)。

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

与操作数量无关，只与操作顺序有关。

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

关于顺序没有“最快”，如果您不知道元素在哪里(并且它们均匀分布)，您必须尝试每个索引。任何顺序 - 即使是随机的 - 都会起到同样的作用。但请注意，您的代码更糟糕，因为当未找到该元素时，它会查看每个索引两次 - 它不会在中间停止。

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

• let(仍然？)比 var 慢，请参阅 Why is using `let` inside a `for` loop so slow on Chrome?和 Why is let slower than var in a for loop in nodejs? 。事实上，循环体作用域的这种拆卸和拆卸(大约 50 次)确实主宰了您的运行时 - 这就是为什么您的低效代码不会完全慢两倍的原因。
• 与 0 进行比较比与长度进行比较要快一些，这使得向后循环具有优势。请参阅Why is iterating through an array backwards faster than forwards , JavaScript loop performance - Why is to decrement the iterator toward 0 faster than incrementing和 Are loops really faster in reverse?
• 一般情况下，请参阅What's the fastest way to loop through an array in JavaScript? :从引擎更新变为引擎更新。不要做任何奇怪的事情，编写惯用的代码，这样才能得到更好的优化。