如何使用 Set 来提高JS代码的性能
摘要: 高效使用Set!
- 作者:前端小智
- 原文:如何使用 Set 来提高代码的性能
Fundebug经授权转载,版权归原作者所有。
为了保证的可读性,本文采用意译而非直译。
我确信有很多开发人员坚持使用基本的全局对象:数字,字符串,对象,数组和布尔值。对于许多用例,这些都是需要的。 但是如果想让你的代码尽可能快速和可扩展,那么这些基本类型并不总是足够好。
在本文中,我们将讨论JS 中Set
对象如何让代码更快— 特别扩展性方便。 Array
和Set
工作方式存在大量的交叉。但是使用Set
会比Array
在代码运行速度更有优势。
Set 有何不同
最根本的区别是数组是一个索引集合,这说明数组中的数据值按索引排序。
const arr = [A, B, C, D];
console.log(arr.indexOf(A)); // Result: 0
console.log(arr.indexOf(C)); // Result: 2
相比之下,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
。
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');
- Array: 0.173ms
- Set: 0.023ms
Set
速度快了7.54
倍
代码部署后可能存在的BUG没法实时知道,事后为了解决这些BUG,花了大量的时间进行log 调试,这边顺便给大家推荐一个好用的BUG监控工具 Fundebug。
测试2:添加元素
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:删除元素
最后,删除一个元素,由于数组没有内置方法,首先先创建一个辅助函数:
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
极大地改善运行时间。再来看看一些Set
有用的实际例子。
案例1:从数组中删除重复的值
如果想快速地从数组中删除重复的值,可以将其转换为一个 Set
。这是迄今为止过滤惟一值最简洁的方法:
const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
// 将数组转换为 Set
let uniqueCollection = new Set(duplicateCollection);
console.log(uniqueCollection) // Result: Set(4) {"A", "B", "C", "D"}
// 值保存在数组中
let uniqueCollection = [...new Set(duplicateCollection)];
console.log(uniqueCollection) // Result: ["A", "B", "C", "D"]
案例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
。
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) =>
arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));
因为Set.prototype.has()
的时间复杂度仅为O(1)
,所以使用 Set 来代替数组,最终使整个解决方案的线性运行时为O(N)
。
如果使用 Array.prototype.indexOf()
或Array.prototype.includes()
,它们的时间复杂度都为 O(N),则总运行时间将为O(N²)
,慢得多!
参考
关于Fundebug
Fundebug专注于JavaScript、微信小程序、微信小游戏、支付宝小程序、React Native、Node.js和Java线上应用实时BUG监控。 自从2016年双十一正式上线,Fundebug累计处理了10亿+错误事件,付费客户有阳光保险、核桃编程、荔枝FM、掌门1对1、微脉、青团社等众多品牌企业。欢迎大家免费试用!
相关文章
- Html Table用JS导出excel格式问题 导出EXCEL后单元格里的000412341234会变成412341234 7-14 会变成 2018-7-14(7月14) 自定义格式 web利用table表格生成excel格式问题 js导出excel增加表头、mso-number-format定义数据格式 数字输出格式转换 mso-number-format:"@"
- js,jq滚动监听,切换等常用JS代码
- JS基础 Set 用于存储任何类型的唯一值
- 【JavaScript】JS中暂停几秒再往下执行!
- node.js应用生成windows service的plugin——winser
- 【JS】js创建Object对象和构造函数的多种方法(综合示例)
- 【Vue/js】Js中执行变量中的命令语句,也就是所谓的宏替换(很实用的例子)
- IE浏览器下返回执行错误的Javascript代码所在的问题(js有用)
- Vue - 实现用 JS 调用自定义组件 / 类似 ElementUI 弹框组件(在 js 文件中通过 this.xxx 方式调用并显示自定义弹框模态框组件)
- JS--Object、 Set、Map
- JS Leetcode 220. 存在重复元素 III 题解分析,暴力解法与桶排序
- JS模式:jq中简单的模式--》采摘自js设计(tomxu_version)
- 《Ember.js实战》——第1章 发力雄心勃勃的Web应用 1.1 Ember.js适用场景
- 基于canvas的原生JS时钟效果
- jquery.params.js,Jquery获取页面参数,js获取页面参数
- 前后端加密解密 【JS加密模块(md5 、 crypto 、 crypto-js、jsencrypt) python RSA加密解密(pycryptodome )模块安装与使用】
- js 给json添加新的字段,或者添加一组数据,在JS数组指定位置删除、插入、替换元素
- vue项目mixin.js的使用及注意详解
- JS 工具函数 方法(其中js的crc32和php的crc32区别)
- [js高手之路]html5 canvas动画教程 - 下雪效果
- arcgis api 3.x for js 入门开发系列七图层控制(附源码下载)
- 第一个Cocos2d-JS游戏
- 【cocos2d-js官方文档】五、Cocos2d-JS v3.0的新Action API
- js-原生Js汉语拼音首字母匹配城市名
- js实现无缝滚动
- js 中 Map/Set 集合
- Node.js Events模块