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

查看:153
本文介绍了为什么使用循环从数组的开始迭代到结束比从开始到结束和结束开始更快地迭代?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

给定一个数组 .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:


  • 比较

  • 递增/递减

  • 数组查找

  • 条件跳转

  • comparisons
  • increments/decrements
  • array lookup
  • conditional jumps

(我们可能更精细,例如计算变量获取和存储操作,但那些几乎无关紧要 - 无论如何一切都在寄存器中 - 它们的数量基本上是与其他人线性关系。)

(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 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屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