给定一个具有.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");
jsperfhttps://jsperf.com/iterate-from-start-iterate-from-start-and-end/1
答案很明显:
更多的操作需要更多的时间
当判断代码的速度时,你要看它将执行多少操作。走过去数数。每条指令都将花费一个或多个CPU周期,并且周期越多,运行时间就越长。不同的指令需要不同的周期,这基本上无关紧要——虽然数组查找可能比整数运算更昂贵,但两者基本上都需要恒定的时间,如果太多,它会主导我们算法的成本。
在您的示例中,有几种不同类型的操作可能需要单独计数:
- 比较
- 增量/减量
- 阵列查找
- 条件跳跃
(我们可以更精细,比如计算变量的获取和存储操作,但这些都无关紧要——所有的东西都在寄存器中——它们的数量基本上与其他的是线性的)。
现在,两个代码都迭代了大约50次——它们中断循环的元素位于数组的中间。忽略一些错误,这些就是计数:
| forwards | forwards and backwards
---------------+------------+------------------------
>=/===/< | 100 | 200
++/-- | 50 | 100
a[b] | 50 | 100
&&/||/if/for | 100 | 200
考虑到这一点,做两次工作需要相当长的时间,这并不意外。
我还将回答您评论中的几个问题:
第二次查找对象是否需要额外的时间?
是的,每个单独的查找都很重要。它们不可能一次执行,也不可能优化为一次查找(如果它们查找了相同的索引,可以想象)。
每个开始到结束和结束到开始应该有两个单独的循环吗?
操作的数量无关紧要,只取决于它们的顺序。
或者,换言之,在数组中查找元素的最快方法是什么?
;"最快";关于顺序,如果你不知道元素在哪里(而且它们是均匀分布的),你必须尝试每个索引。任何订单——即使是随机订单——都会起到同样的作用。然而,请注意,您的代码严格来说更糟,因为当找不到元素时,它会两次查看每个索引——它不会在在中间停止。
但是,在微观优化这样一个循环时,仍然有一些不同的方法——检查这些基准。
let
(仍然?)比var
慢,请参阅为什么在Chrome上的"for"循环中使用"let"如此慢?以及为什么在nodejs中的for循环中let比var慢?。事实上,循环体作用域的这种分解(大约50倍)确实主导了您的运行时——这就是为什么低效代码的速度不会完全慢一倍的原因- 与
0
相比稍微快于与长度相比,这使得向后循环具有优势。请参阅为什么向后迭代数组比向前迭代快,JavaScript循环性能-为什么向0递减迭代器比递增迭代器快,循环真的反向更快吗 - 一般来说,请参阅What';用JavaScript循环数组的最快方法是什么?:它从引擎更新变为引擎更新。不要做任何奇怪的事情,编写惯用代码,这会得到更好的优化
@Bergi是正确的。更多的操作意味着更多的时间。为什么?更多的CPU时钟周期。时间实际上是指执行代码所需的时钟周期。为了了解其实质,您需要查看机器级代码(如程序集级代码),以找到真正的证据。每个CPU(核心?)时钟周期可以执行一条指令,那么你执行了多少条指令?
自从为嵌入式应用程序编程摩托罗拉CPU以来,我已经很久没有计算过时钟周期了。如果你的代码花费的时间更长,那么它实际上是在生成一个更大的机器代码指令集,即使循环更短或运行的次数相等。
永远不要忘记,你的代码实际上是被编译成CPU将要执行的一组命令(内存指针、指令代码级指针、中断等)。这就是计算机的工作方式,在ARM或摩托罗拉处理器等微控制器级别更容易理解,但我们今天运行的复杂机器也是如此。
你的代码根本没有按照你写的方式运行(听起来很疯狂,对吧?)。它是在编译为机器级指令时运行的(编写编译器一点都不好玩)。数学表达式和逻辑可以编译成一堆汇编、机器级代码,这取决于编译器选择如何解释它(这是位偏移等,还记得二进制数学吗?)
参考:https://software.intel.com/en-us/articles/introduction-to-x64-assembly
你的问题很难回答,但正如@Bergi所说,手术越多,时间越长,但为什么?执行代码所需的时钟周期越多。双核、四核、线程、汇编(机器语言)它很复杂。但没有代码能像你写的那样被执行。C++、C、Pascal、JavaScript、Java,除非你是在汇编中写的(即使是编译成机器代码的),但它更接近实际执行代码。
一个CS大师,你将开始计算时钟周期和排序时间。你可能会让你自己的语言框架在机器指令集上。
大多数人说谁在乎?如今内存很便宜,CPU也越来越快
但是,在一些关键应用中,10ms很重要,需要立即中断,等等。
商业,美国国家航空航天局,核电站,国防承包商,一些机器人,你明白了。
我投票让它继续前进。
干杯,伍基
由于您要查找的元素总是大致位于数组的中间,因此您应该期望从数组的开始和结束向内走的版本所需的时间大约是从开始走的版本的两倍。
每个变量更新都需要时间,每个比较都需要时间。由于您知道在这个版本中,循环的迭代将减少一到两次才能终止,因此您应该推断它将花费大约两倍的CPU时间。
这种策略仍然是O(n)
时间复杂性,因为它只看每个项目一次,当项目靠近列表中心时,情况会更糟。如果接近尾声,这种方法将有一个更好的预期运行时间。例如,试着在两者中查找项目90。
所选答案非常好。我想添加另一个方面:试试findIndex()
,它比使用循环快2-3倍:
const arr = Array.from({length: 900}, (_, 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");
console.time("iterate using findIndex");
var i = arr.findIndex(function(v) {
return v === n;
});
console.timeEnd("iterate using findIndex");
这里的其他答案涵盖了主要原因,但我认为一个有趣的补充可能是提到缓存。
通常,顺序访问阵列将更高效,尤其是对于大型阵列。当您的CPU从内存中读取数组时,它还会将附近的内存位置提取到缓存中。这意味着,当您获取元素n
时,元素n+1
也可能被加载到缓存中。现在,缓存相对来说大,所以你的100 int数组可能可以很舒服地放在缓存中。然而,在尺寸大得多的阵列上,按顺序读取将比在阵列的开头和结尾之间切换更快。