浅谈虚拟列表实现与原理分析

12,040 阅读7分钟

前言

虚拟列表可以说是一个很常见的需求场景了。

什么是虚拟列表?在我们日常生活中,刷不到底的新闻 Feed 流,无尽图片瀑布流、超级超级长的排行榜等等。对于这种场景,我们不可能一次性加载完所有数据,因为不仅用户手机的视窗大小决定了这种做法很浪费,同时请求如此多的数据,从网络带宽、服务端压力上都很不经济,同时宿主环境从大量数据中渲染如此多的元素,对应用的性能也有不小负担。

因此,对于一般都要从用户体验和应用性能两方面去权衡考虑,从而优化这种场景。那么,常见的解决思路有哪些呢?基本有三种如下:

  • 分页加载。实现简单直接,但是在请求下一页时,可能也会打断用户心流,体验不是最佳。
  • 懒加载。实现难度不大,可以解决首屏的压力,但是长时间加载数据,也同样会产生大量元素节点,从而影响应用性能(因为也没有处理过期节点的销毁问题)。
  • 虚拟列表。实现难度较大,通过计算滚动视窗,每次只渲染部分元素,既减少了首屏压力,长时间加载也不会有更多的性能负担,可以满足上述大部分场景。


因此。虚拟列表作为一种对用户体验和应用性能都有裨益的方案,是现代应用开发中一种流行方案。前端里也有 react-virtualized、react-window 等成熟解决方案。开发一个讲究体验的信息流应用,少不了要应用到虚拟列表。

当然懂得流行虚拟列表库的 API 怎么运用是实践的第一步。但是,只有掌握原理才可以深入优化列表性能,以及针对性做扩展。

以下,正文开始。

原理分析

虚拟长列表模型

长列表分为几个区域:

  1. VirtualList:完整的列表区域
  2. VisibleRange:视窗区域
  3. RenderRange(PreScanRange + VisibleRange + PostScanRange):实际渲染区域
  4. LoadedRange:已加载区域
  5. UnloadRange:未加载区域


如下图:


计算公式如下:

  • RenderRange = PreScanRange + VisibleRange + PostScanRange = stop - start
  • LoadedRange = lastMeasureIndex - 0
  • UnloadRange = size(VirtualList) - lastMeasureIndex


实际滚动过程中需要不断更新 start、stop、lastMeasureIndex,从而得出渲染区域和视窗区域。

位置缓存

缓存的意义,一般在于提高性能。因此对 LoadedRange 中的元素已经得到计算的尺寸、偏移缓存在哈希表中,用以减少重复计算,提高性能。

查找指定元素

基于有序元素偏移列表:

  • 在 LoadedRange 中使用二分查找算法,时间复杂度可降低到 O(lgN);
  • 在 UnloadRange 中使用指数查找算法,时间复杂度同样为 O(lgN),但是可以将 N 值缩小,进一步提高搜索性能。


指数搜索如下:

核心思想:先用指数搜索定位范围 low - high,内嵌二分查找 target。算法实现如下:

滚动偏移计算

VirtualList 总长度计算公式如下:
TotalSize = lastMeasuredSizeAndPosition.offset + lastMeasuredSizeAndPosition.size + (itemCount - lastMeasuredIndex - 1) * estimatedItemSize

基本思路是使用已计算的偏移尺寸,加上未加载的预估尺寸,即为基本等价于整体尺寸。实现一个 SizeAndPositionManager 用以管理以及计算滚动偏移。代码概略如下:


通过 SizeAndPositionManager 的设计,将虚拟列表的偏移计算等相关逻辑抽离在此处,从而解耦和视图界面之间的关联。

不定尺寸的子元素

子元素的尺寸不定的情况下:

  • 静态计算 :提前预知所有元素的尺寸,并通过数组类型的 prop 传入,每个列表项的高度通过索引来获得。配置方式:prop:itemSize=[]number
  • 动态延迟计算:传入获取列表项高度的方法,给这个方法传入 item 和 index ,返回对应列表项的高度。配置方式:prop:itemSize=: number


将上述方式得出的尺寸作为计算依据,若无法获取对应尺寸,则使用预估尺寸(可配置)。

在 C 端项目中必然存在图片加载撑起高度等情况,子项高度大概率不确定。

