专栏首页程序员成长指北如何使用 Set 来提高代码的性能

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

原文:https://medium.com/@bretcameron/how-to-make-your-code-faster-using-javascript-sets-b432457a4a7 译者:小智

我确信有很多开发人员坚持使用基本的全局对象:数字,字符串,对象,数组和布尔值。对于许多用例,这些都是需要的。但是如果想让你的代码尽可能快速和可扩展,那么这些基本类型并不总是足够好。

在本文中,我们将讨论JS 中 Set对象如何让代码更快— 特别扩展性方便。 ArraySet工作方式存在大量的交叉。但是使用 Set会比 Array在代码运行速度更有优势。

Set 有何不同

最根本的区别是数组是一个索引集合,这说明数组中的数据值按索引排序。

const arr = [A, B, C, D];console.log(arr.indexOf(A)); // Result: 0console.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

测试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'];// 将数组转换为 Setlet 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²),慢得多!

本文分享自微信公众号 - 程序员成长指北(coder_growth),作者:小智

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • MySql基础架构(sql查询语句在MySql内部具体是怎么执行的?)

    对于一个做后台不久的我,起初做项目只是实现了功能,所谓的增删改查,和基本查询索引的建立。直到有一个面试官问我一个问题,一条sql查询语句在mysql数据库中具体...

    coder_koala
  • 如何答一道惊艳面试官的数组去重问题?

    思想: 双重 for 循环是比较笨拙的方法,它实现的原理很简单:先定义一个包含原始数组第一个元素的数组,然后遍历原始数组,将原始数组中的每个元素与新数组中的每个...

    coder_koala
  • 辩证的眼光搞懂 JWT 这个知识点

    JWT 由三部分组成:Header,Payload,Signature 三个部分组成,并且最后由.拼接而成。

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

    我确信有很多开发人员坚持使用基本的全局对象:数字,字符串,对象,数组和布尔值。对于许多用例,这些都是需要的。 但是如果想让你的代码尽可能快速和可扩展,那么这些基...

    前端小智@大迁世界
  • 如何使用 Set 来提高JS代码的性能

    我确信有很多开发人员坚持使用基本的全局对象:数字,字符串,对象,数组和布尔值。对于许多用例,这些都是需要的。 但是如果想让你的代码尽可能快速和可扩展,那么这些基...

    Fundebug
  • ES6新的数据结构Set

    Set一种新的数据结构,在之前数据的集合分为数组(Array)和对象(Object),ES6出现新的Set数据结构,和Map,这里先介绍一下Set.

    十月梦想
  • ES6 中的 Set

    ES6 新增了几种集合类型,本文主要介绍Set以及其使用。Set对象是值的集合,你可以按照插入的顺序迭代它的元素。 Set中的元素只会出现一次,即 Set 中的...

    腾讯IVWEB团队
  • ES6 Set

    本文作者:IMWeb kurtshen 原文出处:IMWeb社区 未经同意,禁止转载 ES6 Set ES6 新增了几种集合类型,本文主要介绍Set以...

    IMWeb前端团队
  • ES6 Set

    其中iterable是一个可迭代对象,其中的所有元素都会被加入到 Set 中。null被视作 undefined。也可以不传入[iterable],通过其add...

    IMWeb前端团队
  • es6 -- set 数据结构

    ES6 提供了新的数据结构 Set。它类似于数组,但是成员的值都是唯一的,没有重复的值。

    小蔚

扫码关注云+社区

领取腾讯云代金券