JavaScript 9种数组去重及性能问题

今天药忘吃喽~ 2022-05-23 23:04 226阅读 0赞

最近在面试的过程中，碰到了如何在 JavaScript 中实现数组去重的功能，当时面试官说不用考虑性能什么的，所以我想到的思路是这样的：

1.  新建一个数组；
2.  每次遇到一个字符，进行判定；
3.  如果在新的数组中没有这个字符，就插入到这个新数组中；
4.  如果有这个字符，开始读取下一个字符；
5.  重复步骤 2 - 4，直到数组遍历完了，最后返回这个新数组。

回来之后，查了查 JavaScript 中几种常见数组去重的方法，这里做个总结，然后并附上我对这几种方法性能的测试结果。

下面的函数是用来创建随机数数组的函数（1-1000）：

function createArr(length) { 
    
        var arr = new Array();
        for(var i = 0; i < length; i++) {
            arr[i] = Math.floor(Math.random() * 1000) + 1;
        }
    
        return arr;
    }

#### 1、for循环（两次嵌套）+ 新数组 ####

--------------------

//chrome: max: 1443, min: 1181, average: 1207.47
    //firefox: max: 238, min: 178, average: 185.7
    function sort1(arr) { 
        var flag = 0;
        var result = new Array();
        for(var i = 0; i < arr.length; i++) {
            flag = 0;
            for(var j = 0; j < arr.length; j++) {
                if(result[j] == arr[i]) {
                    flag = 1;break;
                }
            }
            if(flag == 0)
                result.push(arr[i]);
        }
    
        return result;
    }

这就是我一开始想到的思路，当然性能也是最差的，不过不是很清楚，为何在 chrome 和 firefox 中的执行时间差那么多。

#### 2、for 循环（一次） + indexOf() + 新数组 ####

--------------------

//chrome: max: 87, min: 65, average: 69.75
    //firefox: max: 110, min: 38, average: 41.96
    function sort1(arr) { 
        var result = new Array();
        for(var i = 0; i < arr.length; i++) {
            if(result.indexOf(arr[i]) == -1)
                result.push(arr[i]);
        }
        return result;
    }

将方法1进行一次改进，对新数组判定是否有字符，可以调用 `Array.prototype.indexOf` 这个函数，执行时间缩减了很多。

#### 3、forEach() + indexOf() + 新数组 ####

--------------------

//chrome: max: 139, min: 69, average: 77.38
    //firefox:max: 48, min: 38, average: 41.08
    function sort1(arr) { 
        var result = new Array();
        arr.forEach((item, index, array) => {
            if(result.indexOf(item) == -1)
                result.push(item);
        })
        return result;
    }

这里用 ES5 中的 `forEach()`， 替代一下方法2中的 `for(...) {}`，性能方面火狐上与方法2时间一样，谷歌浏览器执行时间比方法2稍长。

#### 4、filter() + indexOf() ####

--------------------

// chrome: max: 167, min: 130, average: 142.17
    // firefox: max: 144, min: 74, average: 80.98
    function sort1(arr) { 
         return arr.filter((item, index, array) =>  array.indexOf(item) === index);
    }

这里用 ES5 中的 `filter()`， 替代一下方法2中的 `for(...) {}`，性能比方法2、方法3都要长。

#### 5、reduce + includes() + …(展开运算符) ####

--------------------

//chrome: max: 128, min: 99, average: 105.27
    //firefox: max: 58, min: 46, average: 49.04
    function sort1(arr) { 
        return arr.reduce((prev,cur) => prev.indexOf(cur) != -1 ? prev : [...prev,cur],[]);
    }

这里用 ES5 中的 `reduce()` 累加器，来替代上面方法中的循环，并用 ES6 中的 `...(展开运算符)`，来替代 `push()` 的作用。性能方面比方法2、3慢，比方法4快。

#### 6、filter() + new Map() ####

--------------------

//chrome: max: 9, min: 3, average: 4.16
    //firefox: max: 10, min: 4, average: 6.24
    function sort1(arr) { 
        const seen = new Map();
        return arr.filter((item) => !seen.has(item) && seen.set(item, 1));
    }

这里用 ES6 中的 `Map 集合`，来替代前面方法中的新数组，调用 Map.has 替代 indexOf()，Map.set 替代 push()，再结合 ES5 中的 `filter()`。性能方面，比前面的方法都要快。

#### 7、new Set() + Array.from() ####

--------------------

//chrome: max: 7, min: 3, average: 4.24
    //firefox: max: 6, min: 2, average: 3.74
    function sort1(arr) { 
        return Array.from(new Set(arr));
    }

这里使用 ES6 中的 Set 集合，**Set 集合是一种无重复元素的列表**，因此`new Set(arr)`会自动剔除重复元素，`Array.from(...)`，将 Set 集合转换为数组。性能方面，谷歌上与方法6差不多，火狐上比方法6略快。

#### 8、new Set() + …(展开运算符) ####

//chrome: max: 8, min: 3, average: 4.34
    //firefox: max; 6, min: 2, average: 3.9
    function sort1(arr) { 
        return [...(new Set(arr))];
    }

思路与方法7一致，只是将 Set 集合转换为数组的实现方法从 `Array.from(...)` 改成了 `...(展开运算符)`。性能方面与方法7差不多。

#### 9、for循环(一次) + 新对象 ####

//chrome: max: 4, min: 1, average: 1.39
    //firefox: max: 2, min: 0, average: 0.52
    function sort1(arr) { 
        let obj = {};
        for (let i = 0; i < arr.length; i++) {
            if (!obj[arr[i]]) {
                obj[arr[i]] = 1;
            }
        }
        return Object.keys(obj);;
    }

思路是将方法2、方法3等方法中的创建一个新数组，改成创建一个新对象，通过对对象的 key 值进行判定，存在跳过，不存在则将字符以对象的 key 值存储。性能方面，执行时间是所有的方法中最短的，因为**对象的属性是基于Hash表实现，因此对属性进行访问的时间复杂度可以达到O(1)**，而诸如 `indexOf()`都需要遍历所有元素来检查，此方法的时间复杂度是O(n)。

参考文章： [JavaScript数组去重的10种方法][JavaScript_10]

[JavaScript_10]: http://www.cnblogs.com/lewiscutey/p/8269567.html