阅读 1938

「前端长列表」开源库解析及最佳实践

前言

长列表一般也叫虚拟列表,是一种大数据量下只渲染可见节点避免页面卡顿的优化方案

长列表也有时间分片的做法,比较少用,感兴趣的可以看 高性能渲染十万条数据(时间分片)

前端比较有名的有两个项目:

  • react-window
  • vue-virtual-scroller

以及 Ant Design 4 的 virtual-list

本文将对这些开源库进行剖析,分析实现原理,并进行各个指标的评估,最终实现一个高可用的长列表组件

主要评估以下几点:

  1. 渲染:回流, 渲染策略等
  2. 计算:起止项和偏移位置的计算,总高度的计算
  3. 功能:自适应高度,其他
  4. 健壮:是否存在鼠标与滚动条不同步的 bug(计算时总高度增加了,则滚动条会相对鼠标向上)

然后说下看源码的策略,主要看这几点:

  1. dom 结构
  2. 查找起始位置
  3. 计算偏移距离
  4. 计算总高度

长列表入门

如果还不清楚长列表是什么,可以先看下这篇文章「前端进阶」高性能渲染十万条数据(虚拟列表)

一张图快速入门

下面我们来看看其他开源库都怎么做的

vue-virtual-scroller

项目地址

功能: 支持自适应高度,横向滚动,图片自适应高度

渲染

dom 结构如下

<!-- position: relative;overflow-y: auto; -->
<div class="vue-recycle-scroller">
  <div class="vue-recycle-scroller__item-wrapper" :style="{ 'minHeight': totalSize + 'px' }">
    <div
        v-for="view of pool"
        :key="view.nr.id"
        :style="{ transform: `translateY(${view.position}px)` }"
        class="vue-recycle-scroller__item-view"
      >
        <slot
          :item="view.item"
          :index="view.nr.index"
          :active="view.nr.used"
        />
      </div>
  </div>
</div>
复制代码

一个相对定位的列表,由 min-height 撑开 wrapper 以产生滚动条

每个列表项进行平移(translateY),这个偏移值为该项在列表中的高度累加值

还有一些 -9999px 的不可见元素,这些其实是缓存池列表项,这个在 节点回收复用 一节会讲到

列表项数据结构:

listItem = {
  // 数据项内容
  item:Object,
  // 非响应式数据
  nr:{
    id,// 唯一标识
    index,// 数据项中的索引
    used: Boolean,// 是否已用来显示在可视区域
    key,// 数据项中的key
    type,// 在对应类型的缓冲池中存取
  }
  // translateY 值
  position: Number,
}
复制代码

不会产生回流(非自适应高度的情况)

浏览器渲染速度快:进行滚动时产生变化的列表项会尽可能的使用缓存池元素并修改 translateY ,其他没有变动的列表项在dom结构中的位置不变

计算

有三种场景

① 使用默认高度

最简单的情况,需要设置 itemSize

起始项索引可以通过 ~~(scrollTop / itemSize) 得到

列表总高度 = itemSize * itemCount

② 定义高度字段

itemSize 设为 null,通过数据项中的 height 字段定义每个列表项的高度

由于所有列表项高度是确定的,一开始会计算每一项的高度和偏移值

O(n) 时间复杂度

同时确定了列表总高度,固定为 最后一项的偏移值+高度

当进行滚动时,由于每一项的偏移位置是确定的,则查找起始项索引可以采用二分法

O(logn) 时间复杂度

③ 自适应高度

需要配置数据项最小高度,并根据这个值初始化每个数据项的高度和偏移值 -- sizes

O(n) 时间复杂度

列表总高度为 最后一项的偏移值+高度

sizes 计算

for (let i = 0, l = items.length; i < l; i++) {
  current = items[i][field] || minItemSize
  accumulator += current
  sizes[i] = { accumulator, size: current }
}
复制代码

进行滚动,通过二分 sizes 得到起始项索引,结束项索引为起始项索引加上 可视高度/最小列高

O(logn) 时间复杂度

之后进行节点渲染,渲染完毕时获取实际高度,并重新计算 sizes 以及列表总高度

O(n) 时间复杂度

总体来说,性能较差,有优化的空间

【卖点】节点回收与复用