如何动态估算子项高度?可以使用 estimatedItemSize 类似配置,这样就能依赖预估高度计算列表内容的总高度,并且总高度随着列表项的渲染而渐进调整。这个在列表项是动态高度的场景下很有用,可以初始化内容的总长度以撑开容器元素,使其可在水平/垂直方向滚动。
**
当然如果上述都满足不了需求。也有 react-virtualized 中的 CellMeasurer 作为一种提供尺寸度量的 HOC 组件提供。本质上桥接了组件调用方与虚拟列表组件内部通讯,组件调用方可以在元素尺寸稳定时显示通知组件更新计算。

调用方式如下:

function rowRenderer ({ index, isScrolling, key, parent, style }) {
  const source // This comes from your list data

  return (
    <CellMeasurer
      cache={cache}
      columnIndex={0}
      key={key}
      parent={parent}
      rowIndex={index}
    >
      {({ measure, registerChild }) => (
        <div ref={registerChild} style={style}>
          <img
            // 图片加载成功时调用 measure 回调通知组件内部更新尺寸度量
            onLoad={measure}
            src={source}
          />
        </div>
      )}
    </CellMeasurer>
  );
}

function renderList (props) {
  return (
    <List
      {...props}
      deferredMeasurementCache={cache}
      rowHeight={cache.rowHeight}
      rowRenderer={rowRenderer}
    />
  );
}

上述代码中的 measure 就是通信的一种方式。在图片加载成功后,会通知长列表组件更新计算。从而达到动态尺寸的诉求。

自定义 Header/Footer

使用单独一个 slotManager 对 Header、Footer 进行插槽计算。即为将所有的 Header 和 Footer 当做虚拟列表的子项以外的插槽进行额外处理。

实现一个 SlotManager ,用以进行所有的插槽计算,如下:


插槽队列示例图如下:


附加上插槽的虚拟列表如图:


根据分析 VirtualList 的子节点获取得到插槽队列,然后通知 sizeAndPositionManager:

  • 更新计算所有虚拟子节点的 offset
  • 根据插槽的 start & end 划分 section


插槽的偏移计算公式如下:

  • SlotHeader(n).offset = SlotHeader(n).firstItem.offset - SlotHeader(n).size
  • SlotFooter(n).offset = SlotHeader(n).lastItem.offset + SlotHeader(n).lastItem.size

单列多 Section

遍历 VirutalList 内部的所有子元素,处理有 Section 和 无 Section 两种情况。最终处理为统一格式的 section 数组提供给后续渲染。

这种诉求场景是当我们渲染长列表时,我们可能会存在需要定制化个别元素作为某一段落的头部和尾部。

基本算法逻辑如下:
image.png
上述的算法逻辑本质上就是在遍历所有子元素(this.props.children),根据类型(Section、Header、Footer)进行判断处理,统一处理为 Section 格式,从而交给上文所说的 SlotManager 继续插槽计算。最后才可以进行插槽以及虚拟列表子项的正确渲染。

使用方法如下:
image.png
渲染效果如下:
image.png

抛掷动画(自由滚动)

实现基本逻辑:

  • 若有浏览器原生支持的 ScrollToOptions,则默认使用
  • 降级使用 easeInOutQuad 函数实现平滑动画曲线

实现代码如下:
image.png
比较有趣的是,其中有一个 _flushTotalSize 是为了解决滚动偏移超出实际总尺寸的情况(还记得么,因为 UnloadRange 区域的列表子项都是使用预估的尺寸,所以是有可能存在此情况的)

然后 _flushTotalSize 和 _scrollTo 方法如下:
image.png

当然,如果浏览器不支持 ScrollToOption,我们也可以使用贝塞尔函数曲线定时滚动去模拟平滑效果,实现优雅降级。不过肉眼看上去,还是远不如上者平滑。scrollTo 代码如下:

横向与纵向

如何让虚拟列表同时支持横向和纵向滚动呢?其实我们知道,二者的逻辑是十分相似的。比如说横向滚动,改变的是 scrollLeft,纵向滚动改变的是 scrollTop,还有分别对应的 width、height 等等。因此,我们只需要声明如下变量:
image.png
然后在组件中取得滚动方向配置,用该配置在运行时动态读取对应的参数即可。

小结

完整虚拟列表实现以及 API 文档,请戳:github.com/sulirc/reac…

以上。感谢阅读~😎