node.js splice zbyt wolne dla więcej niż 70000 pozycji

Question

Jestem newbie in node.js.

Próbowałem wstawić 70000 elementów do tablicy, a następnie usunąć wszystkie z nich:

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

To działa dobrze i wyjście jest:

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

Ale kiedy Zwiększ liczbę pozycji do 72000, skończy się to za dużo czasu:

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

a wyjście jest:

End: 9554 : 0 

dlaczego występuje? tylko 2000 artykułów dodanych więcej, ale zajmuje to zbyt dużo czasu.

wersja

node.js jest: v6.11.3

Answer 1

Programista V8 tutaj. Usunięcie (lub wstawienie) elementów tablicy na początku (na array[0]) jest na ogół bardzo kosztowne, ponieważ wszystkie pozostałe elementy muszą zostać przeniesione.Zasadniczo, co ma zrobić silnik pod maską dla każdej z tych operacji jest .splice(0, 1):

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

W niektórych przypadkach V8 może zastosować trick pod maską, gdzie początek obiektu zostanie przeniesiona zamiast - w szybkich przypadkach widać niesamowite przyspieszenie, jakie zapewnia ta sztuczka. Jednak z przyczyn technicznych ta sztuczka nie może być stosowana do tablic przekraczających pewien rozmiar. Wynikłe "spowolnienie" jest w rzeczywistości "prawdziwą" prędkością tej bardzo kosztownej operacji.

Jeśli chcesz szybko usunąć elementy tablicy, usuń je od końca (pod array[array.length - 1]), np. przy użyciu Array.pop(). Jeśli chcesz usunąć wszystkie elementy za jednym razem, po prostu ustaw array.length = 0. Jeśli potrzebujesz szybkiej selekcji FIFO/"kolejki", rozważ zainspirowanie się buforami pierścieni: użyj "kursora" dla następnego elementu, który chcesz odczytać/odesłać, i zmniejszaj tylko tablicę, gdy jest duża porcja elementów, które mają zostać uwolnione. Z grubsza:

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

---

marginesie: To nie ma znaczenia, ale dla przypomnienia, naciskać 70.000 elementów w macierzy, pętla powinna zaczynać się od 0: for (var i = 0; i < 70000; i++) {...}. Jak napisano, tylko pchasz 69 999 elementów.

Nota boczna 2: Zaokrąglanie podwójnego do liczby całkowitej za pomocą "parseInt" jest dość powolne, ponieważ najpierw formatuje podwójne jako ciąg, a następnie odczytuje ten ciąg z powrotem jako liczbę całkowitą. Szybszym sposobem byłoby Math.floor(Math.random() * 10000)). (Dla celów tego testu możesz również po prostu nacisnąć i.)

Answer 2

Ciekawe, zrobiłem coś takiego

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

wewnątrz 2nd pętli. (To jest bolesne do obliczenia, ale pomoże zdiagnozować problem)

Nie doznałem straty wydajności. Ale myślę, że odkryłem, że "tylko" 2000 rzeczy do zrobienia jest trudne dla węzła. Pierwszy - my różnica: [pętli max num urządzenie 3 Wyniki poziomami odniesienia]

70k: [MS] ~ 26k ~ 25.7k ~ 26k 72k: [MS] ~ 25.6k, 27k, 25.7k

OK, jak widziałem rejestrację, widziałem, że ostatnie rekordy 10k są obliczane jak natychmiast. Myślę, że splice usuwa 1 przedmiot z przodu, a następnie - jeden po drugim przesuwa indeks tablicy 1 "na początek", zmieńmy nasz test na 10 tablic, każdy z rekordami 10k, aby zobaczyć, czy będzie znacznie lepiej. Zrobię to w najbardziej leniwy sposób:

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

A, tak ... I nie odpowiedział dlaczego exacly komputer mają taką stratę wydajności między 70k i 72k rekordów - Wierzę, że coś jest zależny maszyna .. Prawdopodobnie brak pamięci RAM, ale nie zrozum mnie źle - nie wiem.

Rozwiązałem, jak to poprawić. Czas wykonania 100k (-10) przy 10 tablicach wynosił około 73-74 ms. Myślę, że możesz zapisać go w tablicy 2d i zmodyfikować logikę, aby obliczyć długość i resztę, jak chcesz.

Dzięki za uwagę.