JavaScript - 중복 알고리즘 효율성 제거

Question

이 주제에 대해 많이 읽었으며 많은 알고리즘을 보았습니다. 다른 알고리즘에 비하면 효율을 이해하는 데 어려움을 겪는 다른 솔루션을 우연히 발견했습니다. 간단한 임시 객체를 사용하여 배열의 기존 요소를 보유하고 있기 때문입니다. 정교한 정렬 방법과 비교를 사용하는 "구식"방법과 비교할 때 유효한 해결책입니까?

function removeDup(arr){ 
     var element, 
       existObj= {}, 
       finalArr = []; 

     for(var i=0;i<arr.length;i++){ 
      element = arr[i]; 
      if(!existObj[element]){ 
       finalArr.push(element); 
       existObj[element] = true; 
      } 
     } 
     return finalArr; 
    } 
    //console.log(removeDup([2,2,2,2,4534,5,7,3])); 
    console.log(removeDup(["mike","john","alex","mike","john"])); 

친구는 임시 개체가 실제로 구현 된 방법을 알고 있기 때문에 효율성을 명확히 결정할 수 없다고 말했습니다.

Answer 1

가장 적합한 데이터 구조를 사용하면 최고의 실적을 거둘 수 있습니다. js와 같은 JIT/해석 언어에서 네이티브 기능을 사용하면 얻을 수있는 이점은 엄청납니다.

첫 번째 장소에서 사용해야하는 집합입니다. 이렇게하면 dups를 제거하기 위해 아무 것도하지 않아도됩니다. 추가 할 때 무시됩니다.
방금 ​​간단한 테스트를했고 공연은 세트로 약 6 ~ 10 배 (!!) 빠릅니다.

http://jsbin.com/jofofeyixaco/1/edit?js,console

결과 예 : 여기

"overhead is : 0.015700000221841037" 
"Built unic numbers with a lookup object in : 6.237600000167731" 
"Built unic numbers with a Set in : 0.7921500000520609" 

두 알고리즘 50.000 행 N = 0에 대한 곡선이다.
실제로 해시 맵은 O (1)과 매우 비슷하게 동작하지만 n이 높아지면 퍼짐이 더 높아지는 것을 볼 수 있습니다.
세트가 거의 완벽하게 선형입니다.

jsbin를 (! 환자 수) 그리기 : http://jsbin.com/jofofeyixaco/2/

코드 :

// noprotect 
// build a test set 
var numbers = []; 
var cnt = 10000; 
for (var i=0; i<cnt; i++) numbers.push(Math.floor(Math.random*1000)); 

// build unic values using lookup object 
function buildWithObject() { 
    var existing= {}; 
    var unicNumbers = []; 
    for (var i=0; i<cnt; i++) { 
    var num = numbers[i]; 
    if (!existing[num]) { 
     unicNumbers.push(num); 
     existing[num]=true; 
    } 
    } 
} 

// build unic values using a Set 
function buildWithSet() { 
    var unicNumbersSet = new Set(); 
    for (var i=0; i<cnt; i++) { 
     var num = numbers[i]; 
     unicNumbersSet.add(num); 
    } 
} 

function iterate() { 
    for (var i=0; i<cnt; i++) { 
     var num = numbers[i]; 
    }  
} 

// warming up functions 
for (var i=0; i<30; i++) { buildWithObject(); buildWithSet() ; iterate(); } 

// -------- Measures -------------------- 
var measureRepeat = 20; 
var m; 

var s,e; 
// ---------------------------- 
m=measureRepeat; 
s=window.performance.now(); 
while (m--) iterate(); 
e=window.performance.now(); 

console.log('overhead is : ' + (e-s)/measureRepeat); 

// ---------------------------- 
m=measureRepeat; 
s=window.performance.now(); 
while (m--) buildWithObject(); 
e=window.performance.now(); 

console.log('Built unic numbers with a lookup object in : ' + (e-s)/measureRepeat); 

// ---------------------------- 
m=measureRepeat; 
s=window.performance.now(); 
while (m--) buildWithSet(); 
e=window.performance.now(); 
console.log('Built unic numbers with a Set in : ' + (e-s)/measureRepeat); 

(잊지 마세요 설정은 JS 태그에, ECMA 스크립트 (6), 이렇게 사용하는 것입니다, type = "application/javascript; version = 1.7"

호환성이 염려되는 경우 : http://kangax.github.io/compat-table/es6/#Set
모든 '현대적인'플랫폼 확인 : Ch, FF, IE11, OS8
다른 모든 것은 괜찮습니다.)