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 开发人员在这里。在开始（ at 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 可以在引擎盖下使用一个技巧，而不是移动对象的开头——在快速的情况下，你可以看到这个技巧提供的惊人的加速。但是，由于技术原因，此技巧不能应用于超过特定大小的数组。由此产生的“减速”实际上是这种非常昂贵的操作的“真实”速度。

如果您想快速删除数组元素，请从末尾（at 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”将双精度舍入为整数非常慢，因为它首先将双精度格式化为字符串，然后将该字符串读回为整数。更快的方法是Math.floor(Math.random() * 10000)). （为了这个测试的目的，你也可以简单地 push i。）