node.js splice가 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 

그러나 때 내가

는 내가 배열에 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를 버전은 다음과 같습니다

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

---

사이드 노트 : 그것은 여기에 문제가되지 않지만, 기록을 위해, 루프는 0에서 시작한다 당신의 배열에 70,000 요소를 밀어 : for (var i = 0; i < 70000; i++) {...}. 서면으로, 당신은 69,999 요소를 추진하고 있습니다.

사이드 노트 2 : "parseInt"를 통해 정수로 double을 반올림하는 것은 처음에는 double을 문자열로 서식 설정하고 다시 그 문자열을 정수로 읽어 들이기 때문에 매우 느립니다. 더 빠른 방법은 Math.floor(Math.random() * 10000))입니다. 이 테스트의 목적 상 i을 누르기 만하면됩니다.

Answer 2

재미있는 v6.11.3, 나는 두번째 루프 내부

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

같은 것을했다. (이것은 고통 스럽지만 문제를 진단하는 데 도움이됩니다.)

나는 성능 손실을 겪지 않았습니다. 그러나, 나는 생각하기에, "단지"2000 가지 더 많은 일들이 노드에 대해 그렇게 어려운 이유를 발견했다. 첫째 - 내 차 : [루프 최대 NUM, 단위, 3 개 벤치 마크 결과]

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

로깅을 보았을 때, 나는 마지막 10k 레코드가 즉시와 같이 계산된다는 것을 알았습니다. 나는 splice이 앞에서 1 항목을 제거한 다음 배열 하나의 인덱스를 "처음부터"하나씩 이동한다고 생각합니다. 10k 레코드마다 10 개의 배열로 테스트를 변경하여 훨씬 더 나아질 지 봅니다. 그래 ... 내가 exacly 당신의 PC는 70K와 72K 기록과 같은 성능 손실을 왜 대답하지 않았다

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

그리고 - 나는 뭔가 기계 의존 보라 .. : 나는 가장 게으른 방법으로이 작업을 수행 할 것 아마 RAM이 부족하지만 잘못 이해하지 마라. 나는 모른다.

개선 방법을 해결했습니다. 10 개의 배열 실행 시간에 대한 100k (-10)은 약 73-74ms입니다. 내 생각에, 당신은 2 차원 어레이에 그것을 쓰고 길이와 나머지 것들을 원하는대로 계산하도록 로직을 수정할 수 있습니다.

감사합니다.