JavaScript - удалять эффективность алгоритмов дубликатов

Question

Я много читал об этой теме, и я видел много разных алгоритмов. Я наткнулся на другое решение, которое Im с трудом понимает его эффективность по сравнению с другими алгоритмами, поскольку использует простой временный объект для хранения существующих элементов массива. Является ли это верным решением по сравнению с методом «старой школы» с использованием сложного метода сортировки и сравнения?

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

Вы получите лучшие результаты, используя наиболее подходящую структуру данных. В JIT/интерпретируемом языке, таком как js, преимущества использования встроенной функциональности огромны.

Это набор, который вы должны использовать в первую очередь: таким образом, вы даже не должны ничего делать, чтобы удалить дубликаты, они будут просто проигнорированы при добавлении.
Я просто сделал простой тест, а выступления в шесть-десять раз (!!) быстрее с набором.

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" 

Ниже приведены кривые п = 0 до 50.000 как для алгоритма.
Мы видим, что действительно, hashmap ведет себя как 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); 

(не забывайте, что Set является ECMAScript 6, так что используйте в теге Js, type = "application/javascript; version = 1.7"

Если вас беспокоит совместимость: http://kangax.github.io/compat-table/es6/#Set
Все «современные» платформы в порядке: Ch, FF, IE11, OS8
Все остальные не в порядке.)