JavaScript-消除重复算法的效率

Alex 发表于 Dev

亚历克斯

我已经阅读了很多有关该主题的文章，并且看到了许多不同的算法。我偶然发现了另一个解决方案，与其他算法相比，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"]));

一个朋友告诉我，这里的效率无法明确确定，因为我真的不知道临时对象是如何实现的。

游戏炼金术士

通过使用最合适的数据结构，您将获得最佳性能。在像js这样的JIT /解释语言中，使用本机功能的好处是巨大的。

这是您首先应该使用的Set：这样，您甚至无需执行任何操作即可删除dups，添加后它们将被忽略。
我只是做了一个简单的测试，使用Set的速度快了大约六到十倍（!!）。

http://jsbin.com/jofofeyixaco/1/edit?js，控制台

结果示例：

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

这是两种算法的n = 0至50.000的曲线。
我们看到，确实哈希表的行为很像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);