標籤：

再談前端虛擬列表的實現

04-03

書接上文，在之前的 聊聊前端開發中的長列表 中，筆者對「可視區域渲染」的列表進行了介紹，並寫了一個簡化的例子來展現如何實現。這種列表一般叫做 Virtual List，在本文中會使用「虛擬列表」來指代。在本文中，筆者會把上篇文章中的簡化例子一步步強化成一個相對通用、性能優異的虛擬列表組件，旨在講清楚虛擬列表的實現思路。閱讀本文不需要閱讀上一篇文章，但代碼是使用 Vue.js 來實現的，所以你需要有 Vue.js 的使用經驗。另外，提供了各個步驟的 JSFiddle，如果有不懂的地方，建議通過修改 JSFiddle 在線運行調試。

實現思路

在講解下面的內容之前，先對虛擬列表做一個簡單的定義。

因為 DOM 元素的創建和渲染需要的時間成本很高，在大數據的情況下，完整渲染列表所需要的時間不可接收。其中一個解決思路就是在任何情況下只對「可見區域」進行渲染，可以達到極高的初次渲染性能。

虛擬列表指的就是「可視區域渲染」的列表，重要的基本就是兩個概念：

  • 可滾動區域：假設有 1000 條數據，每個列表項的高度是 30，那麼可滾動的區域的高度就是 1000 * 30。當用戶改變列表的滾動條的當前滾動值的時候，會造成可見區域的內容的變更。
  • 可見區域：比如列表的高度是 300，右側有縱向滾動條可以滾動，那麼視覺可見的區域就是可見區域。

實現虛擬列表就是處理滾動條滾動後的可見區域的變更，其中具體步驟如下：

  1. 計算當前可見區域起始數據的 startIndex
  2. 計算當前可見區域結束數據的 endIndex
  3. 計算當前可見區域的數據，並渲染到頁面中
  4. 計算 startIndex 對應的數據在整個列表中的偏移位置 startOffset，並設置到列表上

建議參考下圖理解一下上面的步驟：

最簡單的例子

這個章節會講述如何把上面步驟變成代碼，讓這個邏輯在瀏覽器里真正的運行起來。

為了讓這個例子足夠簡單，做了一個設定：每個列表項的高度都是 30px。在這個約定下，核心 JavaScript 代碼不超過 10 行，但是可以完整的實現可見區域的渲染和更新。

我們首先要考慮的是虛擬列表的 HTML、CSS 如何實現，添加了這麼幾個樣式：

  • 列表元素（.list-view）使用相對定位
  • 使用一個不可見元素（.list-view-phantom）撐起這個列表，讓列表的滾動條出現
  • 列表的可見元素（.list-view-content）使用絕對定位，left、right、top 設置為 0

CSS 代碼如下：

