arrays - node.js 拼接超过 70000 个项目时速度太慢

Question

我是 node.js 的新手。

我尝试将 70000 项插入数组，然后将其全部删除:

var Stopwatch = require("node-stopwatch").Stopwatch;
var stopwatch = Stopwatch.create();


var a = []
stopwatch.start();

for (var i = 1 ; i < 70000 ; i++){
    a.push((parseInt(Math.random() * 10000)) + "test");
}

for (var i = 1 ; i < 70000 ; i++){
    a.splice(0,1);
}

stopwatch.stop();

console.log("End: " + stopwatch.elapsedMilliseconds + " : " + a.length);

它工作正常，输出是:

PS C:\Users\Documents\VSCode> node test.js
End: 51 : 0

但是当我将项目数量增加到 72000 时，结束需要太多时间:

var Stopwatch = require("node-stopwatch").Stopwatch;
var stopwatch = Stopwatch.create();


var a = []
stopwatch.start();

for (var i = 1 ; i < 72000 ; i++){
    a.push((parseInt(Math.random() * 10000)) + "test");
}

for (var i = 1 ; i < 72000 ; i++){
    a.splice(0,1);
}

stopwatch.stop();

console.log("End: " + stopwatch.elapsedMilliseconds + " : " + a.length);

输出是:

End: 9554 : 0

为什么会发生？才加了2000多条，但是太费时间了。

Node.js 版本是:v6.11.3

Answer 1

这里是 V8 开发人员。在开头(在 array[0] 处)删除(或插入)数组元素通常非常昂贵，因为必须移动所有剩余元素。本质上，引擎必须在引擎盖下为这些中的每一个做些什么 .splice(0, 1)操作是:

for (var j = 0; j < a.length - 1; j++) {
  a[j] = a[j+1];
}
a.length = a.length - 1`

在某些情况下，V8 可以在引擎盖下使用一个技巧，即移动对象的开头——在快速的情况下，您可以看到这个技巧提供的惊人加速。但是，由于技术原因，这个技巧不能应用于超过一定大小的数组。由此产生的“减速”实际上是这种非常昂贵的操作的“真实”速度。

如果要快速删除数组元素，请从末尾(在 array[array.length - 1] 处)删除它们，例如使用 Array.pop() .如果想一次性删除所有元素，设置array.length = 0即可。 .如果您需要快速 FIFO/“队列”语义，请考虑从环形缓冲区中汲取灵感:为要读取/返回的下一个元素设置一个“游标”，并且仅在有大量元素要释放时才收缩数组。大致:

function Queue() {
  this.enqueue = function(x) {
    this.array_.push(x);
  }
  this.dequeue = function() {
    var x = this.array_[this.cursor_++];
    // Free up space if half the array is unused.
    if (this.cursor_ > this.array_.length / 2) {
      this.array_.splice(0, this.cursor_);
      this.cursor_ = 0;
    }
    return x;
  }
  this.array_ = [];
  this.cursor_ = 0;
}

---

旁注:这里无关紧要，但为了记录，要将 70,000 个元素插入数组，循环应从 0: for (var i = 0; i < 70000; i++) {...} 开始。 .如所写，您仅推送 69,999 个元素。

旁注 2:通过“parseInt”将 double 舍入为整数非常慢，因为它首先将 double 格式化为字符串，然后将该字符串读回为整数。更快的方法是 Math.floor(Math.random() * 10000)) . (出于本次测试的目的，您也可以简单地按 i。)