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

有趣，我做了类似的事情

if (i % 1000 === 0) {
    console.log(i + " " + stopwatch.elapsedMilliseconds + " : " + a.length);
}

在第二个循环中。（这计算起来很痛苦，但它有助于诊断问题）

我没有遭受性能损失。但是，我认为，我发现了为什么 "only" 2000 多件事情对 node 来说那么难。首先-我的区别： [循环最大数量，单位，3 个基准测试结果]

70k: [ms] ~26k, ~25.7k, ~26k 72k: [毫秒] ~25.6k, 27k, 25.7k

好的，正如我看到的日志记录，我看到，最近的 10k 条记录是即时计算的。我认为 splice 从前面删除 1 个项目，然后 - 一个一个地移动数组 1 索引 "to the start"，让我们将测试更改为 10 个数组，每个数组有 10k 条记录，看看它是否会很多更好的。我会用最懒的方式来做：

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

var a1 = [], a2 = [], a3 = [], a4 = [], a5 = [];
var a6 = [], a7 = [], a8 = [], a9 = [], a10 = [];

stopwatch.start();

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

fill(a1); fill(a2); fill(a3); fill(a4); fill(a5);
fill(a6); fill(a7); fill(a8); fill(a9); fill(a10);

let removeCount = 0;
function unfill(arr) {
    for (var i = 1 ; i < 10000 ; i++){
        arr.splice(0,1);
        removeCount++;

        if (i % 1000 === 0) {
            console.log(i + " " + stopwatch.elapsedMilliseconds + " : " + arr.length);
        }
    }
}

unfill(a1); unfill(a2); unfill(a3); unfill(a4); unfill(a5);
unfill(a6); unfill(a7); unfill(a8); unfill(a9); unfill(a10);

stopwatch.stop();

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

而且，是的......我没有回答为什么你的电脑在 70k 和 72k 记录之间有这样的性能损失 - 我相信它是机器依赖的......可能缺少 RAM，但不明白错了-我不知道。

我解决了如何改进它。 10 个数组上的 100k(-10) 执行时间约为 73-74 毫秒。我认为，您可以将其写入二维数组并修改逻辑以根据需要计算长度和其他内容。

感谢关注。

Answer 2

这里是 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 可以在引擎盖下使用一个技巧，即移动对象的开头——在快速的情况下，您可以看到这个技巧提供的惊人加速。但是，由于技术原因，这个技巧不能应用于超过一定大小的数组。结果 "slowdown" 实际上是这个非常昂贵的操作的 "true" 速度。

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

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))。（出于本次测试的目的，您也可以简单地按 i。）

node.js 超过 70000 个项目的拼接速度太慢

node.js splice too slow for more than 70000 items

arrays

v8

node.js