array vs singly linked list

ArrayVsSingleLinkedList.js

// 10,000,000개의 객체를 만든다.
// 각 객체는 "value" 값과 "update" 함수를 프로퍼티로 갖는다. 
// "update" 함수는 "value"의 값을 1 증가시켜준다.

myarr = []

for(i=0; i<10000000; ++i) 
  myarr.push( { "update": function() { this.value = this.value + 1 }, "value": 1 } )

// 노드에서 시간 측정을 위한 함수(마이크로초 단위)
function clock(start) {
  if ( !start ) return process.hrtime();
  var end = process.hrtime(start);
  return Math.round((end[0]*1000000) + (end[1]/1000));
}

// 천만개의 배열을 update()하면서 결과 보기
function benchmark() { 
  //var start = performance.now()   // 브라우저에서는 performance 사용 가능
  var start = clock();
  for(i=0; i<myarr.length; ++i) 
    myarr[i].update()
  var duration = clock(start)
  //var end = performance.now() 
  //var duration = end - start
  console.log(duration) 
}


for(kk=0; kk<10; ++kk) benchmark()

/* 내 노트북에서 나온 결과임 
438998
244993
251144
276350
269407
265339
265891
267002
254118
250467
*/

// 단일 연결 리스트를 사용해 구현해본 것

// 루트 노드 정의
var root = { "update": function() { this.value = this.value + 1 }, "value": 1, "next": undefined }

// 루트부터 next를 계속 연결
var curPtr = root;
for(i=1; i<10000000; ++i) {
   var newNode = { "update": function() { this.value = this.value + 1 }, "value": 1, "next": undefined }
   curPtr.next = newNode
   curPtr = newNode
}

// 연결리스트를 방문하면서 시간 재기
function benchmark2() { 
  //var start = performance.now()
  var start = clock();
  for(curPtr = root; curPtr; curPtr = curPtr.next ) { 
    curPtr.update()
  }	
  var duration = clock(start)
  //var end = performance.now() 
  //var duration = end - start
  console.log(duration) 
}

for(kk=0; kk<10; ++kk) benchmark2()
/* 내 노트북에서 나온 결과임
297472
241504
238520
240210
266176
248957
249183
252813
260980
244051
*/