javascript 为什么array.push有时比array[n] = value快?

i7uaboj4  于 2023-02-11  发布在  Java
关注(0)|答案(6)|浏览(143)

作为测试一些代码的附带结果,我写了一个小函数来比较使用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;
}
hrirmatl

hrirmatl1#

各种各样的因素都在起作用,大多数JS实现使用平面数组,如果以后需要的话,它会转换为稀疏存储。
基本上,稀疏化的决定是一个启发式的决定,它基于要设置哪些元素,以及为了保持平坦将浪费多少空间。
在您的例子中,您首先设置了最后一个元素,这意味着JS引擎将看到一个长度为n的数组,但只有一个元素。如果n足够大,这将立即使数组成为稀疏数组--在大多数引擎中,这意味着所有后续插入将采取缓慢的稀疏数组情况。
您应该添加一个额外的测试,从索引0到索引n-1填充数组--这样应该快得多。
作为对@Christoph的回应,出于拖延的愿望,这里描述了数组(通常)是如何在JS中实现的--具体细节因JS引擎而异,但一般原理是相同的。
所有的JS Object(所以不是字符串、数字、true、false、undefinednull)都继承自一个基对象类型--具体的实现各不相同,可以是C++继承,也可以在C中手动继承(无论哪种方式都有好处)--基对象类型定义默认的属性访问方法,例如

interface Object {
    put(propertyName, value)
    get(propertyName)
private:
    map properties; // a map (tree, hash table, whatever) from propertyName to value
}

此Object类型处理所有标准属性访问逻辑、原型链等。然后,Array实现变为

interface Array : Object {
    override put(propertyName, value)
    override get(propertyName)
private:
    map sparseStorage; // a map between integer indices and values
    value[] flatStorage; // basically a native array of values with a 1:1
                         // correspondance between JS index and storage index
    value length; // The `length` of the js 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]不会将整数转换为字符串。

osh3o9ms

osh3o9ms2#

这是我从你的测试中得到的结果
在Safari上:

  • 数组。push(n)1,000,000个值:0.124秒
  • 数组[n .. 0] =值(降序)1,000,000个值:三点六九七秒
  • 数组[0 .. n] =值(升序)1,000,000个值:0.073秒

在火狐上:

  • 数组。push(n)1,000,000个值:0.075秒
  • 数组[n .. 0] =值(降序)1,000,000个值:1.193秒
  • 数组[0 .. n] =值(升序)1,000,000个值:0.055秒

在IE7上:

  • 数组。push(n)1,000,000个值:二点八二八秒
  • 数组[n .. 0] =值(降序)1,000,000个值:1.141秒
  • 数组[0 .. n] =值(升序)1,000,000个值:七点九八四秒

根据您的测试push 方法似乎在IE7上更好(巨大的差异),由于在其他浏览器上差异很小,因此 push 方法似乎是向数组添加元素的最佳方法。
但是我创建了另一个simple test script来检查什么方法可以快速地向数组中添加值,结果真的让我很惊讶,使用Array.length似乎比使用Array.push快得多,所以我真的不知道该说什么或想什么了,我一无所知。

  • 顺便说一句:在我的IE7上,你的脚本停止了,浏览器问我是否想让它继续(你知道典型的IE消息是这样说的:“停止运行此脚本?...”)我建议减少一些循环。*
vyu0f0g1

vyu0f0g13#

push()是更一般的Put的特例,因此可以进一步优化:
当对数组对象调用Put时,参数必须首先转换为无符号整数,因为所有属性名(包括数组索引)都是字符串。然后,必须将其与数组的length属性进行比较,以确定是否需要增加长度。当推送时,不需要进行此类转换或比较:只要使用当前长度作为数组索引并增加它。
当然,还有其他一些事情会影响运行时,例如调用push()应该比通过[]调用Put慢,因为必须检查原型链中的前者。
正如奥利耶所指出的:实际的ECMAScript实现将优化转换,即对于数字属性名,不进行从string到uint的转换,而只是简单的类型检查。2基本假设应该仍然成立,尽管它的影响将比我最初假设的要小。

mzillmmw

mzillmmw4#

下面是一个很好的测试平台,它证实了直接赋值明显比推送快:http://jsperf.com/array-direct-assignment-vs-push.
编辑:在显示累积结果数据方面似乎有一些问题,但希望很快得到修复。

py49o6xq

py49o6xq5#

array[n] = value在先前初始化为一个长度(如new Array(n))时比array.pushn >= 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] = valueArray.push(n)**在此特定测试代码的初步运行中快4.5倍到9倍。
这与@Timo Kähkönen报道的其他测试一致,具体参见他提到的测试的修订版:https://jsperf.com/push-method-vs-setting-via-key/10
修改后的代码,所以你可以看到我如何编辑它,并以公平的方式初始化数组(没有必要用数组的长度初始化它。推送测试用例):

function testArr(n, doPush){

  var now = new Date().getTime(),
                  duration,
                  report =  ['<b>.push(n)</b>',
                             '<b>.splice(0,0,n)</b>',
                             '<b>.splice(n-1,0,n)</b>',
                             '<b>[0 .. n] = value</b> (ascending)',
                             '<b>[n .. 0] = value</b> (descending)'];
  doPush = doPush || 5;

  if (doPush === 1) {
   var arr = [];
   while (--n) {
     arr.push(n);
   }
  } else if (doPush === 2) {
   var arr = [];
   while (--n) {
    arr.splice(0,0,n);
   }
  } else if (doPush === 3) {
   var arr = [];
   while (--n) {
    arr.splice(n-1,0,n);
   }
  } else if (doPush === 4) {
   var arr = new Array(n);
   for (var i = 0;i<n;i++) {
    arr[i] = i;
   }
  } else {
    while (--n) {
    var arr = [];
      arr[n] = n;
    }
  }
  /*console.log(report[doPush-1] + '...'+ arr.length || 'nopes');*/
  duration = ((new Date().getTime() - now)/1000);
  $('zebradinges').innerHTML +=  '<br>Array'+report[doPush-1]+' 1.000.000 values: '+duration+' sec' ;
  arr = null;
}
zaq34kh6

zaq34kh66#

Push将其添加到末尾,而array[n]必须遍历数组才能找到正确的位置。可能取决于浏览器及其处理数组的方式。

相关问题