如何使用 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²)，慢得多！

参考

• 10个javascript难点
• 10个最佳es6特性

关于fundebug

fundebug专注于javascript、微信小程序、微信小游戏、支付宝小程序、react native、node.js和java线上应用实时bug监控。 自从2016年双十一正式上线，fundebug累计处理了10亿+错误事件，付费客户有阳光保险、核桃编程、荔枝fm、掌门1对1、微脉、青团社等众多品牌企业。欢迎大家免费试用！