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

  • 首页
  • 荣誉资质
  • 新闻中心
  • 你的位置:焦作市恒辉精密制造有限公司 > 新闻中心 > 浅谈虚拟列表实现与原理分析

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

    发布日期:2022-08-07 04:24    点击次数:74

     

    前言

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

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

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

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

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

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

    以下, 郑州市红火阑珊文化传播有限公司正文开始。

    原理分析

    虚拟长列表模型

    长列表分为几个区域:

    VirtualList:完整的列表区域 VisibleRange:视窗区域 RenderRange(PreScanRange + VisibleRange + PostScanRange):实际渲染区域 LoadedRange:已加载区域 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 数组提供给后续渲染。

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

    基本算法逻辑如下:

     

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

    使用方法如下:

     

    渲染效果如下:

     

    抛掷动画(自由滚动)

    实现基本逻辑:

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

    实现代码如下:

     

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

    然后 _flushTotalSize 和 _scrollTo 方法如下:

     

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

     

     

    横向与纵向

    如何让虚拟列表同时支持横向和纵向滚动呢?其实我们知道,二者的逻辑是十分相似的。比如说横向滚动,改变的是 scrollLeft,纵向滚动改变的是 scrollTop,还有分别对应的 width、height 等等。因此,我们只需要声明如下变量:

     

    然后在组件中取得滚动方向配置,用该配置在运行时动态读取对应的参数即可。

    小结

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

    作者:苏里

    链接:https://juejin.im/post/6877507011769008135

    来源:掘金

     



    TOP