set

2019-10-22 本文已影响0人田成力

我坚信很多开发者依旧与这些基本的全局对象打交道：numbers，strings，objects，arrays 和 booleans。

大部分业务场景，以上这些已经够用了。但是，如果你想让你的代码运行的尽可能快、可扩展性尽可能的好，那么这些基本类型并不够优秀。

在这篇文章，我们将要讨论如何利用 JS 的 Set 对象让你的代码运行的更快——尤其是在它所处理的数据量大的时候。Array 和 Set 在处理数据时，两则有太多的相似。但是使用 Set 所带来的运行时优势，是 Array 无法完成的。

Set 有何不同？
根本的区别就是 Array 是索引集合（index collection）。这意味着，数据的值是以索引（index）排序的。

const arr = [A, B, C, D];

console.log(arr.indexOf(A));// Result: 0

console.log(arr.indexOf(C));// Result: 2

而 Set 则是键集合（keyed collection）。相比使用索引，Set 使用键来组织它的数据。一个 Set 中所有项都是按插入顺序可迭代的，它不会有重复值。换句话说，Set 中的每一项都是独一无二的。

最主要的收益是什么？
Set 相比 Array 有些优势，特别是考虑到需要更快的运行时间：

查找项: 使用 indexOf() 或 includes() 去检查一个项是否在数组中很慢。
删除项: 在 Set 中，你可以使用值去删除一项。而在 Array 中，相同的功能需要使用项的索引使用 splice()方法。使用索引是很慢的
插入项: 在 Set 中新增一项比 Array 使用 push() 或者 unshift() 等方法新增一项要快的多。
排序NaN值: 你无法使用 Array 的 indexOf() 或者 includes() 去定位 NaN 值，但是 Set 可以并且能够存储这个值
去重: Set 对象只存储独一无二的值，如果你想避免储存重复值，这是比 Array 更好的选择，因为使用 Array，你需要使用额外的代码去处理这种情况。
Note: 更多 Set 内置方法，请查阅 MDN Web Docs
什么是时间复杂度？
使用 Array 去查找是一个为 O(N) 的线性时间复杂度。换句话说，随着数据量的提高，运行时间随着增加。

相比而言，使用 Set 去查找，不管是删除还是插入的时间复杂度都仅仅是 O(1)——这意味着，运行时间不随着数量的提高而增加。

那么 Set 究竟有多快呢？
虽然运行时间受使用的操作系统、数据的大小和其它的一些变量的影响，我希望我的测试结果能让你对 Set 的速度有个直观的感受。

准备测试
在开始运行之前，我们简单的将 Array 和 Set 填充 1000000 个值（0~999999）


let arr = [], set = new Set(), n = 1000000;

for(let i = 0; i < n; i++){

    arr.push(i);

    set.add(i);

}

测试1：查找
查找值 123123:


let result;

console.time('Array');

result = arr.indexOf(123123) !== -1;

console.timeEnd('Array');

console.time('Set');

rusult = set.has(123123);

console.timeEnd('Set');
Array: 0.173ms
Set: 0.023ms
Set 快了 7.54 倍

测试2: 新增
新增一个值，变量为 n：

console.time('Array');

arr.push(n);

console.timeEnd('Array');

console.time('Set');

set.add(n);

console.timeEnd('Set');
Array: 0.018ms
Set: 0.003ms
Set 快了 6.73 倍

测试3：删除
最后，我们删除一项（就删除我们刚新增的）。因为 Array 没有原生删除方法，我们写一个 helper 来完成这个功能：



const deleteFromArr = (arr, item) = > {

    let index = arr.indexOf(item);

    return index !== -1 && arr.splice(index, 1);

}
进行我们的测试：


console.time('Array');

deleteFromArr(arr, n);

console.timeEnd('Array');

console.time('Set');

set.delete(n);

console.timeEnd('Set');
Array: 1.122ms
Set: 0.015ms
这一次，Set 快了 74.13 倍！

总体来说，我们可以看到在运行时间上，Set 相比 Array 优势巨大。现在我们来看看 Set 的一些实践：

用例1: 数组去重
如果你想要在 Array 中快速去重，你可以将它转为 Set。这是目前为止最简洁的方法。



const duplicateCollection = ['A','B','B','C',''D','B','E'];

//如果你想把 Array 转成 Set

let uniqueCollection = new Set(duplicateCollection);

console.log(uniqueCollection) //Set(4) {"A","B","C","D"};

//如果你想让你的值仍是`Array`

let uniqueCollection = [...new Set(duplicateCollection)];

console.log(uniqueCollection)//["A","B","C","D"]

用例2：谷歌面试题
在我的另一篇文章中，我为谷歌面试官的一个问题讨论了一些解决方案。面试是使用 C++，但是如果是 JS，Set 会是最终解决方案的关键点。

如果你想要更深入了解这些解决方案，我推荐阅读原文，但是这里，我简单的介绍一下解决方案。

问题是这样的

给一个未排序的整数数组和一个值 sum，如果数组中任意两项相加等于 sum，则返回 true，否则返回 false。

如给定数组 [3, 5, 1, 4] 和值 9，我们的方法应该返回 true，因为 4 + 5 = 9。

答

这里解释思路，不翻译了，看代码就能懂。


const findSum = (arr, val) => {

    let searchValues = new Set();

    searchValues.add(val - arr[0]);

    for(let i = 1;length = arr.length; i < length; i++){

        let searchVal = val - arr[i];

        if(searchValues.has(arr[i])){

            return true;

        }else{

            searchValues.add(searchVal);

        }

    }

    return false;

}

更简洁的版本：

    const findSum = (arr, sum) => ((set => n => set.has(n) || !set.add(sum - n))(new set));

因为 Set.prototype.has() 时间复杂度只有 O(1), 使用 Set 存储数据，结合 Array 的循环，我们最终的时间复杂度为 O(N)。

如果我们依赖 Array.prototype.indexOf() 或 Array.prototype.includes()，而两者的时间复杂度都是 O(N), 我们最终的时间复杂度会达到 O(N²)。太慢了!

set

猜你喜欢

热点阅读