我们是否应该使用 Set 来提高代码的性能

前言

为什么要做这个对比呢？因为昨天看到了这篇文章《如何使用 Set 来提高代码的性能》，文章中说到的好多东西我并不认同，原作者一味的推崇Set比数组要快，但是在我认知中似乎没有别的数据结构在存取方面能比线性存储的数组更快。而原文下面的一些测试只用一组数据对比，这让我感觉原作者根本就没有认真对比。所以萌生了自己测试一把的想法。

本来题目打算取成《驳：<如何使用 Set 来提高代码的性能>》的?，测试完发现并没有什么好驳的，就不给前端娱乐圈添加新闻了。

废话不多说，下面放上测试数据

为了能够清楚的看到内存的消耗，测试在浏览器和Node中分别跑一次，以Node中的内存消耗为参考。数据量为1e7

const MB_SIZE = 1024 * 1024;

function formatMemory (size) {
  return size < MB_SIZE ? `${(size/1024).toFixed(3)}KB` : `${(size/MB_SIZE).toFixed(3)}MB`
}
function getMemory() {
  let memory = process.memoryUsage()
  console.log('------------------------------------')
  console.log('总占用:', formatMemory(memory.rss))
  console.log('堆内存:', formatMemory(memory.heapTotal))
  console.log('堆内存（使用中）:', formatMemory(memory.heapUsed))
  console.log('V8占用:', formatMemory(memory.external))
  console.log('------------------------------------')
}

module.exports = getMemory
复制代码

创建&添加元素对比

Array

const COUNT = 1e7
console.time('new_arr')
let arr = []
console.timeEnd('new_arr')

getMemory()

// 创建时间
console.time('push_arr')
for(let i = 0; i < COUNT; i++) {
  arr.push(i)
}
console.timeEnd('push_arr')

// 赋值时间
console.time('push_arr2')
for(let i = 0; i < COUNT; i++) {
  arr[i] = i + 1
}
console.timeEnd('push_arr2')

// 赋值时间
console.time('push_arr3')
for(let i = 0; i < COUNT; i++) {
  arr[i] = i - 1
}
console.timeEnd('push_arr3')

//  单循环时间
console.time('for_time')
for(let i = 0; i < COUNT; i++) {
  // arr[i] = i
}
console.timeEnd('for_time')
getMemory()
复制代码

测试结果为：

new_arr: 0.156ms
------------------------------------
总占用: 20.820MB
堆内存: 9.234MB
堆内存（使用中）: 4.060MB
V8占用: 85.453KB
------------------------------------
push_arr: 221.450ms
push_arr2: 10.103ms
push_arr3: 9.332ms
for_time: 6.687ms
------------------------------------
总占用: 362.148MB
堆内存: 350.246MB
堆内存（使用中）: 344.085MB
V8占用: 8.477KB
------------------------------------
复制代码

可以看到由于js中的Array是动态创建的所以第一次push创建数组的时候相对与后面的直接存取时间相差了20倍左右，并且直接存取的大部分时间还是循环所耗费的。可见动态创建申请内存非常的耗费时间，内存申请到后的存取就非常符合O(1)的时间了，下面看一下Set的表现。

Set

const COUNT = 1e7

console.time('new Set')
let set = new Set()
console.timeEnd('new Set')

getMemory()

console.time('set_add')
for(let i = 0; i < COUNT; i++) {
  set.add(i)
}
console.timeEnd('set_add')

getMemory()
复制代码

测试结果为：

new Set: 0.169ms
------------------------------------
总占用: 20.828MB
堆内存: 9.234MB
堆内存（使用中）: 4.057MB
V8占用: 85.453KB
------------------------------------
set_add: 2282.407ms
------------------------------------
总占用: 662.043MB
堆内存: 650.227MB
堆内存（使用中）: 644.690MB
V8占用: 85.453KB
------------------------------------
复制代码

可以看到同样的数量Set创建速度比Array要慢了近10倍，内存占用也多出了近2倍。我们都知道Set底层有红黑树和HashSet两种实现方式，都是以空间换时间。虽然没有看过V8的具体实现，但是由于JS中Set是无序的，结合后面测试set.has()是O(1)的时间复杂度，可以猜测V8中的Set是以Hash的形式实现的，有Hash必然涉及到动态扩张Hash或者链式Hash，空间自然会占用的多。

查找元素

首先我们通过下面这段代码随机生成10000个元素来进行查找的测试

const fs = require('fs')
function random () {
  return ~~(Math.random() * 1e7)
}

let arr = []
for(let i = 0; i < 1e3; i++) {
  arr.push(random())
}

fs.writeFileSync('./data.json', JSON.stringify(arr))
复制代码

Array

console.time('indexOf_time')
for(let i = data.length; i >=0 ; i--) {
  arr.indexOf(data[i])
}
console.timeEnd('indexOf_time')


console.time('includes_time')
for(let i = data.length; i >=0 ; i--) {
  arr.includes(data[i])
}
console.timeEnd('includes_time')
复制代码

测试结果：

indexOf_time: 52451.386ms
includes_time: 52599.605ms
复制代码

Set

console.time('set_has_time')
for(let i = data.length; i >=0 ; i--) {
  set.has(data[i])
}
console.timeEnd('set_has_time')
复制代码

测试结果为：

set_has_time: 3.402ms
复制代码

可以看到对比非常夸张数组查询的速度基本比Set慢了15000倍！，远超原文的7.54倍。这是为什么呢？经过前面的分析我们知道Set底层又Hash实现，查询的复杂度基本为O(1)，查询时间并不会随着数据的增大而增大，而数组的查询为线性的O(n)，由于我们本次测试的数据量又达到了1e7的数量，所以查询的速度就相差了非常多了。

删除元素

删除必然依赖查询，从查询的结果上来看我们已经可以预见删除测试的结果了，由于Array作为一个线性的数据结构是不存在删除操作的，一般来说都是将某个位置置空来表示删除的，如果非要使用splice(index, 1)来进行删除，那么相当与将index后面所有的元素都移动了一次，相当于又是一次O(n)的操作，可以遇见性能一定好不了。为了节省时间这次我们将删除的数据调整为1000个

创建删除辅助函数：

function deleteFromArr (arr, item) {
  let index = arr.indexOf(item);
  return index !== -1 && arr.splice(index, 1);
}
复制代码

Array

function deleteFromArr (arr, item) {
  let index = arr.indexOf(item);
  return index !== -1 && arr.splice(index, 1);
}

console.time('includes_time')
for(let i = data.length; i >=0 ; i--) {
  deleteFromArr(arr, data[i])
}
console.timeEnd('includes_time')
复制代码

测试结果为:

deleteFromArr_time: 8245.150ms
复制代码

Set

console.time('set_delete_time')
for(let i = data.length; i >=0 ; i--) {
  set.delete(data[i])
}
console.timeEnd('set_delete_time')
复制代码

测试结果为:

set_delete_time: 0.574ms
复制代码

显然结果与我们预测的一样，同样Set的性能远超Array

结论

以上，并不是说性能不重要，而是要在合适的场景去考虑合适的性能优化，在客户端考虑一下如何减少重排重绘要比考虑使用Array还是Set能减少更多的开销，在服务端合理的设计可能会比考虑这个带来更大的优化。

最后，测试的所有代码都在这里github.com/xluos/Compa…