连续滚动(continuous): 前后两次查找的数据范围有重叠,比如第一次为 1~10 第二次为 5~14 或者相反
已使用的列表项(views): 记录已使用项的 Map ,key 为列表项的 key
pool: 页面中所有渲染的列表项,包括未使用的
类型-缓存池 Map (unusedViews): 记录类型和缓存池的 Map
缓存池(unusedPool): 某种类型的缓存池,其中的列表项在页面中偏移位置为 -9999px 
复制代码

举个连续滚动的例子:

  1. 一开始查到 1~10 放入 views 中,进行滚动,查到 5~14
  2. 将 1~4 放入对应类型的 unusedPool 中,设置未使用,并从 views 中删除
  3. 将原来的 5~10项 设置为 已使用
  4. 查到 11 时,看 unusedPool 中有没有和 11 同类型的,有的话 pop 出来复用,替换下内容和偏移位置,没有的话新建一个 view,会放入 pool 中

对应的,非连续滚动定义为 快速滚动,初始化一个空的 map -- unusedIndex, 作用是记录同类型的 unusedPool 需要从哪个索引开始取值。

如果 unusedPool 存在元素,拿来复用;如果同类型 pool 被用光了,addView

感觉此处 v++ 的处理有点问题,没有深究

和安卓的列表滚动类似,按类型进行回收,新找到的列表项会复用缓存中同类型的,可以减少 layout 时间

类似的还有 weex 的 recycle-list

健壮

由于进度条高度会变化,因此存在鼠标与滚动条不同步的 bug

总结

功能丰富,自适应高度方面的处理性能不行(尝试考虑pr),项目结构较差不易维护

不建议使用

react-window

提供四种组件:

  • FixedSizeList
  • FixedSizeGrid
  • VariableSizeList
  • VariableSizeGrid

不支持自适应高度

grid 不分析了, FixedSizeList 就是最简单的固定高度的情景,做法都一样,我们直接分析 VariableSizeList

先吐个槽, react-window 为了复用,代码封装了一层又一层,render 还是用的 createElement ... 看源码的时候实在难受,而且还是用 flow 写的,编辑器各种报错

不知道什么原因,依赖安装的时候一直失败,本地没有启动起来,这次是直接看的源码

渲染

<div style="{{position: 'relative', height: `${height}px`, overflow: 'auto'}}">
  <div style="{{height: `${totalSize}px`, width: '100%'}}">
    <div style="position: absolute; left: 0px; top: 38px; height: 30px; width: 100%;">
      Row 1
    </div>
    <div style="position: absolute; left: 0px; top: 68px; height: 65px; width: 100%;">
      Row 2
    </div>
    ....
    <div style="position: absolute; left: 0px; top: 133px; height: 70px; width: 100%;">
      Row 3
    </div>
  </div>
</div>
复制代码

依然是用一个 totalSize 高度的容器去产生进度条,每个列表项通过绝对定位进行偏移

这里其实用 transform: translateY 效果一样的,当然渲染上的性能差异我就不知道了

计算

和这篇文章的实现一致 -- 再谈前端虚拟列表的实现

貌似对指数搜索有误解?

设 lastMeasureItem 为已测量的最远元素,

lastMeasureItem.offset 为该元素的偏移值

lastMeasureItem.index 为该元素的索引

列表总高度 = lastMeasureItem.offset + 未测量元素 * 默认高度

初次滚动,从第0项开始测量并缓存已滚动过的元素的偏移和索引,更新 lastMeasureItem

O(n) 时间复杂度

当滚动偏移值小于 lastMeasureItem.offset 时,表示起始项在 0~lastMeasureItem.index 范围之间,由于该范围所有列表项偏移值都计算过了,此时采用二分即可快速得到起始项索引

O(logn)

当滚动偏移值小于 lastMeasureItem.offset 时,则以 lastMeasureItem.index 开始测量并缓存已滚动过的元素的偏移和索引,更新 lastMeasureItem

O(n) 时间复杂度

Watch 观察 lastMeasureItem.index ,若改变,则列表总高度跟着变

在线 Demo

本方案有两个缺点:

  • 拓展差,做不了自适应高度
  • 前面的滚动较耗时间,把没用到的也计算进去了

健壮

