Gahing's blog
gahing
2019-12-10
目录

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

# 前言

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

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

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

  • react-window
  • vue-virtual-scroller

以及 Ant Design 4 的 virtual-list (opens new window)

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

主要评估以下几点：

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

然后说下看源码的策略，主要看这几点：

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

# 长列表入门

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

一张图快速入门

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

# vue-virtual-scroller

项目地址 (opens new window)

功能： 支持自适应高度，横向滚动，图片自适应高度

# 渲染

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>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

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

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

列表项数据结构：

listItem = {
  // 数据项内容
  item:Object,
  // 非响应式数据
  nr:{
    id,// 唯一标识
    index,// 数据项中的索引
    used: Boolean,// 是否已用来显示在可视区域
    key,// 数据项中的key
    type,// 在对应类型的缓冲池中存取
  }
  // translateY 值
  position: Number,
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

不会产生回流（非自适应高度的情况）

浏览器渲染速度快：进行滚动时产生变化的列表项会尽可能的使用缓存池元素并修改 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 }
}
1
2
3
4
5

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

O(logn) 时间复杂度

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

O(n) 时间复杂度

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

# 【卖点】节点回收与复用

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

举个连续滚动的例子：

  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 (opens new window)

# 健壮

由于进度条高度会变化，因此存在鼠标与滚动条不同步的 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>
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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

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

# 计算

和这篇文章的实现一致 -- 再谈前端虚拟列表的实现 (opens new window)

貌似对指数搜索有误解？

设 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 (opens new window)

本方案有两个缺点：

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

# 健壮

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

# 总结

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

如果有用到 Grid 的话可以用

# virtual-list

项目地址 (opens new window)

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

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

# 渲染

  <!-- 用户可见的容器高度可能只有 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>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

# 计算

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

处理逻辑如下：

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

注意：此处的渲染表示对 dom 进行操作，仍处于宏任务，还未到浏览器实际渲染(UI Render)阶段

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

# ① 确定定位项和起止项

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

当滚动条为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))
1
2
3
4
5
6
7
8
9
10
11

# ② 渲染列表项

渲染 startIndex ~ endIndex 的列表项

# ③ 调整 offset

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

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

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

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

如图所示：

# 健壮

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

# 总结

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

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

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

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

react 长列表首选方案

vue 可以尝试造个轮子

# 其他处理方案

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

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

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

性能较差的一种方案

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

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

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

时间复杂度 O(n)

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

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

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

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

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

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

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

时间复杂度 O(logn)

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

时间复杂度 O(n)

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

在线 Demo (opens new window)

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

缺点：更新 sizes 较为耗时

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

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

在未看 virtual-list (opens new window) 的方案前，我一度以为这是最好的方案

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

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

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

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

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

提供了几个方法

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
1
2
3

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

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

感兴趣的可以看我的开源库 virtual-list-demo (opens new window)

# 回流优化

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

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

# 综合实现

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

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

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

# 展望

# 浏览器兼容性测试

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

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

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

# 图片自适应高度

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

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

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

# 响应键盘事件

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

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

原文地址 (opens new window)，感兴趣的给个 star ~

# 参考

  1. virtual-list-demo (opens new window)
  2. 「前端进阶」高性能渲染十万条数据(虚拟列表) (opens new window)
  3. 再谈前端虚拟列表的实现 (opens new window)
编辑 (opens new window)
#React#最佳实践#长列表#性能
上次更新: 2024/09/01, 23:56:56
为什么不用rAF进行滚动节流
如何解决长列表的滚动白屏问题

← 如何解决长列表的滚动白屏问题→

最近更新
01
浅谈代码质量与量化指标
08-27
02
快速理解 JS 装饰器
08-26
03
Vue 项目中的 data-v-xxx 是怎么生成的
09-19
更多文章>
Theme by Vdoing | Copyright © 2016-2024 Gahing | 闽ICP备19024221号-1