JS数组性能小则|你以为的快不是真的快

场景

这是在写一个特殊的 React 业务组件(虚拟树形列表)时想到的一个问题,当时我内部实现了一个继承数组的类(因为不想用 Getter 的方式去访问这个类存储的数据,所以选择直接继承数组,这样也可以在内部直接用 this 去访问数组本身以及方法)并且要实现一个内部过滤数据并且可以重置过滤的功能。

我第一时间想到的便是,在初始化时给每个数据打上标记,过滤时把数据取出,重置时把数据放回并且按标记来重新排序。

class DataArr extends Array {     constructor(data, key){         super()         this.dataMap = {}         this.dataKey = key         this.dataWhichBeFiltered = []     }     initData () {         this.forEach((item, index) => {             this.initItem(item, {                 index             })         })     }     initItem (item, opt) {         this.dataMap[item[this.dataKey]] = item         item._index = opt.index     }     filter () {}     resetFilter () {} } // usage const data = new DataArr(arr) data.filter(item => item.a === 1) data.resetFilter() 复制代码

然后问题就来了,在这种情况下 filter 我们不能直接用 Array.prototype.filter,因为这个方法只会返回新数组,我们没办法写 this = this.filter(item => item.a === 1) 这样的代码。

过程

写一个数组自己 filter 的方法,我一开始就想到数组倒序遍历然后在当中用 splice 一个一个把要摘的数据提出来,就像下面这样

filter (fn) {     for (let i = this.length - 1; i >= 0 ;i--) {         const item = this[i]         if (!!fn(item)) {             const delItem = this.splice(i, 1)[0]             this.dataWhichBeFiltered.push(delItem)         }     } } 复制代码

这样执行的结果确实可行,但却有着不低的隐患,至今很多人以为 splicepoppush 这些方法一样,是很常规的 O(1) 操作,实际上 splice 的性能是非常差的。我问我的前端同事小伙伴,他们也觉得没有多大的问题,而我有时候在逛掘金的时候也碰见过 “倒序遍历 splice 真的很爽” 这样的评论。

除了上面的方式,我还想了一个看起来慢,但实际上比循环 splice 快将近 100 倍的方案,就是循环标记需要过滤的内容,而后将要过滤的内容排序到末尾再将他们切除。

filter (fn) {     let index = 0     for (let i = this.length - 1; i >= 0 ;i--) {         const item = this[i]         if (!!fn(item)) {             item.willBeFiltered = 1             index ++         }         else item.willBeFiltered = 0     }     this.sort((a, b) => b.willBeFiltered - a.willBeFiltered)     this.dataWhichBeFiltered = this.splice(i) } 复制代码

在浏览器 console 中测试的结果图

直接倒序遍历 splice

先排序后 splice,1w 的数据量不算多,但是占用 1s 以上已经有严重的卡顿感了。

原由

splice 的缓慢在于数组的插入移除操作不像链表,只需要切除要移除的节点,再把 prev 节点和 next 节点连接就完成了。

数组中的元素存在一个连续的内存块中并且只能用索引访问。

也就是说数组的存放是有先后顺序的,用数组下标去访问每一个数组元素,当我们“简单”地在数组当中移除掉或者插入一个或者多个数组元素,那么需要对应地改变这个元素之后地所有元素的下标,这样的行为带来了不少的损耗。

原数组 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

移除当中的元素 【5】 arr.splice(4,1) [1, 2, 3, 4, 6, 7, 8, 9, 10]

数组的变化(移除前-移除后) 0 => 1          0 => 1 1 => 2          1 => 2 2 => 3          2 => 3 3 => 4          3 => 4 4 => 5    =>    4 => 6 5 => 6    =>    5 => 7 6 => 7    =>    6 => 8 7 => 8    =>    7 => 9 8 => 9    =>    8 => 10 9 => 10          复制代码

这个变化带来的影响与数组长度以及需要调整的下标数量有关。除了 splice 还有一个具有同样性能损耗的,就是同样具有插入功能的 unshift 方法了。

tips

除了上面的问题,我还发现一个不经意的一个 es6 带来的变化。上面说到,除了实现 filter 功能还要实现一个 resetFilter,这个方法说来也简单,就是把 dataWhichBeFiltered 的数据重新加回数组,然后我们在按原 index 排序就阔以了。

    this.dataWhichBeFiltered.forEach(data => this.push(data))     this.sort((a, b) => a._index - b._index) 复制代码

这时候同样的我也不能写 this = this.concat(this.dataWhichBeFiltered),只能循环一个一个地 push 回原数组。

但我当时随手试了一下 push 方法,原来 push 是可以传多个参数的!

arr.push(element1, ..., elementN)

因为在以前 es5 的环境下很少会用 push 传多个参数去新增多项数组项(因为你不能动态的往 push 方法里传参),但是现在由于 es6 新加入的拓展运算符,我们可以直接就是 this.push(...this.beFilteredData)。效果无论是从哪方面看都非常让我满意。而在以前的代码里还躺着 const result = arr1.concat(arr2) 这样的过去式代码。

总结

总结一下,在前端浏览器环境中,没四千万不要在数组循环中使用 splice 或者 unshift 方法,在数据量超过一定数量时,这样操作会耗费大量性能。因为数组的元素是存在一块连续的内存块中,只能通过索引访问,当发生删除或者插入操作时,会引起当中一系列连锁变化,导致性能变差。

我想起某位知名大佬写的快排,当中循环的一个 splice 直接把"快"排变成了"慢"排。导致被各路大神疯狂吐槽,这也是很久之前的事情了。现在人家都是人生赢家了,而我还在办公室里加班QAQ。

上一篇:js关于splice方法,被自己埋雷


下一篇:splice方法