.list-view { height: 400px; overflow: auto; position: relative; border: 1px solid #aaa;}.list-view-phantom { position: absolute; left: 0; top: 0; right: 0; z-index: -1;}.list-view-content { left: 0; right: 0; top: 0; position: absolute;}.list-view-item { padding: 5px; color: #666; line-height: 30px; box-sizing: border-box;}

HTML 代碼如下（先忽略其中的事件、變數綁定）：

<template> <div class="list-view" @scroll="handleScroll"> <div class="list-view-phantom" :style="{ height: contentHeight }"> </div> <div ref="content" class="list-view-content"> <div class="list-view-item" :style="{ height: itemHeight + px }" v-for="item in visibleData"> {{ item.value }} </div> </div> </div></template>

JavaScript 代碼如下：

export default { name: ListView, props: { data: { type: Array, required: true }, itemHeight: { type: Number, default: 30 } }, computed: { contentHeight() { return this.data.length * this.itemHeight + px; } }, mounted() { this.updateVisibleData(); }, data() { return { visibleData: [] }; }, methods: { updateVisibleData(scrollTop) { scrollTop = scrollTop || 0; const visibleCount = Math.ceil(this.$el.clientHeight / this.itemHeight); const start = Math.floor(scrollTop / this.itemHeight); const end = start + visibleCount; this.visibleData = this.data.slice(start, end); this.$refs.content.style.webkitTransform = `translate3d(0, ${ start * this.itemHeight }px, 0)`; }, handleScroll() { const scrollTop = this.$el.scrollTop; this.updateVisibleData(scrollTop); } }}

  1. 渲染可見區域的數據是 Vue.js 完成的，使用的是 visibleData 這個數組中的元素
  2. 其中虛擬列表的更新邏輯是 updateVisibleData 這個方法，筆者對這個方法加了一些注釋：

updateVisibleData(scrollTop) { scrollTop = scrollTop || 0; const visibleCount = Math.ceil(this.$el.clientHeight / this.itemHeight); // 取得可見區域的可見列表項數量 const start = Math.floor(scrollTop / this.itemHeight); // 取得可見區域的起始數據索引 const end = start + visibleCount; // 取得可見區域的結束數據索引 this.visibleData = this.data.slice(start, end); // 計算出可見區域對應的數據，讓 Vue.js 更新 this.$refs.content.style.webkitTransform = `translate3d(0, ${ start * this.itemHeight }px, 0)`; // 把可見區域的 top 設置為起始元素在整個列表中的位置（使用 transform 是為了更好的性能）}

3. 為了讓虛擬列表可以正確的出現滾動條，使用了 Vue.js 的計算屬性 contentHeight 來計算滾動區域的真正高度

這個最簡單的實現可以通過 這裡 在線運行，建議對代碼進行一些修改然後運行，加深對上文的理解。

去掉高度限制

最簡單實現中存在每個元素高度相同的限制，如果打破這個限制，代碼該如何實現？

例子中使用了 itemHeight 屬性來決定列表項的高度，有兩個選擇可以實現列表項的動態高度：

  1. 添加一個數組類型的 prop，每個列表項的高度通過索引來獲得
  2. 添加一個獲取列表項高度的方法，給這個方法傳入 item 和 index ，返回對應列表項的高度

很明顯第二種方案更靈活一點，所以增加了一個 itemSizeGetter 屬性，用來獲取每個列表項的高度。

  1. 增加 itemSizeGetter 屬性，代碼如下：

itemSizeGetter: { type: Function}

2. 因為每一行的高度是不一樣的，所以 contentHeight 的演算法需要進行更新，更新後的代碼如下：

contentHeight() { const { data, itemSizeGetter } = this; let total = 0; for (let i = 0, j = data.length; i < j; i++) { total += itemSizeGetter.call(null, data[i], i); } return total;}

3. 上一個例子中，計算可是區域的起始索引和結束索引只需要使用 itemHeight 進行一些簡單的計算。在這個例子裡面，需要通過 scrollTop 來計算出這個位置的元素索引，所以增加了一個方法叫 findNearestItemIndex，實現代碼如下：

findNearestItemIndex(scrollTop) { const { data, itemSizeGetter } = this; let total = 0; for (let i = 0, j = data.length; i < j; i++) { const size = itemSizeGetter.call(null, data[i], i); total += size; if (total >= scrollTop || i === j -1) { return i; } } return 0;}

4. 同理，某個列表項在列表中的 top 之前也可以通過索引簡單的計算出來，現在需要增加一個方法來計算，實現代碼如下：

getItemSizeAndOffset(index) { const { data, itemSizeGetter } = this; let total = 0; for (let i = 0, j = Math.min(index, data.length - 1); i <= j; i++) { const size = itemSizeGetter.call(null, data[i], i); if (i === j) { return { offset: total, size }; } total += size; } return { offset: 0, size: 0 };}

5. updateVisibleData 方法根據上面的修改做了一個簡單的更新，代碼如下：

updateVisibleData(scrollTop) { scrollTop = scrollTop || 0; const start = this.findNearestItemIndex(scrollTop); const end = this.findNearestItemIndex(scrollTop + this.$el.clientHeight); this.visibleData = this.data.slice(start, Math.min(end + 1, this.data.length)); this.$refs.content.style.webkitTransform = `translate3d(0, ${ this.getItemSizeAndOffset(start).offset }px, 0)`;}

增加了 itemSizeGetter 的實現可以通過 這裡 在線運行，你可以修改 itemSizeGetter 的返回值，看看是否能正常響應。

緩存計算結果

雖然上個例子實現了列表項的動態高度，但是每個列表項目的尺寸、偏移計算沒有任何緩存，在初次渲染、滾動更新時 itemSizeGetter 會被重複調用，性能並不理想。為了優這個性能，需要把尺寸、偏移信息進行一個緩存，在下次時候的時候直接從緩存中取得結果。

在常規情況下，用戶的滾動是從頂部開始的，並且是連續的。可以採取一個非常簡單的緩存策略，記錄最後一次計算尺寸、偏移的 index 。

  1. 把這個變數叫做 lastMeasuredIndex，默認值為 -1；存儲緩存結果的變數叫做 sizeAndOffsetCahce，類型為對象，實現代碼如下：

data() { return { lastMeasuredIndex: -1, startIndex: 0, sizeAndOffsetCahce: {}, ... };}

2. 緩存列表項高度的計算結果主要是修改 getItemSizeAndOffset 這個方法，增加緩存後的代碼如下：

getItemSizeAndOffset(index) { const { lastMeasuredIndex, sizeAndOffsetCahce, data, itemSizeGetter } = this; if (lastMeasuredIndex >= index) { return sizeAndOffsetCahce[index]; } let offset = 0; if (lastMeasuredIndex >= 0) { const lastMeasured = sizeAndOffsetCahce[lastMeasuredIndex]; if (lastMeasured) { offset = lastMeasured.offset + lastMeasured.size; } } for (let i = lastMeasuredIndex + 1; i <= index; i++) { const item = data[i]; const size = itemSizeGetter.call(null, item, i); sizeAndOffsetCahce[i] = { size, offset }; offset += size; } if (index > lastMeasuredIndex) { this.lastMeasuredIndex = index; } return sizeAndOffsetCahce[index];}

3. findNearestItemIndex 方法中的還在使用 itemSizeGetter 來獲取元素大小，我們在這裡可以修改成使用 getItemSizeAndOffset 來獲取，修改後的代碼如下：

findNearestItemIndex(scrollTop) { const { data, itemSizeGetter } = this; let total = 0; for (let i = 0, j = data.length; i < j; i++) { const size = this.getItemSizeAndOffset(i).size; // ... } return 0;}

使用了緩存之後的代碼可以點擊 這裡 在線運行，如果覺得性能並沒有明顯的改進，可以把數組的大小改成 20000 或者 50000 試試。

優化 contentHeight 的計算

如果你給 itemSizeGetter 加入一行 console.log，你會發現初次渲染的時候 contentHeight 會在第一次把所有列表項的 itemSizeGetter 執行一遍。

為了解決這個問題，需要引入另外一個屬性 estimatedItemSize。這個屬性的含義是為那些還沒計算高度的元素進行一個預估，那麼 contentHeight 就等於緩存過的列表項的高度和 + 未緩存過的列表項的數量 * estimatedItemSize。

  1. 首先需要為組件增加這個屬性，默認值為 30，代碼如下：

estimatedItemSize: { type: Number, default: 30}

2. 因為需要得知計算過高度的列表項的高度和，需要增加方法 getLastMeasuredSizeAndOffset，代碼如下：

getLastMeasuredSizeAndOffset() { return this.lastMeasuredIndex >= 0 ? this.sizeAndOffsetCahce[this.lastMeasuredIndex] : { offset: 0, size: 0 };}

3. 根據上面的演算法修改後的代碼如下：

contentHeight() { const { data, lastMeasuredIndex, estimatedItemSize } = this; let itemCount = data.length; if (lastMeasuredIndex >= 0) { const lastMeasuredSizeAndOffset = this.getLastMeasuredSizeAndOffset(); return lastMeasuredSizeAndOffset.offset + lastMeasuredSizeAndOffset.size + (itemCount - 1 - lastMeasuredIndex) * estimatedItemSize; } else { return itemCount * estimatedItemSize; }}

優化過 contentHeight 的實現可以通過 這裡 在線運行，你可以為 itemSizeGetter 屬性增加 console.log，來查看 itemSizeGetter 是如何運行的。

優化已緩存結果的搜索性能

使用過緩存的虛擬列表實際上還有優化的空間，比如 findNearestItemIndex 的搜索方式是順序查找的，時間複雜度為 O(N)。實際上列表項的計算結果天然就是一個有序的數組，可以使用二分查找來優化已緩存的結果的搜索性能，把時間複雜度降低到 O(lgN) 。

  1. 為組件增加 binarySearch 方法，代碼如下：

binarySearch(low, high, offset) { let index; while (low <= high) { const middle = Math.floor((low + high) / 2); const middleOffset = this.getItemSizeAndOffset(middle).offset; if (middleOffset === offset) { index = middle; break; } else if (middleOffset > offset) { high = middle - 1; } else { low = middle + 1; } } if (low > 0) { index = low - 1; } if (typeof index === undefined) { index = 0; } return index;}

這個二分查找和普通的二分查找略有不同，區別在於在任何情況下都不會返回 -1，可以思考下為什麼這個邏輯會是這樣。

2. 修改 findNearestItemIndex 方法，對於已緩存的結果使用二分查找，代碼如下：

findNearestItemIndex(scrollTop) { const { data, itemSizeGetter } = this; const lastMeasuredOffset = this.getLastMeasuredSizeAndOffset().offset; if (lastMeasuredOffset > scrollTop) { return this.binarySearch(0, this.lastMeasuredIndex, scrollTop); } else { // ... } return 0;}

使用了二分查找的實現可以通過 這裡 在線運行，從效果上來講和上個例子是沒有區別的。

優化未緩存結果的搜索性能

未緩存過的結果的搜索依然是順序搜索的，對於未緩存過的結果的搜索優化有兩個思路：

  1. 一次查找多條的數量，一個合理的數值是 contentHeight / estimatedSize ，找到超過自己查找結果的 index，然後使用二分查找
  2. 按指數數量查找，比如 1、2、4、8、16、32… 的順序來查找範圍，然後使用二分查找

筆者選擇了第二種方式，這個搜索演算法的名稱為 Exponential Search，這個演算法的搜索過程可以參考下圖：

  1. 增加 exponentialSearch 方法，代碼如下：

exponentialSearch(scrollTop) { let bound = 1; const data = this.data; const start = this.lastMeasuredIndex >= 0 ? this.lastMeasuredIndex : 0; while (start + bound < data.length && this.getItemSizeAndOffset(start + bound).offset < scrollTop) { bound = bound * 2; } return this.binarySearch(start + Math.floor(bound / 2), Math.min(start + bound, data.length), scrollTop);}

這個演算法與標準的 Exponential Search 也略有不同，主要的區別是不會從頭進行搜索，會從 lastMeasuredIndex 的位置開始搜索。

2. 修改 findNearestItemIndex 方法，代碼如下：

findNearestItemIndex(scrollTop) { const { data, itemSizeGetter } = this; const lastMeasuredOffset = this.getLastMeasuredSizeAndOffset().offset; if (lastMeasuredOffset > scrollTop) { return this.binarySearch(0, this.lastMeasuredIndex, scrollTop); } else { return this.exponentialSearch(scrollTop); }}

優化後的實現可以通過 這裡 在線運行，可以為代碼中加一下 console.log 觀察搜索的執行流程。

參考資料

在寫這篇文章的過程中，筆者參考了很多的開源項目，也參考了很多的文章，對我幫助比較大的有以下這些：

  • React Tiny Virtual List
  • React Virtualized
  • estimatedRowHeight 自適應 Cell

寫在最後

如果你有意了解如何實現一個虛擬列表，希望這篇文章能對你有所幫助。

對於一個靜態數據的虛擬列表，可以做的優化基本上這篇文章已經介紹了。如果你對這個主題依然很有興趣，可以嘗試為虛擬列表增加這麼兩個功能：

  1. 根據渲染結果動態的更新列表項的高度
  2. 數據更新後讓緩存失效，並儘可能讓失效緩存的範圍最小

感謝你有耐心讀完這篇文章，如果文章中有任何錯誤，或者你有任何疑問，請直接在文章評論區留言。


推薦閱讀：

TAG:前端組件 | Vuejs | 前端開發 |