You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
在运行任何测试之前,创建一个数组和一个 Set,每个数组和 Set 都有100万个元素。为了简单起见,我从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');
result = set.has(123123);
console.timeEnd('Set');
为了保证的可读性,本文采用意译而非直译。
我确信有很多开发人员坚持使用基本的全局对象:数字,字符串,对象,数组和布尔值。对于许多用例,这些都是需要的。 但是如果想让你的代码尽可能快速和可扩展,那么这些基本类型并不总是足够好。
在本文中,我们将讨论JS 中
Set
对象如何让代码更快— 特别扩展性方便。Array
和Set
工作方式存在大量的交叉。但是使用Set
会比Array
在代码运行速度更有优势。想阅读更多优质文章请猛戳GitHub博客,一年百来篇优质文章等着你!
Set 有何不同
最根本的区别是数组是一个索引集合,这说明数组中的数据值按索引排序。
相比之下,
set
是一个键的集合。set
不使用索引,而是使用键对数据排序。set
中的元素按插入顺序是可迭代的,它不能包含任何重复的数据。换句话说,set
中的每一项都必须是惟一的。主要的好处是什么
set
相对于数组有几个优势,特别是在运行时间方面:查看元素:使用
indexOf()
或includes()
检查数组中的项是否存在是比较慢的。删除元素:在
Set
中,可以根据每项的的value
来删除该项。在数组中,等价的方法是使用基于元素的索引的splice()
。与前一点一样,依赖于索引的速度很慢。保存 NaN:不能使用
indexOf()
或includes()
来查找值NaN
,而Set
可以保存此值。删除重复项:
Set
对象只存储惟一的值,如果不想有重复项存在,相对于数组的一个显著优势,因为数组需要额外的代码来处理重复。时间复杂度?
数组用来搜索元素的方法时间复杂度为
0(N)
。换句话说,运行时间的增长速度与数据大小的增长速度相同。相比之下,
Set
用于搜索、删除和插入元素的方法的时间复杂度都只有O(1)
,这意味着数据的大小实际上与这些方法的运行时间无关。Set 究竟有多快?
虽然运行时间可能会有很大差异,具体取决于所使用的系统,所提供数据的大小以及其他变量,但我希望我的测试结果能够让你真实地了解
Set
的速度。 我将分享三个简单的测试和我得到的结果。准备测试
在运行任何测试之前,创建一个数组和一个 Set,每个数组和 Set 都有100万个元素。为了简单起见,我从
0
开始,一直数到999999
。测试1:查找元素
我们搜索数字
123123
Set
速度快了7.54
倍测试2:添加元素
Set
速度快了6.73
倍测试3:删除元素
最后,删除一个元素,由于数组没有内置方法,首先先创建一个辅助函数:
这是测试的代码:
Set
速度快了74.13
倍总的来说,我们可以看到,使用
Set
极大地改善运行时间。再来看看一些Set
有用的实际例子。案例1:从数组中删除重复的值
如果想快速地从数组中删除重复的值,可以将其转换为一个
Set
。这是迄今为止过滤惟一值最简洁的方法:案例2:谷歌面试问题
问题:
给定一个整数无序数组和变量
sum
,如果存在数组中任意两项和使等于sum
的值,则返回true
。否则,返回false
。例如,数组[3,5,1,4]
和sum = 9
,函数应该返回true
,因为4 + 5 = 9
。解答
解决这个问题的一个很好的方法是遍历数组,创建
Set
保存相对差值。当我们遇到
3
时,我们可以把6
加到Set
中, 因为我们知道我们需要找到9
的和。然后,每当我们接触到数组中的新值时,我们可以检查它是否在Set
中。当遇到5
时,在 Set 加上4。最后,当我们最终遇到4
时,可以在Set
中找到它,就返回true
。简洁的版本:
因为
Set.prototype.has()
的时间复杂度仅为O(1)
,所以使用 Set 来代替数组,最终使整个解决方案的线性运行时为O(N)
。如果使用
Array.prototype.indexOf()
或Array.prototype.includes()
,它们的时间复杂度都为 O(N),则总运行时间将为O(N²)
,慢得多!交流
干货系列文章汇总如下,觉得不错点个Star,欢迎 加群 互相学习。
我是小智,公众号「大迁世界」作者,对前端技术保持学习爱好者。我会经常分享自己所学所看的干货,在进阶的路上,共勉!
关注公众号,后台回复福利,即可看到福利,你懂的。
The text was updated successfully, but these errors were encountered: