如何利用 JS 的 Set 对象让你的代码运行的更快

作者:日期:2019-04-20 15:05:59 点击:47 set的用法,set优势

我坚信很多开发者依旧与这些基础的全局对象打交道: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²)••。太慢了!

盼望本文对你有所赞助

上一篇: 弯道超车,5分钟快速懂得结构器函数与原型对象之间的关系

下一篇: 站内信最佳通信方案:WebSocket

澳洲快乐十分玩法 彩世界彩票注册平台 玖玖网彩票官网 北京pk10开奖网站 幸运农场规则 红韵彩票网 75秒赛车开奖结果 北京pk10开奖网站 网易红彩彩票平台 幸运农场规则