由于进度条高度会变化,因此存在鼠标与滚动条不同步的 bug

总结

不支持自适应高度,性能不行,不是 react 长列表的首选方案

如果有用到 Grid 的话可以用

virtual-list

项目地址

目前分析综合评分最高的一个

支持自适应高度,支持动画效果,支持滚动位置复原

渲染

  <!-- 用户可见的容器高度可能只有 300px -->
  <div
    class="container"
    style="width: 200px; height: 300px;"
    @scroll.passive="handleScroll"
  >
    <!-- 总的列表 div ,用于撑起列表的高度 -->
    <div
      class="total-list"
      :style="{
        height: `${itemHeight * data.length}px`,
      }"
    >
      <div
        class="visible-list"
        :style="{
        transform: `translateY(${topHeight}px)`,
      }"
      >
        <div
          v-for="item in visibleList"
          :key="item.id"
          class="visible-list-item"
          :style="{
          height: `${itemHeight}px`,
        }"
        >{{ item.value }}</div>
      </div>
    </div>

    <!-- 此处只需渲染可见列表即可,无需渲染全部数据 -->

  </div>
复制代码

和上面的方案不一样,这里是创建了一个 total-list 的容器,直接对这个容器进行 translateY 偏移

计算

总高度始终固定,等于 列表项个数(itemCount) * 列表项最小高度(itemHeight)

处理逻辑如下:

  1. 滚动,确定定位项和起止项
  2. 渲染起止列表项
  3. 列表项渲染完毕,计算并调整起始项偏移位置
  4. 进行重渲染

注意:此处的渲染表示对 dom 进行操作,还未到浏览器实际渲染阶段

核心思想是任意高度的列表项都占据相同的滚动条范围

① 确定定位项和起止项

定位项与滚动条位置对应,可以理解为滚动条水平方向指向的那个列表项。

当滚动条为0时,指向第0项,此时定位项为第0项

当滚动条处于最大值时,指向最后一项,此时定位项为最后一项

const itemCount = this.data.length
const scrollTopMax = scrollHeight - clientHeight
/** 进度条滚动百分比 */
const scrollPtg = scrollTop / scrollTopMax
/** 确定定位项 */
const itemIndex = Math.floor(scrollPtg * itemCount);
/** 可见列表项个数 = 可见容器高度 / 每个列表项高度 ,记得向上取整 */
const visibleCount = Math.ceil(this.$el.clientHeight / this.itemHeight)
/** 确定起始项和结束项 */
const startIndex = Math.max(0, itemIndex - Math.ceil(scrollPtg * visibleCount))
const endIndex = Math.min(itemCount - 1, itemIndex + Math.ceil((1 - scrollPtg) * visibleCount))
复制代码

② 渲染列表项

渲染 startIndex ~ endIndex 的列表项

③ 调整 offset

在列表项渲染完毕后,触发 update 回调

获取并统计 startIndex ~ itemIndex 列表项的实际总高度 s2iHeight

计算起始项偏移高度 startItemTop ,如下:

const startItemTop = 定位项绝对高度(itemAbsoluteTop) - 起始项至定位项的高度(s2iHeight)
const itemAbsoluteTop = scrollTop + 定位项相对视口高度(itemRelativeTop)
const itemRelativeTop = 滚动过的视口高度(scrollPtg * clientHeight) - 定位项偏移高度(itemOffsetPtg * itemHeight)
复制代码

如图所示:

健壮

由于总高度固定,不存在鼠标和滚动条不同步的问题

总结

性能优异,通过几个数学公式即可确定起止位置(还有优化的空间)

若需要自适应高度,则需要进行2次render,否则第一次render即可计算偏移位置

目前唯一一种不产生鼠标和滚动条不同步问题的方案

拓展性强,毕竟后面是 Ant Design 4 的核心组件之一

react 长列表首选方案

vue 可以尝试造个轮子

其他处理方案

本节为其他一些长列表的处理方案,主要表现在起始项查找和更新列表高度方面的不同

这里提到的几种方案,都会出现 鼠标和滚动条不同步 的问题

① 顺序查找,差量更新总高度

性能较差的一种方案

定义数组 itemHeightRecord 记录列表项实际高度,可以是自适应计算出来的高度,也可以是定义高度方法计算得到的高度

一开始,列表总高度 = 列表项个数 * 默认高度

查找起始项,由于没有记录偏移值,只能采用顺序叠加的方式判断, itemHeightRecord 中有值的取值,没值的取默认高度

时间复杂度 O(n)

渲染列表项,并将取得的高度与默认值之间的差更新到 列表总高度 上,并对 itemHeightRecord 进行赋值

缺点:查找起始项的效率太低

② 二分查找,顺序更新偏移值

思路来源于 「前端进阶」高性能渲染十万条数据(虚拟列表) ,并对更新偏移值进行优化

需要配置数据项最小高度,并根据这个值初始化每个数据项的高度和偏移值 -- sizes

列表总高度 = sizes[length-1].offset + sizes[length-1].height

查找起始项,根据 sizes 进行二分

时间复杂度 O(logn)

渲染列表项(假设有m项),并将取得的高度替换 sizes 中的 height,并将 height 与默认值之间的差更新到其后每一项的 offset

时间复杂度 O(n)

与 vue-virtual-scroller 自适应高度的处理方式类似,只不过我们仅需要从起始项开始处理

在线 Demo

引用自 「前端进阶」高性能渲染十万条数据(虚拟列表) ,更新偏移值那边的时间复杂度为 O(n*m)

缺点:更新 sizes 较为耗时

③ 树状数组优化更新偏移值

自己想出来的一种解决方案,能够达到查询和更新都是 O(logn) 时间复杂度

在未看 virtual-list 的方案前,我一度以为这是最好的方案

效率上两者差不多,不过本方案会有 鼠标和滚动条不同步 的问题

我们先建立数据模型,列表项的高度列表为长度为 len 的正数数组 nums ,有两种操作:

  1. 更新数组中某项的值
  2. 找到一个最小的 n,前 n 项总和大于等于目标值 target , 1<= n <= len

很明显这是一个树状数组模板题,两个操作都是 O(logn) 的时间复杂度,模板可以参考我写的 BinaryIndexedTree

关于树状数组原理可以参考文章 -- 树状数组(Binary Indexed Trees)

提供了几个方法

function findGe(target) {} //找到最小的一个n,其前n项和大于等于 target
function update (i, val) {} // 第 i 项增加差值val, 1<=i<=len
function prefixSum (n = this.tree.length - 1) {} //计算前 n 项的和 , 1<=n<=len
复制代码

查找起始项可以采用 findGe, 查找起始项偏移位置以及列表总高度可以用 prefixSum, 更新偏移值采用 update

测试效果:10W 条数据滚动时处理的计算时间在 1ms 左右

感兴趣的可以看我的开源库 virtual-list-demo

回流优化

可视区域的列表高度,一般不变,没必要每次都通过 $el.clientHeight 获取(会造成回流),在 resize 时再改变

如果是自适应高度,那本操作可有可无

综合实现

本来打算单独写一节的,最后决定采用 virtual-list 的设计方式

列表项采用 Render Props 的形式,用 cloneElement 生成实际列表项。

无论是自适应高度还是固定高度,都是通过参数配置,对外仅提供一个组件

展望

浏览器兼容性测试

个人方案仅测试了 chrome ,还没测试过其他浏览器,看开源库的时候有看到其做了一些兼容处理

比如火狐滚动白屏问题,Safari scrollTop 可能为负的问题,移动端卡顿的问题

篇幅有限,这些不在本文的研究范围,建议就是生产环境尽量用开源库

图片自适应高度

若列表项高度是依赖于图片高度的,由于图片加载较慢,在初次渲染结束时(update生命周期中)并获取不到真实列表高度,需要等待图片加载完毕后计算

具体做法就是采用 ResizeObserver API ,不过这个兼容性有点问题,

vue-virtual-scroller 中其实有用到了,感兴趣的可以参考一下

响应键盘事件

通过方向键切换列表项,需要拦截键盘默认事件,并赋值 scrollTop

这个更多的是基于长列表的 Select,Tree 中会用到,到时候用到再说


原文地址,感兴趣的给个 star ~

参考

  1. virtual-list-demo
  2. 「前端进阶」高性能渲染十万条数据(虚拟列表)
  3. 再谈前端虚拟列表的实现