场景
这是在写一个特殊的 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) } } } 复制代码
这样执行的结果确实可行,但却有着不低的隐患,至今很多人以为 splice
和 pop
、push
这些方法一样,是很常规的 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。