看了 Furybean 的文章 《再談前端虛擬列表的實(shí)現(xiàn)》 學(xué)習(xí)了下 Virtual List。記了些筆記逗堵，并且動(dòng)手實(shí)踐了一下秉氧，在此記錄一下~
大數(shù)據(jù)列表優(yōu)化方案
1. 列表中有N個(gè)高度相同的元素
- 根據(jù)單個(gè)元素高度及元素?cái)?shù)量計(jì)算整個(gè)列表高度，使用空白元素?fù)纹鹆斜砀叨取?/li>
- 根據(jù) ScrollTop 屬性和元素高度計(jì)算從哪個(gè)元素開(kāi)始顯示蜒秤，并通過(guò)顯示容器的高度確定最后一個(gè)需要顯示的元素汁咏，最后返回需要顯示元素的數(shù)組。
- 用vue渲染需要顯示的列表作媚，通過(guò)scrollTop確定top元素的位置攘滩。
2. 高度不同
- 添加單個(gè)列表元素高度計(jì)算方法
itemSizeGetter，該方法返回單個(gè)列表元素的高度掂骏。 - 使用
itemSizeGetter方法求和計(jì)算整個(gè)列表高度轰驳。 - 使用 ScrollTop 屬性和
itemSizeGetter方法計(jì)算第一個(gè)顯示的列表元素的索引和偏移量。再配合顯示容器的高度計(jì)算最后一個(gè)顯示的列表元素的索引和偏移量。最后返回需要顯示元素的數(shù)組级解。 - 用vue渲染需要顯示的列表冒黑，通過(guò)scrollTop確定top元素的位置。
3. 使用緩存
為了避免每次滾動(dòng)列表都要反復(fù)計(jì)算勤哗，所以使用緩存將計(jì)算過(guò)的元素屬性都緩存下來(lái)抡爹。
具體做法：將所有測(cè)量計(jì)算過(guò)得元素的高度和偏移量保存在一個(gè)對(duì)象中，優(yōu)先從對(duì)象中獲取芒划，如果沒(méi)有再去計(jì)算高度和偏移量冬竟。
4. 獲取列表高度優(yōu)化
其實(shí)計(jì)算整個(gè)列表高度需要遍歷所有元素計(jì)算高度并求和，也是很消耗性能的民逼。
解決方案：定義一個(gè)所有元素的高度預(yù)估值泵殴，即所未顯示元素的平均高度。計(jì)算時(shí)根據(jù)緩存來(lái)判斷兩種情況拼苍，如果沒(méi)有緩存直接使用 數(shù)量 * 預(yù)估高度笑诅；如果有緩存，計(jì)算方法就是 緩存的偏移量 + 剩余元素?cái)?shù)量 * 預(yù)估高度疮鲫。
5. 優(yōu)化已緩存搜索
緩存數(shù)據(jù)檢索也需要消耗資源吆你，如何將資源消耗最小化？
文章中使用的是二分法搜索~（又 GET 到一個(gè)新技能 :D ）這里自己試著寫個(gè)二分法試試：
<div>
<input id="input" type="text"/>
<button onclick="middleSearch()">search</button>
<span id="result"></span>
</div>
<script>
let arr = []
let i = 10000
while(i--) {
arr.push(i*2)
}
function middleSearch(){
const value = parseInt(document.getElementById("input").value)
if (value != 0 && !value) {
return -1
}
let start = 0
let end = arr.length - 1
let middle
while(start <= end) {
middle = Math.floor((start + end)/2)
if (value == arr[middle]) {
console.log(middle)
document.getElementById("result").textContent = middle
return middle
} else if (arr[middle] > value) {
end = middle - 1
} else {
start = middle + 1
}
}
if (!middle) {
middle = -1
}
console.log(middle)
document.getElementById("result").textContent = middle
return middle
}
</script>
注意俊犯，二分法的前提必須是有序的數(shù)組集合才可以這么查找妇多。這種查找方式效率要比逐條查詢快很多。
6. 優(yōu)化未緩存搜索
這是一種指數(shù)查找的方式燕侠，具體方法文中只是給了個(gè)圖片顯示者祖，仔細(xì)看了下源碼，了解了一下指數(shù)查找方式贬循。
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
);
},
仔細(xì)看下邏輯其實(shí)并不難：
- 先獲取開(kāi)始查詢的位置 start咸包，從 lastMeasuredIndex 開(kāi)始查起。
- 循環(huán)執(zhí)行 getItemSizeAndOffset 方法獲取偏移量與 ScrollTop 屬性對(duì)比杖虾。如果偏移量小于 ScrollTop烂瘫，則 bound 乘以2（其實(shí)就是指數(shù)加1），直到 start 索引值超出元素?cái)?shù)量或者偏移量大于 ScrollTop奇适，跳出循環(huán)坟比。
- 跳出循環(huán)說(shuō)明在最后一個(gè)指數(shù)有我們需要的數(shù)據(jù)，獲取跳出循環(huán)前的 start 索引（即除以2）嚷往，最后還是使用二分法去找最終結(jié)果葛账。
一些思考
最后作者也留下了幾個(gè)思考的問(wèn)題：
- 根據(jù)渲染結(jié)果動(dòng)態(tài)的更新列表項(xiàng)的高度
- 數(shù)據(jù)更新后讓緩存失效，并盡可能讓失效緩存的范圍最小
第一個(gè)問(wèn)題不太理解皮仁，何謂 渲染結(jié)果籍琳。
第二個(gè)問(wèn)題呢菲宴，說(shuō)下大概猜想：
- 既然是數(shù)據(jù)更新，那么通過(guò)數(shù)據(jù)監(jiān)聽(tīng)趋急、對(duì)比喝峦、差異化等方式將更新的數(shù)據(jù)的 index 找出來(lái)。
- 在 getItemSizeAndOffset 中獲取緩存方法前判斷 index 相對(duì) data 數(shù)據(jù)是否更新呜达，更新則不讀取緩存而是重新計(jì)算谣蠢，并且更新緩存內(nèi)容。
一些問(wèn)題
- sizeAndOffsetCahce 緩存為何是對(duì)象而非數(shù)組查近，因?yàn)?/li>
- 二分法查找數(shù)據(jù)中眉踱，返回 0 不返回 -1 是因?yàn)橹笠玫?slice 方法的關(guān)系吧？如果為 -1 會(huì)查找數(shù)組后一位的數(shù)據(jù)霜威。
- 二分法查找數(shù)據(jù)中谈喳，
if (low > 0){ index = low - 1 }這段代碼的意義何在?
最后
看了下大牛的文章，收獲還是蠻多的侥祭。不過(guò)還是停留在接受信息的階段叁执，最好能夠在思考和理解之后輸出點(diǎn)內(nèi)容。
