看了 Furybean 的文章 《再谈前端虚拟列表的实现》 学习了下 Virtual List。记了些笔记，并且动手实践了一下，在此记录一下~

大数据列表优化方案

1. 列表中有N个高度相同的元素

• 根据单个元素高度及元素数量计算整个列表高度，使用空白元素撑起列表高度。
• 根据 ScrollTop 属性和元素高度计算从哪个元素开始显示，并通过显示容器的高度确定最后一个需要显示的元素，最后返回需要显示元素的数组。
• 用vue渲染需要显示的列表，通过scrollTop确定top元素的位置。

2. 高度不同

• 添加单个列表元素高度计算方法 itemSizeGetter，该方法返回单个列表元素的高度。
• 使用 itemSizeGetter 方法求和计算整个列表高度。
• 使用 ScrollTop 属性和 itemSizeGetter 方法计算第一个显示的列表元素的索引和偏移量。再配合显示容器的高度计算最后一个显示的列表元素的索引和偏移量。最后返回需要显示元素的数组。
• 用vue渲染需要显示的列表，通过scrollTop确定top元素的位置。

3. 使用缓存

为了避免每次滚动列表都要反复计算，所以使用缓存将计算过的元素属性都缓存下来。
具体做法：将所有测量计算过得元素的高度和偏移量保存在一个对象中，优先从对象中获取，如果没有再去计算高度和偏移量。

4. 获取列表高度优化

其实计算整个列表高度需要遍历所有元素计算高度并求和，也是很消耗性能的。
解决方案：定义一个所有元素的高度预估值，即所未显示元素的平均高度。计算时根据缓存来判断两种情况，如果没有缓存直接使用 数量 * 预估高度；如果有缓存，计算方法就是 缓存的偏移量 + 剩余元素数量 * 预估高度。

5. 优化已缓存搜索

缓存数据检索也需要消耗资源，如何将资源消耗最小化？
文章中使用的是二分法搜索~（又 GET 到一个新技能 :D ）这里自己试着写个二分法试试：

    <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>

注意，二分法的前提必须是有序的数组集合才可以这么查找。这种查找方式效率要比逐条查询快很多。

6. 优化未缓存搜索

这是一种指数查找的方式，具体方法文中只是给了个图片显示，仔细看了下源码，了解了一下指数查找方式。

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
  );
},

仔细看下逻辑其实并不难：

• 先获取开始查询的位置 start，从 lastMeasuredIndex 开始查起。
• 循环执行 getItemSizeAndOffset 方法获取偏移量与 ScrollTop 属性对比。如果偏移量小于 ScrollTop，则 bound 乘以2（其实就是指数加1），直到 start 索引值超出元素数量或者偏移量大于 ScrollTop，跳出循环。
• 跳出循环说明在最后一个指数有我们需要的数据，获取跳出循环前的 start 索引（即除以2），最后还是使用二分法去找最终结果。

一些思考

最后作者也留下了几个思考的问题：

1. 根据渲染结果动态的更新列表项的高度
2. 数据更新后让缓存失效，并尽可能让失效缓存的范围最小

第一个问题不太理解，何谓 渲染结果。
第二个问题呢，说下大概猜想：

1. 既然是数据更新，那么通过数据监听、对比、差异化等方式将更新的数据的 index 找出来。
2. 在 getItemSizeAndOffset 中获取缓存方法前判断 index 相对 data 数据是否更新，更新则不读取缓存而是重新计算，并且更新缓存内容。

一些问题

• sizeAndOffsetCahce 缓存为何是对象而非数组，因为
• 二分法查找数据中，返回 0 不返回 -1 是因为之后要用到 slice 方法的关系吧？如果为 -1 会查找数组后一位的数据。
• 二分法查找数据中，if (low > 0){ index = low - 1 } 这段代码的意义何在?

最后

看了下大牛的文章，收获还是蛮多的。不过还是停留在接受信息的阶段，最好能够在思考和理解之后输出点内容。