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

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

鉴于此,做两倍的工作需要相当长的时间并不出人意料.

我还会回答你的评论中的几个问题:

第二个对象查找需要额外的时间吗？

是的,每个查找都很重要.它不像是可以立即执行,也不是优化为单个查找(如果它们查找了相同的索引,则可以想象).

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

操作次数无关紧要,仅适用于他们的订单.

或者,换句话说,在数组中查找元素的最快方法是什么？

关于订单没有"最快",如果你不知道元素的位置(并且它们是均匀分布的),你必须尝试每个索引.任何订单 - 甚至是随机订单 - 都会起作用.但请注意,您的代码严格更差,因为它在找不到元素时会查看每个索引两次 - 它不会在中间停止.

但是,微观优化这种循环还有一些不同的方法 - 检查这些基准.

• let是(仍然？)慢var,请参阅为什么在`for`循环中使用`let`在Chrome上这么慢？而为什么我们比VAR慢的在循环的NodeJS？.事实上,循环体范围的这种撕裂(大约50次)确实占据了运行时间 - 这就是为什么你的低效代码不是完全慢两倍的原因.
• 比较与0长度相比稍微快一些,这使得循环向后有利.请参阅为什么迭代向后迭代数组的速度要快得多,JavaScript循环性能 - 为什么迭代器的递减速度比递增速度快0并且循环的反转速度真的更快？
• 一般来说,看看在JavaScript中循环数组的最快方法是什么？:它从引擎更新变为引擎更新.不要做任何奇怪的事情,编写惯用的代码,这将是更好的优化.