如何使用 Set 来提高JS代码的性能

你的名字 2021-12-12 14:35 217阅读 0赞

**摘要：** 高效使用Set！

*  作者：前端小智
 *  原文：[如何使用 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][Fundebug 1]。**

#### 测试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, 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_JavaScript]
 *  [10个最佳ES6特性][10_ES6]

### 关于Fundebug ###

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

[Set]: https://github.com/qq449245884/xiaozhi/issues/72
[Fundebug]: https://www.fundebug.com/
[Fundebug 1]: https://www.fundebug.com/?utm_source=xiaozhi
[10_JavaScript]: https://blog.fundebug.com/2017/07/17/10-javascript-difficulties/
[10_ES6]: https://blog.fundebug.com/2017/08/21/10-best-es6-feature/