js数组去重

数组去重是我们经常在面试或者网上刷题时遇到的问题，一般的想法是创建一个新的空数组，然后从原数组中一个个拿出元素，验证在新数组中是否已有相同元素，如果没有就置入；虽然我们知道这种方式是最low的。下面我们来看看这种最low的方案和优化方案的区别。

首先我们先创建一个有十万个拥有0-99整数数值和字符串元素的数组：

let i = 0
let arr = []
while(i++ < 100000) {
    let one = ~~(Math.random()*100)
    Math.random() > 0.5 && (one += '')
    arr.push(one)
}

// 共有200种元素，创建100000个必然有重复
// [ '29', 60, 95, '45', '84', '6', 45, '50', '0', 91, '63', '75', 38, 58, 99, ... ]

首先是最简单的但是性能很差的方案：

function uniqueArray(arr) {
    let result = []
    arr.forEach(item => {
        !~result.indexOf(item) && result.push(item)
    })
  return result
}

这种方式明显很耗性能，每个元素比对的时候都要进行一次循环。我们用console.time打印看看这个函数处理的时间

console.time('uniqueArray')
let uniqueArr = uniqueArray(arr)
console.timeEnd('uniqueArray')

// 共花费时间
// uniqueArray: 51.007ms

上面的方案，原数组有10万个元素，在处理过程中就进行了10万次循环比对，造成了非常大的性能开销。
于是我们设想一种优化的方案，使整个处理过程只需要进行一次循环：

function uniqueArray2(arr) {
    let obj = {}, obj2 = {}, result = []

    arr.forEach(item => {
        if (item in obj) {
            if (item !== obj[item] && !(item in obj2)) {
                obj2[item] = item
                result.push(item)
            }
        } else {
            result.push(item)
            obj[item] = item
        }

    })

    return result
}

看看优化方案的处理时间

console.time('uniqueArray2')
let uniqueArr2 = uniqueArray2(arr)
console.timeEnd('uniqueArray2')

// 共花费时间
// uniqueArray2: 8.142ms

可以看出性能优化了不少。
通过进行多次不同元素个数处理对比，两种方案的性能开销大概8倍左右差距。
如果你有更优化的解法，欢迎赐教。