作为测试一些代码的附带结果,我写了一个小函数来比较使用array.push(value)
方法和直接寻址array[n] = value
的速度。令我惊讶的是,push方法经常显示更快,尤其是在Firefox中,有时在Chrome中。有人能解释吗?
测试如下(注意:2023年2月10日重写)
const arrLen = 10_000;
const x = [...Array(10)].map( (_, i) => testArr(arrLen, i));
console.log(`Array length: ${arrLen}\n--------\n${x.join(`\n`)}`);
function testArr(n, action) {
let arr = [];
const perfStart = performance.now();
const methods =
` for (; n; n--) arr.push(n)
for (; i < n; i += 1) { arr[i] = i; }
for (; i < n; i += 1) arr.push(i)
while (--n) arr.push(n)
while (i++ < n) arr.push(n)
while (--n) arr.splice(0, 0, n)
while (--n) arr.unshift(n)
while (++i < n) arr.unshift(i)
while (--n) arr.splice(n - 1, 0, n)
while (n--) arr[n] = n`.split(`\n`).map(v => v.trim());
const report = i => `${methods[i]}: ${
(performance.now() - perfStart).toFixed(2)} milliseconds`;
let i = 0;
switch (action) {
case 0: for (; n; n--) arr.push(n)
case 1: for (; i < n; i += 1) { arr[i] = i; } break;
case 2: for (let i = 0; i < n; i += 1) arr.push(i); break;
case 3: while (--n) arr.push(n); break;
case 4: while (i++ < n) arr.push(n); break;
case 5: while (--n) arr.splice(0, 0, n); break;
case 6: while (--n) arr.unshift(n)
case 7: while (++i < n) arr.unshift(i); break;
case 8: while (--n) arr.splice(n - 1, 0, n); break;
default: while (n--) arr[n] = n;
}
return report(action);
}
.as-console-wrapper {
max-height: 100% !important;
}
6条答案
按热度按时间hrirmatl1#
各种各样的因素都在起作用,大多数JS实现使用平面数组,如果以后需要的话,它会转换为稀疏存储。
基本上,稀疏化的决定是一个启发式的决定,它基于要设置哪些元素,以及为了保持平坦将浪费多少空间。
在您的例子中,您首先设置了最后一个元素,这意味着JS引擎将看到一个长度为
n
的数组,但只有一个元素。如果n
足够大,这将立即使数组成为稀疏数组--在大多数引擎中,这意味着所有后续插入将采取缓慢的稀疏数组情况。您应该添加一个额外的测试,从索引0到索引n-1填充数组--这样应该快得多。
作为对@Christoph的回应,出于拖延的愿望,这里描述了数组(通常)是如何在JS中实现的--具体细节因JS引擎而异,但一般原理是相同的。
所有的JS
Object
(所以不是字符串、数字、true、false、undefined
或null
)都继承自一个基对象类型--具体的实现各不相同,可以是C++继承,也可以在C中手动继承(无论哪种方式都有好处)--基对象类型定义默认的属性访问方法,例如此Object类型处理所有标准属性访问逻辑、原型链等。然后,Array实现变为
现在,当你在JS中创建一个Array时,引擎会创建类似于上面的数据结构,当你在Array示例中插入一个对象时,Array的put方法会检查属性名是否为整数(或可转换为整数,例如“121”、“2341”等),介于0和2^32-1之间(或者可能是2^31-1,我忘记了)如果不是,那么put方法被转发到基本Object实现,并且标准的Put逻辑被完成,否则值被放入Array自己的存储器中,如果数据足够紧凑,则引擎将使用平面数组存储,在这种情况下,插入(和检索)只是标准数组索引操作,否则引擎将把数组转换成稀疏存储,并且put/get使用Map来从propertyName到value location。
老实说,我不确定当前是否有JS引擎在转换发生后将稀疏存储转换为平面存储。
无论如何,这是一个相当高层次的概述,省略了一些更令人讨厌的细节,但这是一般的实现模式。如何分配额外的存储,以及如何放置/获取的细节在引擎之间是不同的--但这是我所能真正描述的最清楚的设计/实现。
一个小的补充点,虽然ES规范将
propertyName
称为字符串,但JS引擎也倾向于专门进行整数查找,因此如果您正在查看具有整数属性(例如,Array、String和DOM类型(NodeList
s等))的对象,someObject[someInteger]
不会将整数转换为字符串。osh3o9ms2#
这是我从你的测试中得到的结果
在Safari上:
在火狐上:
在IE7上:
根据您的测试,push 方法似乎在IE7上更好(巨大的差异),由于在其他浏览器上差异很小,因此 push 方法似乎是向数组添加元素的最佳方法。
但是我创建了另一个simple test script来检查什么方法可以快速地向数组中添加值,结果真的让我很惊讶,使用Array.length似乎比使用Array.push快得多,所以我真的不知道该说什么或想什么了,我一无所知。
vyu0f0g13#
push()
是更一般的Put的特例,因此可以进一步优化:当对数组对象调用Put时,参数必须首先转换为无符号整数,因为所有属性名(包括数组索引)都是字符串。然后,必须将其与数组的length属性进行比较,以确定是否需要增加长度。当推送时,不需要进行此类转换或比较:只要使用当前长度作为数组索引并增加它。
当然,还有其他一些事情会影响运行时,例如调用
push()
应该比通过[]
调用Put慢,因为必须检查原型链中的前者。正如奥利耶所指出的:实际的ECMAScript实现将优化转换,即对于数字属性名,不进行从string到uint的转换,而只是简单的类型检查。2基本假设应该仍然成立,尽管它的影响将比我最初假设的要小。
mzillmmw4#
下面是一个很好的测试平台,它证实了直接赋值明显比推送快:http://jsperf.com/array-direct-assignment-vs-push.
编辑:在显示累积结果数据方面似乎有一些问题,但希望很快得到修复。
py49o6xq5#
array[n] = value
在先前初始化为一个长度(如new Array(n)
)时比array.push
在n >= 90
时上升快。通过检查your page的javascript源代码,您的
Array[0 .. n] = value (ascending)
测试没有预先使用长度初始化数组。因此,
Array.push(n)
有时在第一次运行时会领先,但在随后的测试运行中,Array[0 .. n] = value (ascending)
实际上一直表现最好(在Safari和Chrome中)。如果修改代码,使其预先初始化一个长度为
var array = new Array(n)
的数组,则Array[0 .. n] = value (ascending)
显示**array[n] = value
比Array.push(n)
**在此特定测试代码的初步运行中快4.5倍到9倍。这与@Timo Kähkönen报道的其他测试一致,具体参见他提到的测试的修订版:https://jsperf.com/push-method-vs-setting-via-key/10
修改后的代码,所以你可以看到我如何编辑它,并以公平的方式初始化数组(没有必要用数组的长度初始化它。推送测试用例):
zaq34kh66#
Push将其添加到末尾,而array[n]必须遍历数组才能找到正确的位置。可能取决于浏览器及其处理数组的方式。