摘要&＃xff1a; 高效使用Set&＃xff01;
- 作者&＃xff1a;前端小智
- 原文&＃xff1a;如何使用 Set 来提高代码的性能
Fundebug经授权转载&＃xff0c;版权归原作者所有。
为了保证的可读性&＃xff0c;本文采用意译而非直译。
我确信有很多开发人员坚持使用基本的全局对象&＃xff1a;数字&＃xff0c;字符串&＃xff0c;对象&＃xff0c;数组和布尔值。对于许多用例&＃xff0c;这些都是需要的。 但是如果想让你的代码尽可能快速和可扩展&＃xff0c;那么这些基本类型并不总是足够好。
在本文中&＃xff0c;我们将讨论JS 中Set对象如何让代码更快— 特别扩展性方便。 Array 和Set工作方式存在大量的交叉。但是使用Set会比Array在代码运行速度更有优势。
Set 有何不同
最根本的区别是数组是一个索引集合&＃xff0c;这说明数组中的数据值按索引排序。
const arr &＃61; [A, B, C, D];
console.log(arr.indexOf(A)); // Result: 0
console.log(arr.indexOf(C)); // Result: 2
相比之下&＃xff0c;set是一个键的集合。set不使用索引&＃xff0c;而是使用键对数据排序。set 中的元素按插入顺序是可迭代的&＃xff0c;它不能包含任何重复的数据。换句话说&＃xff0c;set中的每一项都必须是惟一的。
主要的好处是什么
set 相对于数组有几个优势&＃xff0c;特别是在运行时间方面&＃xff1a;
- 查看元素&＃xff1a;使用
indexOf()或includes()检查数组中的项是否存在是比较慢的。 - 删除元素:在
Set中&＃xff0c;可以根据每项的的 value 来删除该项。在数组中&＃xff0c;等价的方法是使用基于元素的索引的splice()。与前一点一样&＃xff0c;依赖于索引的速度很慢。 - 保存 NaN&＃xff1a;不能使用
indexOf()或 includes() 来查找值 NaN&＃xff0c;而 Set 可以保存此值。 - 删除重复项:
Set对象只存储惟一的值,如果不想有重复项存在&＃xff0c;相对于数组的一个显著优势&＃xff0c;因为数组需要额外的代码来处理重复。
时间复杂度&＃xff1f;
数组用来搜索元素的方法时间复杂度为0(N)。换句话说&＃xff0c;运行时间的增长速度与数据大小的增长速度相同。
相比之下&＃xff0c;Set用于搜索、删除和插入元素的方法的时间复杂度都只有O(1)&＃xff0c;这意味着数据的大小实际上与这些方法的运行时间无关。
Set 究竟有多快&＃xff1f;
虽然运行时间可能会有很大差异&＃xff0c;具体取决于所使用的系统&＃xff0c;所提供数据的大小以及其他变量&＃xff0c;但我希望我的测试结果能够让你真实地了解Set的速度。 我将分享三个简单的测试和我得到的结果。
准备测试
在运行任何测试之前&＃xff0c;创建一个数组和一个 Set&＃xff0c;每个数组和 Set 都有100万个元素。为了简单起见&＃xff0c;我从0开始&＃xff0c;一直数到999999。
let arr &＃61; [], set &＃61; new Set(), n &＃61; 1000000;
for (let i &＃61; 0; i }
测试1&＃xff1a;查找元素
我们搜索数字123123
let result;
console.time(&＃39;Array&＃39;);
result &＃61; arr.indexOf(123123) !&＃61;&＃61; -1;
console.timeEnd(&＃39;Array&＃39;);
console.time(&＃39;Set&＃39;);
result &＃61; set.has(123123);
console.timeEnd(&＃39;Set&＃39;);
- Array: 0.173ms
- Set: 0.023ms
Set 速度快了7.54倍
代码部署后可能存在的BUG没法实时知道&＃xff0c;事后为了解决这些BUG&＃xff0c;花了大量的时间进行log 调试&＃xff0c;这边顺便给大家推荐一个好用的BUG监控工具 Fundebug。
测试2&＃xff1a;添加元素
console.time(&＃39;Array&＃39;);
arr.push(n);
console.timeEnd(&＃39;Array&＃39;);
console.time(&＃39;Set&＃39;);
set.add(n);
console.timeEnd(&＃39;Set&＃39;);
- Array: 0.018ms
- Set: 0.003ms
Set 速度快了6.73倍
测试3&＃xff1a;删除元素
最后&＃xff0c;删除一个元素&＃xff0c;由于数组没有内置方法&＃xff0c;首先先创建一个辅助函数&＃xff1a;
const deleteFromArr &＃61; (arr, item) &＃61;> {let index &＃61; arr.indexOf(item);return index !&＃61;&＃61; -1 && arr.splice(index, 1);
};
这是测试的代码&＃xff1a;
console.time(&＃39;Array&＃39;);
deleteFromArr(arr, n);
console.timeEnd(&＃39;Array&＃39;);
console.time(&＃39;Set&＃39;);
set.delete(n);
console.timeEnd(&＃39;Set&＃39;);
- Array: 1.122ms
- Set: 0.015ms
Set 速度快了74.13倍
总的来说&＃xff0c;我们可以看到&＃xff0c;使用Set 极大地改善运行时间。再来看看一些Set有用的实际例子。
案例1:从数组中删除重复的值
如果想快速地从数组中删除重复的值&＃xff0c;可以将其转换为一个 Set。这是迄今为止过滤惟一值最简洁的方法:
const duplicateCollection &＃61; [&＃39;A&＃39;, &＃39;B&＃39;, &＃39;B&＃39;, &＃39;C&＃39;, &＃39;D&＃39;, &＃39;B&＃39;, &＃39;C&＃39;];
// 将数组转换为 Set
let uniqueCollection &＃61; new Set(duplicateCollection);
console.log(uniqueCollection) // Result: Set(4) {"A", "B", "C", "D"}
// 值保存在数组中
let uniqueCollection &＃61; [...new Set(duplicateCollection)];
console.log(uniqueCollection) // Result: ["A", "B", "C", "D"]
案例2&＃xff1a;谷歌面试问题
问题&＃xff1a;
给定一个整数无序数组和变量 sum&＃xff0c;如果存在数组中任意两项和使等于 sum 的值&＃xff0c;则返回true。否则,返回false。例如&＃xff0c;数组[3,5,1,4]和 sum &＃61; 9&＃xff0c;函数应该返回true&＃xff0c;因为4 &＃43; 5 &＃61; 9。
解答
解决这个问题的一个很好的方法是遍历数组&＃xff0c;创建 Set保存相对差值。
当我们遇到3时&＃xff0c;我们可以把6加到Set中, 因为我们知道我们需要找到9的和。然后&＃xff0c;每当我们接触到数组中的新值时&＃xff0c;我们可以检查它是否在 Set 中。当遇到5时&＃xff0c;在 Set 加上4。最后&＃xff0c;当我们最终遇到4时&＃xff0c;可以在Set中找到它&＃xff0c;就返回true。
const findSum &＃61; (arr, val) &＃61;> {let searchValues &＃61; new Set();searchValues.add(val - arr[0]);for (let i &＃61; 1, length &＃61; arr.length; i };
简洁的版本&＃xff1a;
const findSum &＃61; (arr, sum) &＃61;>arr.some((set &＃61;> n &＃61;> set.has(n) || !set.add(sum - n))(new Set));
因为Set.prototype.has()的时间复杂度仅为O(1)&＃xff0c;所以使用 Set 来代替数组&＃xff0c;最终使整个解决方案的线性运行时为O(N)。
如果使用 Array.prototype.indexOf()或Array.prototype.includes()&＃xff0c;它们的时间复杂度都为 O(N)&＃xff0c;则总运行时间将为O(N²)&＃xff0c;慢得多&＃xff01;
参考
- 10个Javascript难点
- 10个最佳ES6特性
关于Fundebug
Fundebug专注于Javascript、微信小程序、微信小游戏、支付宝小程序、React Native、Node.js和Java线上应用实时BUG监控。 自从2016年双十一正式上线&＃xff0c;Fundebug累计处理了10亿&＃43;错误事件&＃xff0c;付费客户有阳光保险、核桃编程、荔枝FM、掌门1对1、微脉、青团社等众多品牌企业。欢迎大家免费试用&＃xff01;
京公网安备 11010802041100号