node.jsスプライスが70000を超えるアイテムに対して遅すぎる

Question

私はnode.jsの初心者です。

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 

しかし、ときに私は

iは配列に70000の項目を挿入し、それらのすべてを削除しようとしましたアイテムの数を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; 
} 

---

サイドノート：大雑把にそれはここでは問題ではなく、記録のために、あなたの配列に7万要素をプッシュしていない、あなたのループは0で開始する必要があります：for (var i = 0; i < 70000; i++) {...}。書かれているように、あなたは69,999要素を押すだけです。

サイドノート2： "parseInt"を使用してdoubleを整数に丸めるのはかなり遅いです。これは最初にダブルを文字列としてフォーマットし、その文字列を整数として戻すためです。より速い方法はMath.floor(Math.random() * 10000))です。このテストの目的で、iを単に押すこともできます。

Answer 2

興味深い、私は第二ループ内

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

のような何かをしました。 （これは計算には痛ましいですが、問題の診断に役立ちます）

パフォーマンスの低下はありませんでした。しかし、私は、なぜ2000年以上のことがノードにとっては難しいのかということを知りました。まず - 私の違い： [ループの最大NUM、ユニット、3つのベンチマーク結果]

70K：[ミリ秒]〜26K、〜25.7k、〜26K 72K：[ミリ秒]〜25.6k、27K、25.7k

さて、ロギングを見たとき、私はそれを見ました。最後の10kレコードは即座に計算されます。私はspliceが先頭から1つの項目を取り除き、次に1つずつ配列1のインデックスを「先頭に」シフトして、10kレコードごとに10個の配列にテストを変更してみましょう。私はほとんどの怠惰な方法でこれを行います。

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); 

そして、はい...私はなぜexaclyあなたのPCに答えなかった70Kと72Kレコード間、このようなパフォーマンスの低下を持っている - 私はそれがマシンに依存するものです信じ..おそらくRAMが不足しているかもしれませんが、間違ってはいません。わかりません。

私はそれを改善する方法を解決しました。 10アレイ実行時間の100k（-10）は約73-74msでした。私は、あなたは2次元配列に書き込んで、長さと残りのものをあなたが望むように計算するロジックを変更することができると思います。

ありがとうございました。