Поскольку существует проблема производительности, трудно преодолеть узкие места производительности DOM, большие списки. Поэтому происходит «частичный рендеринг» программы оптимизации, что и является основной идеей виртуального списка.
Виртуальный список, вопрос о необходимости сосредоточиться на следующих моментах:
- Схема обновления DOM для видимой области
- План обработки событий
Ниже приводится разбивка описаний по одному.
Расчет видимой области
Вычисление видимой области заключается в использовании высоты текущего окна просмотра и расстояния прокрутки текущей полосы прокрутки для получения интервала координат видимой области. После вычисления интервала координат видимой области элементы списка, попадающие в этот интервал, отфильтровываются, при этом также должны быть вычислены координаты элементов списка.
Рассмотрим следующую ситуацию,
- Высота нашего окна просмотра составляет 100 пикселей.
- Теперь мы свернули 100px
- Наш список списка, каждая высота 20px
Основываясь на этих условиях, мы можем рассчитать, что текущая видимая область — это элементы с 11 по 20.
01 - 05，可视区域上方
+----+-----------+--------
| 06 | 100 ~ 120 |
+----+-----------+
| 07 | 120 ~ 140 |
+----+-----------+
| 08 | 140 ~ 160 | 可视区域
+----+-----------+
| 09 | 160 ~ 180 |
+----+-----------+
| 10 | 180 ~ 200 |
+----+-----------+--------
11 - N，可视区域下方
Это связано с тем, что высота элемента списка фиксирована.Мы можем подсчитать, что в 100px, которые были прокручены, было прокручено 5 элементов списка, поэтому видимая область начинается с 6-го элемента, а высота области просмотра составляет 100px, может вместить 100/20 или 5 шт.
Случай с приведенным выше примером очень прост и не вызывает проблем с производительностью, поэтому его не стоит обсуждать. Есть и другая более сложная ситуация, то есть высота элемента списка не фиксирована, а определяется по содержимому.
На данный момент мы не можем напрямую использовать четыре арифметические операции для вычисления записи, соответствующей видимой области, за один шаг.
Вместо этого должен быть реализован механизм для записи координат всех элементов списка путем проверки того, попадает ли элемент списка в область просмотра.
Следующее направлено на этот вопрос.
Координаты списка предметов
Координаты элемента списка, которые можно определить по следующей формуле:
<列表项 top 坐标值> = <上一项 top 坐标值> + <上一项的高度值>
Значение верхней координаты первого элемента списка равно 0, поэтому, если высоты всех элементов списка записаны, можно вычислить значение верхней координаты любого элемента списка. Таким образом, проблема заключается в том, что должен быть какой-то способ сохранить высоту каждой записи.
Я думаю, что самое простое решение — использовать массив для хранения значений высоты каждого элемента в списке во взаимно однозначном соответствии. Затем, когда получено значение координат конкретного элемента, извлекается значение от первого элемента до целевого элемента и выполняется операция накопления. Обратитесь к следующему коду, чтобы понять:
// 假设使用该数组存储列表每一项的高度
const itemHeightStore = [20, 20, 20, 20, 20]
// 使用该方法，可以算出列表中指定项的 top 坐标值
const getTop = (index) => {
let sum = 0
while (index--) sum += itemHeightStore[index] || 0
return sum
}
// 第一项
getTop(0) // 0
// 第二项
getTop(1) // 20
// ...
Эта реализация работает нормально.
Однако у этого алгоритма есть серьезные проблемы с производительностью: каждый раз при получении координат элемента списка необходимо пройтись по списку, а сложность составляет O(n), что очень неэкономично.
Что, если по-другому хранить координаты каждого элемента напрямую?
На самом деле суть та же. Поскольку высота элементов нашего списка не фиксирована, когда мы быстро перетаскиваем полосу прокрутки в разные области, нам необходимо вычислить высоту в соответствии с локальным результатом рендеринга для обновления записей массива, а при обновлении элемента все последующие элементы списка элемент Все обновления также требуются, а сложность такая же, как O(n).
Итак, мы используем массив для поддержания высоты каждого элемента или координаты, в списке относительно большого размера, и они будут потреблять много времени процессора.
Может быть, TypedArray будет лучше?
Присмотревшись к массиву в приведенном выше примере, совмещенному со списком в реальности, мы можем наблюдать явление:
Элементы списка, как правило, похожи, и во многих случаях высота также может быть одинаковой.
Основываясь на этом опыте, мы можем использовать интервал для хранения высоты элемента списка.
Сокращает количество операций обхода списка за счет свертывания элементов списка, расположенных рядом друг с другом и имеющих одинаковую высоту.
Например, следующее выражение:
const range = {
start: 0,
end: 4,
value: 20
}
Для элементов с 1 по 5 в списке хорошо работает высота 20 пикселей.
Если нам нужно найти высоту шестого элемента, нам нужно всего лишь выполнить простую четырехкратную арифметическую операцию без обхода и накопления пяти элементов.
Легко сделать вывод, что, в большинстве случаев, если список является той же высотой, только отдельные записи при высокой несовместимости (например, Text Wrap), будет иметь очень хорошую производительность.
Конечно, использование диапазонов не обходится без затрат. Это, в свою очередь, усложняет структуру данных.
Из-за распада соседних узлов одинаковой высоты, сохраненный список не может соответствовать исходному элементу одно к одному. Итак, мы не можем просто знать, где высота элемента списка, который мы хотим запрашивать, сохраняется, Для этой цели необходимо разработать специальный механизм хранения.
Этот механизм хранения должен иметь следующие характеристики:
- Эффективный запрос. Вы можете быстро получить соответствующий диапазон и все диапазоны перед диапазоном через номер элемента списка.
- Эффективно модифицируйте. Он может эффективно вставлять и удалять диапазоны, объединять диапазоны и разделять диапазоны.
В сочетании с полученными знаниями о структуре данных мы можем рассмотреть возможность использования какого-либо BST для хранения, чтобы получить хорошую производительность запросов и вставки. А слияние диапазонов, разделение и т. д. можно реализовать специальным классом для управления.
Обновление: протестировано, с использованиемBinary Indexed TreeВыполнено очень хорошо. Но вот главным образом объяснить идею, код не будет обновляться.
// Avl.ts
const SLIGHTLY_UNBALANCED_RIGHT = -1
const SLIGHTLY_UNBALANCED_LEFT = 1
const UNBALANCED_RIGHT = -2
const UNBALANCED_LEFT = 2
// 树结点
class AvlNode<K extends any = any> {
key: any
left: AvlNode<K> | null
right: AvlNode<K> | null
parent: AvlNode<K> | null
_height: number
_prevHeight: number
constructor(key: K) {
this.key = key
this.left = null
this.right = null
this.parent = null
this._height = 0
this._prevHeight = 0
}
// 刷新前的高度，方便平衡操作
get prevHeight() {
return this._prevHeight | 0
}
get height() {
return this._height | 0
}
set height(value) {
this._prevHeight = this._height | 0
this._height = value | 0
}
// 左子树高度
get leftHeight() {
if (this.left === null) return -1
return this.left.height | 0
}
// 右子树高度
get rightHeight() {
if (this.right === null) return -1
return this.right.height | 0
}
// 平衡因子
get balanceFactor() {
return this.leftHeight - this.rightHeight
}
updateHeight() {
const { leftHeight, rightHeight } = this
const height = ((leftHeight > rightHeight ? leftHeight : rightHeight) + 1) | 0
this.height = height
}
}
// AVL 树
export class Avl<K extends any = any> {
_root: AvlNode<K> | null
_size: number
constructor() {
this._root = null
this._size = 0
}
get size() {
return this._size
}
// 插入节点
insert(key: K) {
const node = new AvlNode<K>(key)
const insertPoint = this._nodeInsert(node)
// 本次插入是重复结点，直接更新 key / value
// 无新结点插入，所以无需进行插入后的调整
if (insertPoint == null) return
// 新增结点成功时，回溯调整搜索路径上的结点
this._adjustAfterInsertion(insertPoint)
}
// 删除节点，返回是否成功删除结点
delete(key: K): boolean {
// 搜索待删除结点
const targetNode = this._nodeSearch(key)
// 未找到 value 对应结点
if (targetNode == null) return false
// 执行删除结点操作
const backtracking = this._nodeErase(targetNode)
const parent = backtracking[0]
// 回溯调整搜索路径上的结点
if (parent !== null) {
this._adjustAfterRemoval(parent)
}
return true
}
// 通过 key 查找包含该 key 范围的节点 key
search(key: K) {
const node = this._nodeSearch(key)
if (node !== null) return node.key
return null
}
// 搜索 start 、end 两个 key 之间的所有 key 列表
searchRange(start: K, end: K) {
const results: K[] = []
// 找到符合条件的 root 节点
let root = this._root
while (root !== null) {
const result1 = start.compareTo(root.key)
const result2 = end.compareTo(root.key)
// 当前节点比 start 小，不再搜索左子树
if (result1 > 0) {
root = root.right
continue
}
// 当前节点大于 end，不再搜索右子树
if (result2 < 0) {
root = root.left
continue
}
break
}
if (!root) return results
const stack = []
let current: AvlNode<K> | null = root
while (stack.length || current) {
while (current) {
stack.push(current)
// 当前节点比 start 小，不再搜索 current 的左子树
if (start.compareTo(current.key) > 0) break
current = current.left
}
if (stack.length) {
// 指向栈顶
current = stack[stack.length - 1]
const gteStart = start.compareTo(current.key) <= 0
const lteEnd = end.compareTo(current.key) >= 0
if (gteStart && lteEnd) {
results.push(current.key)
}
stack.pop()
// 只有 current 比 end 小，才继续搜索 current 的右子树
if (lteEnd) {
current = current.right
}
else {
current = null
}
}
}
return results
}
// 增加结点数量
_increaseSize() {
this._size += 1
}
// 减少结点数量
_decreaseSize() {
this._size -= 1
}
// 设置左子结点，同时维护 parent 关系
_setLeft(node: AvlNode<K>, child: AvlNode<K> | null) {
// 断开旧 left 结点
if (node.left !== null) {
node.left.parent = null
}
// 连接新结点
if (child !== null) {
// 从旧 parent 中断开
if (child.parent !== null) {
child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)
}
child.parent = node
}
node.left = child
}
// 设置右子结点，同时维护 parent 关系
_setRight(node: AvlNode<K>, child: AvlNode<K> | null) {
// 断开旧 right 结点
if (node.right !== null) {
node.right.parent = null
}
// 连接新结点
if (child !== null) {
// 从旧 parent 中断开
if (child.parent !== null) {
child.parent.left === child ? (child.parent.left = null) : (child.parent.right = null)
}
child.parent = node
}
node.right = child
}
// 获取中序遍历顺序的前驱结点
_inorderPredecessor(node: AvlNode<K> | null) {
if (node == null) return null
// 1. 有左子树，找到左子树最大元素
if (node.left !== null) {
return this._maximumNode(node.left)
}
// 2. 没有左子树，往上搜索
let parent = node.parent
while (parent != null) {
if (node == parent.right) {
return parent
}
node = parent
parent = node.parent
}
// 4. 搜索到根
return null
}
// 获取最大的结点
_maximumNode(subRoot: AvlNode<K>) {
let current = subRoot
while (current.right !== null) current = current.right
return current
}
// 设置根结点
_setRoot(node: AvlNode<K> | null) {
if (node === null) {
this._root = null
return
}
this._root = node
// 如果本身在树中，则从树中脱落，成为独立的树根
if (node.parent !== null) {
node.parent.left === node ? (node.parent.left = null) : (node.parent.right = null)
node.parent = null
}
}
// 将树上某个结点替换成另一个结点
private _replaceNode(node: AvlNode<K>, replacer: AvlNode<K> | null) {
if (node === replacer) return node
// node 为 root 的情况
if (node === this._root) {
this._setRoot(replacer)
}
else {
// 非 root，有父结点的情况
const parent = node.parent as AvlNode<K>
if (parent.left === node) this._setLeft(parent, replacer)
else this._setRight(parent, replacer)
}
return node
}
// 左旋，返回新顶点，注意旋转完毕会从原本的树上脱落
private _rotateLeft(node: AvlNode<K>) {
const parent = node.parent
// 记录原本在树上的位置
const isLeft = parent !== null && parent.left == node
// 旋转
const pivot = node.right as AvlNode<K>
const pivotLeft = pivot.left
this._setRight(node, pivotLeft)
this._setLeft(pivot, node)
// 旋转完毕
// 新顶点接上树上原本的位置
if (parent !== null) {
if (isLeft) this._setLeft(parent, pivot)
else this._setRight(parent, pivot)
}
// ---
if (node === this._root) {
this._setRoot(pivot)
}
node.updateHeight()
pivot.updateHeight()
return pivot
}
// 右旋，返回新顶点，注意旋转完毕会从原本的树上脱落
private _rotateRight(node: AvlNode<K>) {
const parent = node.parent
// 记录原本在树上的位置
const isLeft = parent !== null && parent.left === node
// 旋转
const pivot = node.left as AvlNode<K>
const pivotRight = pivot.right
this._setLeft(node, pivotRight)
this._setRight(pivot, node)
// 旋转完毕
// 新顶点接上树上原本的位置
if (parent !== null) {
if (isLeft) this._setLeft(parent, pivot)
else this._setRight(parent, pivot)
}
// ---
if (node === this._root) {
this._setRoot(pivot)
}
node.updateHeight()
pivot.updateHeight()
return pivot
}
// 搜索 Node
private _nodeSearch(key: K) {
let current = this._root
while (current !== null) {
let result = key.compareTo(current.key)
if (result === 0) return current
if (result < 0) current = current.left
else current = current.right
}
return null
}
// 在树里插入结点或者刷新重复结点
// 返回新插入（或刷新）的结点
private _nodeInsert(node: AvlNode<K>) {
// 空树
if (this._root === null) {
this._setRoot(node)
this._increaseSize()
return null
}
const key = node.key
let current = this._root
// 查找待插入的位置
while (true) {
const result = key.compareTo(current.key)
if (result > 0) {
if (current.right === null) {
this._setRight(current, node)
this._increaseSize()
return current
}
current = current.right
}
else if (result < 0) {
if (current.left === null) {
this._setLeft(current, node)
this._increaseSize()
return current
}
current = current.left
}
else {
// No duplicates, just update key
current.key = key
return null
}
}
}
// 从树上移除一个结点
private _nodeErase(node: AvlNode<K>) {
// 同时拥有左右子树
// 先转换成只有一颗子树的情况再统一处理
if (node.left !== null && node.right !== null) {
const replacer = this._inorderPredecessor(node)!
// 使用前驱结点替换身份
// 此时问题转换成删掉替代结点（前驱），
// 从而简化成只有一个子结点的删除情况
node.key = replacer.key
// 修改 node 指针
node = replacer
}
// 删除点的父结点
const parent = node.parent
// 待删结点少于两颗子树时，使用子树 (或 null，没子树时) 顶替移除的结点即可
const child = node.left || node.right
this._replaceNode(node, child)
this._decreaseSize()
return [ parent, child, node ]
}
// AVL 树插入结点后调整动作
// 自底向上调整结点的高度
// 遇到离 current 最近的不平衡点需要做旋转调整
// 注意: 对最近的不平衡点调整后 或者 结点的高度值没有变化时
// 上层结点便不需要更新
// 调整次数不大于1
_adjustAfterInsertion(backtracking: AvlNode<K> | null) {
let current = backtracking
// 往上回溯，查找最近的不平衡结点
while (current !== null) {
// 更新高度
current.updateHeight()
// 插入前后，回溯途径结点的高度没有变化，则无需继续回溯调整
if (current.height === current.prevHeight) break
// 若找到不平衡结点，执行一次调整即可
if (this._isUnbalanced(current)) {
this._rebalance(current)
// 调整过，则上层无需再调整了
break
}
current = current.parent
}
}
// AVL树删除结点后调整动作
// 自底向上调整结点的高度
// 遇到离 current 最近的不平衡点需要做旋转调整
// 注意: 对最近的不平衡点调整后，其上层结点仍然可能需要调整
// 调整次数可能不止一次
_adjustAfterRemoval(backtracking: AvlNode<K> | null) {
let current = backtracking
while (current !== null) {
// 更新高度
current.updateHeight()
// 删除前后，回溯途径结点的高度没有变化，则无需继续回溯调整
if (current.height === current.prevHeight) break
if (this._isUnbalanced(current)) {
this._rebalance(current)
}
// 与插入不同，调整过后，仍然需要继续往上回溯
// 上层结点（若有）仍需判断是否需要调整
current = current.parent
}
}
// LL
_adjustLeftLeft(node: AvlNode<K>) {
return this._rotateRight(node)
}
// RR
_adjustRightRight(node: AvlNode<K>) {
return this._rotateLeft(node)
}
// LR
_adjustLeftRight(node: AvlNode<K>) {
this._rotateLeft(node.left!)
return this._rotateRight(node)
}
// RL
_adjustRightLeft(node: AvlNode<K>) {
this._rotateRight(node.right!)
return this._rotateLeft(node)
}
// 检查结点是否平衡
_isUnbalanced(node: AvlNode<K>) {
const factor = node.balanceFactor
return factor === UNBALANCED_RIGHT || factor === UNBALANCED_LEFT
}
// 重新平衡
_rebalance(node: AvlNode<K>) {
const factor = node.balanceFactor
// Right subtree longer (node.factor: -2)
if (factor === UNBALANCED_RIGHT) {
let right = node.right!
// RL, node.right.factor: 1
if (right.balanceFactor === SLIGHTLY_UNBALANCED_LEFT) {
return this._adjustRightLeft(node)
}
else {
// RR, node.right.factor: 0|-1
// 即 right.rightHeight >= right.leftHeight
return this._adjustRightRight(node)
}
}
else if (factor === UNBALANCED_LEFT) {
// Left subtree longer (node.factor: 2)
let left = node.left!
// LR, node.left.factor: -1
if (left.balanceFactor === SLIGHTLY_UNBALANCED_RIGHT) {
return this._adjustLeftRight(node)
}
else {
// LL, node.left.factor: 1 | 0
// 即 left.leftHeight >= left.rightHeight
return this._adjustLeftLeft(node)
}
}
return node
}
}
export function createAvl() {
return new Avl()
}
// SparseRangeList.ts
import { createAvl, Avl } from './Avl'
// 区间类
class Range {
start: number
end: number
constructor(start: number, end?: number) {
this.start = start
this.end = end || start
}
// 用于 Avl 中节点的比较
//
// 列表中项目范围是连续的，必定不会重叠的
// 如果传入的 key 为重叠的，则意味着希望通过构造一个子 Range 搜索所在的 RangeValue
// 例如构造一个 { start: 10, end: 10, value: 'any' }，搜索树中
// 范围包含 10~10 的 RangeValue，如 { start: 0, end: 20, value: 'any' }
compareTo(other: Range) {
if (other.start > this.end!) return -1
if (other.end! < this.start) return 1
return 0
}
}
// 区间-值 类
class RangeValue<T> extends Range {
value: T
constructor(start: number, end: number, value: T) {
super(start, end)
this.value = value
}
clone(): RangeValue<T> {
return new RangeValue(this.start, this.end!, this.value)
}
}
// 最终存储区间-值的类，内部使用 Avl 存储所有 RangeValue
export default class SparseRangeList<T> {
_size: number
defaultValue: T
valueTree: Avl
constructor(size: number, defaultValue: T) {
this._size = size
this.defaultValue = defaultValue
this.valueTree = createAvl()
}
get size() {
return this._size
}
resize(newSize: number) {
newSize = newSize | 0
// 无调整
if (this._size === newSize) return
// 扩容
if (this._size < newSize) {
this._size = newSize
return
}
// 缩小，清空超出的部分，再缩小
this.setRangeValue(newSize - 1, this._size - 1, this.defaultValue)
this._size = newSize
}
// 返回区间包含 index 的 RangeValue 的值
getValueAt(index: number): T {
const result = this.valueTree.search(new Range(index))
if (result) return result.value
return this.defaultValue
}
/**
* 设值方法，
* 自动与相邻的相同值的合并成更大的 RangeValue，
* 导致原本的 RangeValue 不连续，则会
* 自动切分成两个或者三个 RangeValue。
*
* a-------------a
* |a------------|b------------|c-----------|...
*
* 结果：
* |a-------------------|b-----|c-----------|...
*
*
* d-------------d
* |a------------|b------------|c-----------|...
*
* 结果：
* |a-----|d------------|b-----|c-----------|...
*
*/
setRangeValue(start: number, end: number, value: T) {
if (!this.size) return
if (end >= this.size) end = this.size - 1
// 所有与当前传入区间范围有重叠部分，
// -1，+1 将接壤的毗邻 RangeValue 也纳入（如果存在的话），
// 毗邻的 RangeValue 要检查否要合并。
let prevSiblingEnd = start - 1
let nextSiblingStart = end + 1
let rangeValues = this.treeIntersecting(prevSiblingEnd, nextSiblingStart)
// 如果没有重叠的部分，则作为新的 RangeValue 插入，直接结束
// 如果有重叠的部分，就要处理合并、拆分
if (rangeValues.length) {
let firstRange = rangeValues[0]
let lastRange = rangeValues[rangeValues.length - 1]
// end 边界比传入的 start 小，说明是接壤毗邻的更小的 RangeValue
//
// 1. 如果毗邻的 RangeValue 的值跟当前带插入的值不一致，
// 则直接将毗邻的 RangeValue 从列表中移除，
// 不需要做任何特殊操作，正常的插入操作即可
//
// 2. 否则如果毗邻的 RangeValue 的值跟当前待插入的值一致，
// 则将两个 RangeValue 的 Range 合并（修改 start即可），
// 然后这个毗邻的 RangeValue 也自然变成重叠的，正常执行后续
// 的重叠处理逻辑即可（拆分）
if (firstRange.end < start) {
if (firstRange.value !== value) {
rangeValues.shift()
}
else {
start = firstRange.start
}
}
// 接壤毗邻的更大的 RangeValue，处理思路
// 跟上面处理毗邻的更小的 RangeValue 一样的
if (lastRange.start > end) {
if (lastRange.value !== value) {
rangeValues.pop()
}
else {
end = lastRange.end
}
}
// 结束毗邻 RangeValue 合并逻辑
// 开始处理相交的 RangeValue 流程
const length = rangeValues.length
let index = 0
while (index < length) {
const currentRangeValue = rangeValues[index]
const { value: currentValue, start: currentStart, end: currentEnd } = currentRangeValue
// 先移除掉该重叠的 RangeValue，然后：
this.valueTree.delete(currentRangeValue)
// Case 1. 如果是当前 RangeValue 完整包含在传入的范围内，
// 则不需要处理，因为整个范围都将被传入的值覆盖。
if (currentStart >= start && currentEnd <= end) {
index += 1
continue
}
// Case2. 部分相交，该 RangeValue 的大的一侧在传入的范围内，而小的一侧不在。
// 需要做切分操作，以重叠的位置作为切分点，比较小的一侧（不重叠的部分）重新插入，
// 比较大的的那一部分，会被传入的值覆盖掉
if (currentStart < start) {
// 如果值不一样，则以相交的位置作为切分点，非重叠部分重新插入，重叠部分用待插入的值覆盖。
if (currentValue !== value) {
this._insert(currentStart, start - 1, currentValue)
}
else {
start = currentStart
}
}
// Case3. 部分相交，该 RangeValue 的小的一侧在传入的范围内，而大的一侧不在。
// 同 Case 2 做切分操作，只是反向。
if (currentEnd > end) {
if (currentValue !== value) {
this._insert(end + 1, currentEnd, currentValue)
}
else {
end = currentEnd
}
}
index += 1
}
}
this._insert(start, end, value)
}
setValue(index: number, value: T) {
this.setRangeValue(index, index, value)
}
/**
* 筛选出与指定区间有重叠的 RangeValue，即：
*
* 1. 相互部分重叠
*
* o----------o o---------o
* >start------------------end<
*
*
* 2. 相互完全重叠关系
*
* o----------------o
* >start--------end<
*
*
* 3. 包含或被包含关系
*
* o--------------------------------------o
* o-------------------------------o
* o-------------------------------o
* o-----o o-----o o----o
* >start--------------------end<
*
*/
treeIntersecting(start: number, end: number): RangeValue[] {
const startRange = new Range(start)
const endRange = new Range(end)
return this.valueTree.searchRange(startRange, endRange)
}
/**
* 返回指定范围内所有 RangeValue
* 范围内有无值的 Range 的话，则使用
* 携带默认值的 RangeValue 代替
* 从而确保返回的结果是线性的、每个区间都有值的，如:
*
* start>...<end 范围内有 A、B 两个 RangeValue，所有空洞都用 Default 补足
* +-----------|-----|-----------|-----|-----------+
* | Default | A | Default | B | Default |
* >start------|-----|-----------|-----|--------end<
*
*/
intersecting(start: number, end: number): RangeValue[] {
const ranges = this.treeIntersecting(start, end)
if (!ranges.length) {
if (!this.size) return []
return [ new RangeValue(start, end, this.defaultValue) ]
}
let result = []
let range
let index = 0
let length = ranges.length
while (index < length) {
range = ranges[index].clone()
// 传入的 (start, end) 右侧与某个 RangeValue 重叠，
// 左侧没有命中，则左侧区域手动塞入一个携带默认
// 值的 RangeValue
if (range.start > start) {
result.push(new RangeValue(start, range.start - 1, this.defaultValue))
}
result.push(range)
// 将 start 的位置右移，
// 以便下个 range 的比较
start = range.end + 1
index += 1
}
// 如果最后一个 range，与传入的范围只有左侧重叠，
// 而右侧没有重叠的地方，则手动塞入一个携带默认值
// 的 RangeValue
if (range.end < end) {
result.push(new RangeValue(range.end + 1, end, this.defaultValue))
}
else if (range.end > end) {
// 否则如果最后一个 range 的范围已经超出需要的范围，则裁剪
range.end = end
}
return result
}
values() {
if (!this.size) return []
return this.intersecting(0, this.size - 1)
}
_insert(start: number, end: number, value: T) {
if (value !== this.defaultValue) {
const rangeValue = new RangeValue(start, end, value)
this.valueTree.insert(rangeValue)
}
}
}
export function create<T>(size: number, value: T) {
return new SparseRangeList(size, value)
}
import { create as createSparseRangeList } from './SparseRangeList'
// 创建一个默认预估高度为 20 的列表项存储对象
const itemHeightStore = createSparseRangeList(wrappedItems.length, 20)
// 设置第二项为 40px
itemHeightStore.setValue(1, 40)
// 获取第二项的高度
itemHeightStore.getValueAt(1) // 40
// 获取列表项的 top 坐标
const top = (index: number): number => {
if (index === 0) return 0
// 0 ～ 上一项的高度累加
const rangeValues = itemHeightStore.intersecting(0, index - 1)
const sumHeight = rangeValues.reduce((sum: number, rangeValue: any) => {
const span = rangeValue.end - rangeValue.start + 1
return sum + rangeValue.value * span
}, 0)
return sumHeight
}
top(1) // 20
// 计算列表总高度：
const listHeight = itemHeightStore
.values()
.reduce((acc: number, rangeValue: any) => {
const span = rangeValue.end - rangeValue.start + 1
const height = rangeValue.value * span
return acc + height
}, 0)
Подсчет видимых элементов
После завершения управления высотой элементов списка следующий ключевой момент, который необходимо решить, — вычислить, какие элементы являются видимыми.
Самый простой способ реализовать это — напрямую пройтись по нашему списку хранения высоты узла, сравнить его с диапазоном координат области просмотра одну за другой и отфильтровать записи, которые попадают (или частично попадают) внутрь области просмотра. Исходя из соображений производительности, мы, конечно, не можем быть такими простыми и грубыми. Мы можем попробовать следующее, чтобы улучшить производительность:
1. Предполагаемая начальная точка входа + коррекция дихотомии.
Вычисляет первый элемент, который может появиться в области просмотра, исходя из предполагаемой высоты элемента или высоты по умолчанию. Например, координаты верхнего края нашего вьюпорта (то есть расстояние, на которое прокручивается полоса прокрутки) 100px, а расчетная высота нашего элемента 20px, то можно догадаться, что первый появившийся в вьюпорте элемент 100 / 20 + 1, это первый элемент в окне просмотра. Непосредственно вычисляем координаты 6-го входа, проверяем, попадает ли он в окно просмотра, и на основе разрыва результата делаем дихотомическое предположение, пока не найдем реальную начальную точку входа.
2. Расчетная конечная точка входа + коррекция дихотомии
После вычисления входа в начальную точку разделите высоту окна просмотра на расчетную высоту входа, чтобы рассчитать, сколько элементов может отображаться внутри окна просмотра, и добавьте номер начальной точки к этому числу, которое является предполагаемым номером входа в конечную точку. Используйте ту же логику исправления, что и выше, пока не будет найдена правильная запись конечной точки области просмотра.
Описание может быть трудным для понимания, но вот ключевые фрагменты:
// 内部方法，计算局部渲染数据切片的起止点
private _calcSliceRange() {
if (!this.dataView.length) {
return { sliceFrom: 0, sliceTo: 0 }
}
// 数据总量
const MAX = this.dataView.length
// 视口上边界
const viewportTop = (this.$refs.viewport as any).scrollTop || 0
// 视口下边界
const viewportBottom = viewportTop + this.viewportHeight
// 预估条目高度
const estimatedItemHeight = this.defaultItemHeight
// 从估算值开始计算起始序号
let sliceFrom = Math.floor(viewportTop / estimatedItemHeight!)
if (sliceFrom > MAX - 1) sliceFrom = MAX - 1
while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {
const itemTop = this._top(sliceFrom)
// 条目顶部相对于 viewport 顶部的偏移
const itemOffset = itemTop - viewportTop
// 1. 该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条
if (itemOffset > 0) {
// 二分法快速估算下一个尝试位置
const diff = itemOffset / estimatedItemHeight!
sliceFrom -= Math.ceil(diff / 2)
continue
}
// 2. 恰好显示该条目的顶部，则该条目为本次视口的首条元素
if (itemOffset === 0) break
// 以下都是 itemOffset < 0
const itemHeight = this._itemHeight(sliceFrom)
// 3. 该条目在顶部露出了一部分，则该条目为本次视口的首条元素
if (itemOffset < itemHeight) break
// 4. 该条目已被滚出去视口，继续测试下一条
// 二分法快速估算下一个尝试位置
const diff = -itemOffset / estimatedItemHeight!
sliceFrom += Math.ceil(diff / 2)
}
// 从估算值开始计算结束序号
let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!)
if (sliceTo > MAX) sliceTo = MAX
while (sliceTo > sliceFrom && sliceTo <= MAX) {
const itemTop = this._top(sliceTo)
const itemHeight = this._itemHeight(sliceTo)
const itemBottom = itemTop + itemHeight
// 条目底部相对于 viewport 底部的偏移
const itemOffset = itemBottom - viewportBottom
// 1. 该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条
if (itemOffset < 0) {
// 二分法快速估算下一个尝试位置
const diff = -itemOffset / estimatedItemHeight!
sliceTo += Math.ceil(diff / 2)
continue
}
// 2. 恰好显示该条目的底部，则该条目为视口中最后一项
if (itemOffset === 0) break
// 3. 该条目在底部被裁剪了一部分，则该条目为本次视口的末项
if (itemOffset < itemHeight) break
// 该条目还未出场，继续测试上一条
// 二分法快速估算下一个尝试位置
const diff = itemOffset / estimatedItemHeight!
sliceTo -= Math.ceil(diff / 2)
}
// slice 的时候，不含 end，所以 + 1
sliceTo += 1
return { sliceFrom, sliceTo }
}
Вышеизложенное является основной частью расчета видимой области. Полный код будет дан позже.
обновление модели каталога
Поскольку мы используем Vue для реализации виртуальных списков, мы можем сэкономить много утомительного управления деталями с точки зрения обновлений DOM. Нам нужно только заботиться о том, чтобы выяснить, какие элементы должны отображаться в текущем окне просмотра, когда список где-то прокручивается.
Тем не менее, учитывая плавность прокрутки и производительность манипуляций с DOM в таких браузерах, как IE11, нам пришлось сделать гораздо больше.
Массовые манипуляции с DOM
Мы можем видеть на панели инструментов разработчика IE11, что во время процесса прокрутки частая вставка и удаление узлов в начало и конец виртуального списка приведет к очень серьезным проблемам с производительностью. Итак, мы должны контролировать частоту манипуляций с DOM.
Пакетирование может частично решить эту проблему.
Конкретная идея заключается в том, что в обратном вызове прокрутки мы вычисляем начальный и конечный порядковые номера узлов в видимой области, и не применяем их напрямую, а добавляем дополнительное количество отрисовок. Например, если мы подсчитали, что в данный момент должно быть отрисовано 20 ~ 30 элементов, мы можем добавить по 10 дополнительных отображаемых элементов до и после каждого, то есть 10 ~ 40, чтобы одновременно отрисовывалось 30 узлов. Продолжая прокручивать, мы проверяем, находится ли новый начальный и конечный диапазон в диапазоне от 10 до 40. Если это так, мы не добавляем и не удаляем новые узлы.
Основная реализация:
// 刷新局部渲染数据切片范围
private _updateSliceRange(forceUpdate?: boolean) {
// 上下方额外多渲染的条目波动量
const COUNT = this._preRenderingCount()
// 预渲染触发阈值
const THRESHOLD = this._preRenderingThreshold()
// 数据总量
const MAX = this.dataView.length
// 计算出准确的切片区间
const range = this._calcSliceRange()
// 检查计算出来的切片范围，是否被当前已经渲染的切片返回包含了
// 如果是，无需更新切片，（如果 forceUpdate，则无论如何都需要重新切片）
let fromThreshold = range.sliceFrom - THRESHOLD
if (fromThreshold < 0) fromThreshold = 0
let toThreshold = range.sliceTo + THRESHOLD
if (toThreshold > MAX) toThreshold = MAX
// 无需强制刷新，且上下两端都没有触达阈值时，无需重新切片
if (!forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {
return
}
// 下面是更新切片的情况
// 在切片区间头部、尾部，追加预渲染的条目
let { sliceFrom, sliceTo } = range
sliceFrom = sliceFrom > COUNT ? sliceFrom - COUNT : 0
sliceTo = sliceTo + COUNT > MAX ? MAX : sliceTo + COUNT
this.sliceFrom = sliceFrom
this.sliceTo = sliceTo
if (forceUpdate) this._doSlice()
}
После использования этой пакетной операции вы можете видеть, что при обычной прокрутке мышью IE также может прокручивать более плавно.
мероприятие
Поскольку DOM виртуального списка необходимо постоянно генерировать и уничтожать, привязывать события непосредственно к элементам списка очень неэффективно.
Поэтому использование прокси-сервера событий стало очень хорошим решением, регистрируя событие на корневом узле компонента, а затем в соответствии сevent.targetЧтобы определить, какой элемент списка вызвал событие, его можно эффективно обработать.
Реализация компонента
import { Component, Vue, Prop, Watch } from 'vue-property-decorator'
import { createSparseRangeList } from './SparseRangeList'
// 列表项数据包裹，data 字段存放原始数据
// 组件所有操作不应该改变 data 的内容，而是修改该包裹对象的属性
class ItemWrapper {
// 原始数据
data: any
// 数据唯一 key
key: any
// 条目高度
// 1. 正数代表已经计算出来的高度
// 2. 0 代表未计算的高度，不显示
// 3. 负数代表需要隐藏的高度，绝对值为已经计算出来的高度，方便取消隐藏
height: number
// 记录是否已经根据实际 DOM 计算过高度
realHeight: boolean
// 条目在当前过滤视图中的序号
viewIndex: number
constructor(data: any, key: any, height: number) {
this.data = data
// 数据的唯一id，是初始化数据时候的序号
// 每次传入的 data 改变，都会重新生成
this.key = key
// 条目的高度缓存
// 1. 用于重建高度存储时快速恢复
// 2. 用于快速通过数据取高度
this.height = height >> 0
this.realHeight = false
// 每次生成 dataView 都刷新
this.viewIndex = -1
}
}
@Component({ name: 'VList' })
export default class VList extends Vue {
[key: string]: any
// 高度存储 不响应式
private itemHeightStore: any
// 组件宽度，不设置则为容器的 100%
@Prop({ type: Number })
private width?: number
// 组件高度，不设置则为容器的 100%
@Prop({ type: Number })
private height?: number
// 传入高度值，固定条目高度
@Prop({ type: Number })
private fixedItemHeight?: number
// 预估元素高度，
// 在高度不确定的列表中，未计算出高度时使用，
// 该值与元素平均高度越相近，则越高效（修正时估算次数越少）
@Prop({ type: Number, default: 30 })
private estimatedItemHeight!: number
// 数据列表
@Prop({ type: Array, default: () => ([]) })
private data!: any[]
// 计算条目高度的方法
@Prop({
type: Function,
default(node: Node, wrappedData: ItemWrapper) {
return (node as HTMLElement).clientHeight
}
})
private itemHeightMethod!: (node: Node, wrappedItem: ItemWrapper) => number
// 数据过滤方法（可以用于外部实现搜索框过滤）
@Prop({ type: Function })
private filterMethod?: (data: any) => boolean
// 数据排序方法（可以用于外部实现数据自定义过滤）
@Prop({ type: Function })
private sortMethod?: (a: any, b: any) => number
// 包裹后的数据列表（必须 freeze，否则大列表性能撑不住）
private wrappedData: ReadonlyArray<ItemWrapper> = Object.freeze(this._wrapData(this.data))
// 真实渲染上屏的数据列表切片
private dataSlice: ReadonlyArray<ItemWrapper> = []
// viewport 宽度
private viewportWidth = this.width || 0
// viewport 高度
private viewportHeight = this.height || 0
// 当前 viewport 中第一条数据的序号
private sliceFrom = 0
// 当前 viewport 中最后一条数据的序号
private sliceTo = 0
// 列表高度
private listHeight = 0
// 检查是否固定高度模式
private get isFixedHeight() {
return this.fixedItemHeight! >= 0
}
// 获取默认条目高度
private get defaultItemHeight() {
return this.isFixedHeight ? this.fixedItemHeight! : this.estimatedItemHeight
}
// 当前筛选条件下的数据列表
// 依赖：wrappedData, filterMethod, sortMethod
private get dataView() {
const { wrappedData, filterMethod, sortMethod } = this
let data = []
if (typeof filterMethod === 'function') {
const len = wrappedData.length
for (let index = 0; index < len; index += 1) {
const item = wrappedData[index]
if (filterMethod(item.data)) {
data.push(item)
}
}
} else {
data = wrappedData.map(i => i)
}
if (typeof sortMethod === 'function') {
data.sort((a, b) => {
return sortMethod(a, b)
})
}
// 重新记录数据在视图中的位置，用于隐藏部分条目时，可以精确计算高度、坐标
const size = data.length
for (let index = 0; index < size; index += 1) {
const wrappedItem = data[index]
wrappedItem.viewIndex = index
}
return Object.freeze(data)
}
// 原始列表数据变化，重新包裹数据
@Watch('data')
private onDataChange(data: any[]) {
this.wrappedData = Object.freeze(this._wrapData(data))
}
// 当前过滤、排序视图变化，重新布局
@Watch('dataView')
private onDataViewChange(wrappedItems: ItemWrapper[]) {
// 重建高度存储
const estimatedItemHeight = this.defaultItemHeight
this.itemHeightStore = createSparseRangeList(wrappedItems.length, estimatedItemHeight)
// 从缓存中快速恢复已计算出高度的条目的高度
wrappedItems.forEach((wrappedItem, index) => {
// 小于零的需要隐藏，所以高度为 0
this.itemHeightStore.setValue(index,
wrappedItem.height > 0 ? wrappedItem.height : 0)
})
// 刷新列表高度
this.updateListHeight()
// 重置滚动位置
// TODO, 锚定元素
const { viewport } = this.$refs as any
if (viewport) viewport.scrollTop = 0
// 重新切片当前 viewport 需要的数据
this._updateSliceRange(true)
this.$emit('data-view-change', this.dataSlice.map((wrappedItem) => wrappedItem.data))
}
private created() {
const estimatedItemHeight = this.defaultItemHeight
this.itemHeightStore = createSparseRangeList(this.dataView.length, estimatedItemHeight)
this.layoutObserver = new MutationObserver(this.redraw.bind(this))
this.childObserver = new MutationObserver((mutations: MutationRecord[]) => {
this._updateHeightWhenItemInserted(mutations)
})
this.$watch(((vm: any) => `${vm.sliceFrom},${vm.sliceTo}`) as any, this._doSlice)
}
private mounted() {
this.redraw()
this.layoutObserver.observe(this.$el, { attributes: true })
// 非固定高度场景，监听子元素插入，提取高度
if (!this.isFixedHeight) {
this.childObserver.observe(this.$refs.content, { childList: true })
}
}
private beforeDestory() {
this.layoutObserver.disconnect()
if (!this.isFixedHeight) {
this.childObserver.disconnect()
}
this.itemHeightStore = null
}
// DOM 结构比较简单，无需 template，直接使用渲染函数输出 VDOM
private render(createElement: any) {
return createElement(
'div', // 组件容器，与外部布局
{
class: 'VList',
style: {
'box-sizing': 'border-box',
display: 'inline-block',
margin: '0',
padding: '0',
width: this.width ? this.width + 'px' : '100%',
height: this.height ? this.height + 'px' : '100%',
}
},
[
createElement(
'div', // 滚动区域的可见范围
{
ref: 'viewport',
class: 'VList_viewport',
style:
'box-sizing:border-box;position:relative;overflow:hidden;width:100%;height:100%;margin:0;padding:0;overflow:auto;overflow-scrolling:touch;',
on: { scroll: this._onScroll }
},
[
createElement(
'div', // 内容容器，内容真实高度由此容器体现
{
class: 'VList_scollable',
ref: 'content',
style: {
'box-sizing': 'border-box',
position: 'relative',
margin: '0',
padding: '0',
height: this.listHeight + 'px'
}
},
// 列表项
this.dataSlice.map((wrappedItem) => {
return createElement(
'div',
{
key: wrappedItem.key,
class: `VList_item VList_item-${wrappedItem.key % 2 === 0 ? 'even' : 'odd'}`,
attrs: {
'data-key': wrappedItem.key
},
style: {
'box-sizing': 'border-box',
'z-index': '1',
position: 'absolute',
right: '0',
bottom: 'auto',
left: '0',
margin: '0',
padding: '0',
cursor: 'default',
// 注：使用 transfrom 有黑屏 bug
// transform: `translate(0, ${top})`
// transform: `translate3d(0, ${top}, 0)`
top: this._top(wrappedItem.viewIndex) + 'px'
}
},
// 将原始数据，key 注入到 slot 里，
// 以便自定义条目内容使用
this.$scopedSlots.default!({
item: wrappedItem.data,
listKey: wrappedItem.key
})
)
})
)
]
)
]
)
}
// 重绘界面，确保列表渲染正确
public redraw() {
const viewport = this.$refs.viewport as HTMLElement
const { clientWidth, clientHeight } = viewport
this.viewportWidth = clientWidth
this.viewportHeight = clientHeight
this.updateListHeight()
this._updateSliceRange(true)
}
// 刷新列表总高度
public updateListHeight() {
const { itemHeightStore } = this
const rangeValues = itemHeightStore.values()
if (!rangeValues.length) {
this.listHeight = 0
return
}
const listHeight = rangeValues.reduce((sum: number, rangeValue: any) => {
const span = rangeValue.end - rangeValue.start + 1
const height = rangeValue.value * span
return sum + height
}, 0)
this.listHeight = listHeight
}
// Dom 插入时候，计算高度，然后
// 批量刷新高度，避免频繁调整列表高度带来性能问题
public batchUpdateHeight(records: Array<{ wrappedItem: ItemWrapper, height: number }>) {
records.forEach(({ wrappedItem, height }) => {
this._updateHeight(wrappedItem, height, true)
})
this.updateListHeight()
this._updateSliceRange()
}
// 通过数据 key，设置对应条目的高度
public updateHeightByKey(key: any, height: number) {
const wrappedItem = this.wrappedData[key]
if (!wrappedItem) return
this._updateHeight(wrappedItem, height)
this.updateListHeight()
this._updateSliceRange()
}
// 通过数据 key，设置对应条目的显示状态
public showByKey(key: any) {
const wrappedItem = this.wrappedData[key]
if (!wrappedItem) return
if (wrappedItem.height <= 0) {
const height = -wrappedItem.height || this.defaultItemHeight
this._updateHeight(wrappedItem, height!)
this.updateListHeight()
this._updateSliceRange()
// 强制重绘
this._doSlice()
}
}
// 通过数据 key，设置对应条目的显示状态
public hideByKey(key: any) {
const wrappedItem = this.wrappedData[key]
if (!wrappedItem) return
if (wrappedItem.height > 0) {
const height = -wrappedItem.height
wrappedItem.height = height
this._updateHeight(wrappedItem, height)
this.updateListHeight()
// 强制重绘
this._updateSliceRange(true)
}
}
// 通过数据 key 列表，设置对应条目的显示状态
public showByKeys(keys: any[]) {
const wrappedItems = keys.map((key) => this.wrappedData[key])
.filter((wrappedItem) => wrappedItem && wrappedItem.height <= 0)
wrappedItems.forEach((wrappedItem) => {
const height = (-wrappedItem.height || this.defaultItemHeight)!
this._updateHeight(wrappedItem, height)
})
this.updateListHeight()
// 强制重绘
this._updateSliceRange(true)
}
// 通过数据 key 列表，设置对应条目的显示状态
public hideByKeys(keys: any[]) {
const wrappedItems = keys.map((key) => this.wrappedData[key])
.filter(wrappedItem => wrappedItem && wrappedItem.height > 0)
wrappedItems.forEach((wrappedItem) => {
// 设置为负数，表示隐藏
const height = -wrappedItem.height
wrappedItem.height = height
this._updateHeight(wrappedItem, height)
})
this.updateListHeight()
// 强制重绘
this._updateSliceRange(true)
}
// 内部方法，计算局部渲染数据切片的起止点
private _calcSliceRange() {
if (!this.dataView.length) {
return { sliceFrom: 0, sliceTo: 0 }
}
// 数据总量
const MAX = this.dataView.length
// 视口上边界
const viewportTop = (this.$refs.viewport as any).scrollTop || 0
// 视口下边界
const viewportBottom = viewportTop + this.viewportHeight
// 预估条目高度
const estimatedItemHeight = this.defaultItemHeight
// 从估算值开始计算起始序号
let sliceFrom = Math.floor(viewportTop / estimatedItemHeight!)
if (sliceFrom > MAX - 1) sliceFrom = MAX - 1
while (sliceFrom >= 0 && sliceFrom <= MAX - 1) {
const itemTop = this._top(sliceFrom)
// 条目顶部相对于 viewport 顶部的偏移
const itemOffset = itemTop - viewportTop
// 1. 该条目距离视口顶部有距离，说明上方还有条目元素需要显示，继续测试上一条
if (itemOffset > 0) {
// 二分法快速估算下一个尝试位置
const diff = itemOffset / estimatedItemHeight!
sliceFrom -= Math.ceil(diff / 2)
continue
}
// 2. 恰好显示该条目的顶部，则该条目为本次视口的首条元素
if (itemOffset === 0) break
// 以下都是 itemOffset < 0
const itemHeight = this._itemHeight(sliceFrom)
// 3. 该条目在顶部露出了一部分，则该条目为本次视口的首条元素
if (itemOffset < itemHeight) break
// 4. 该条目已被滚出去视口，继续测试下一条
// 二分法快速估算下一个尝试位置
const diff = -itemOffset / estimatedItemHeight!
sliceFrom += Math.ceil(diff / 2)
}
// 从估算值开始计算结束序号
let sliceTo = sliceFrom + 1 + Math.floor(this.viewportHeight / estimatedItemHeight!)
if (sliceTo > MAX) sliceTo = MAX
while (sliceTo > sliceFrom && sliceTo <= MAX) {
const itemTop = this._top(sliceTo)
const itemHeight = this._itemHeight(sliceTo)
const itemBottom = itemTop + itemHeight
// 条目底部相对于 viewport 底部的偏移
const itemOffset = itemBottom - viewportBottom
// 1. 该条目的底部距离视口底部有距离，说明下方还有条目元素需要显示，继续测试下一条
if (itemOffset < 0) {
// 二分法快速估算下一个尝试位置
const diff = -itemOffset / estimatedItemHeight!
sliceTo += Math.ceil(diff / 2)
continue
}
// 2. 恰好显示该条目的底部，则该条目为视口中最后一项
if (itemOffset === 0) break
// 3. 该条目在底部被裁剪了一部分，则该条目为本次视口的末项
if (itemOffset < itemHeight) break
// 该条目还未出场，继续测试上一条
// 二分法快速估算下一个尝试位置
const diff = itemOffset / estimatedItemHeight!
sliceTo -= Math.ceil(diff / 2)
}
// slice 的时候，不含 end，所以 + 1
sliceTo += 1
return { sliceFrom, sliceTo }
}
// 上下两端预先批量渲染的项目波动量
// 原理是，每次插入删除都是一个小批量动作，
// 而不是每次只插入一条、销毁一条
// 计算出的局部渲染数据范围，跟上一次计算出来的结果，差距
// 在这个波动量范围内，则不重新切片渲染，用于
// 防止 IE 11 频繁插入内容导致性能压力
private _preRenderingCount() {
// 默认预渲染 2 屏
return Math.ceil(this.viewportHeight / this.defaultItemHeight!) * 2
}
// 滚动到上下方剩下多少个条目时，加载下一批
// 缓解 Macbook & iOS 触摸滚动时的白屏
private _preRenderingThreshold() {
// 默认触达预渲染的一半数量时，加载下一批切片
return Math.floor(this._preRenderingCount() / 2)
}
// 刷新局部渲染数据切片范围
private _updateSliceRange(forceUpdate?: boolean) {
// 上下方额外多渲染的条目波动量
const COUNT = this._preRenderingCount()
// 预渲染触发阈值
const THRESHOLD = this._preRenderingThreshold()
// 数据总量
const MAX = this.dataView.length
// 计算出准确的切片区间
const range = this._calcSliceRange()
// 检查计算出来的切片范围，是否被当前已经渲染的切片返回包含了
// 如果是，无需更新切片，（如果 forceUpdate，则无论如何都需要重新切片）
let fromThreshold = range.sliceFrom - THRESHOLD
if (fromThreshold < 0) fromThreshold = 0
let toThreshold = range.sliceTo + THRESHOLD
if (toThreshold > MAX) toThreshold = MAX
// 无需强制刷新，且上下两端都没有触达阈值时，无需重新切片
if (!forceUpdate && ((this.sliceFrom <= fromThreshold) && (this.sliceTo >= toThreshold))) {
return
}
// 更新切片的情况
// 在切片区间头部、尾部，追加预渲染的条目
let { sliceFrom, sliceTo } = range
sliceFrom = sliceFrom > COUNT ? sliceFrom - COUNT : 0
sliceTo = sliceTo + COUNT > MAX ? MAX : sliceTo + COUNT
this.sliceFrom = sliceFrom
this.sliceTo = sliceTo
if (forceUpdate) this._doSlice()
}
// 当前需要渲染的数据切片
private _doSlice() {
const { dataView, sliceFrom, sliceTo } = this
const slice = dataView.slice(sliceFrom, sliceTo)
.filter((wrappedItem) => wrappedItem.height > 0)
this.dataSlice = Object.freeze(slice)
this.$emit('slice', slice.map((wrappedItem) => wrappedItem.data))
}
// `index` 数据在 dataView 中的 index
private _itemHeight(index: number): number {
return this.itemHeightStore.getValueAt(index)
}
// `index` 数据在 dataView 中的 index
private _top(index: number): number {
if (index === 0) return 0
// 0 ～ 上一项的高度累加
const rangeValues = this.itemHeightStore.intersecting(0, index - 1)
const sumHeight = rangeValues.reduce((sum: number, rangeValue: any) => {
const span = rangeValue.end - rangeValue.start + 1
return sum + rangeValue.value * span
}, 0)
return sumHeight
}
// 包裹原始数据列表
private _wrapData(list: any[]): ItemWrapper[] {
return list.map((item, index) => new ItemWrapper(item, index, this.defaultItemHeight!))
}
// 通过 DOM Node 获取对应的数据
private _getDataByNode(node: Node): ItemWrapper {
return this.wrappedData[(node as any).dataset.key]
}
// 刷新列表项高度
private _updateHeight(wrappedItem: ItemWrapper, height: number, isRealHeight?: boolean) {
height = height >> 0
// 更新结点高度缓存
wrappedItem.height = height
if (isRealHeight) {
wrappedItem.realHeight = true
}
// 如果 wrappedItem 为当前过滤下的项目，
// 则同时刷新高度存储 store
const index = this.dataView.indexOf(wrappedItem)
if (index !== -1) {
// 小于等于零表示折叠不显示，计算高度为零
// 负值存在 wrappedItem 中，用于反折叠时恢复
this.itemHeightStore.setValue(index, height > 0 ? height : 0)
}
}
// 节点插入时，检查是否首次插入，如果是，计算高度并更新对应的 ItemWrapper
private _updateHeightWhenItemInserted(mutations: MutationRecord[]) {
const addedNodes: Node[] = mutations
.map((mutation: MutationRecord) => mutation.addedNodes)
.reduce((result: any, items: NodeList) => {
result.push(...items)
return result
}, [])
const batch: Array<{ wrappedItem: ItemWrapper, height: number }> = []
addedNodes.forEach((node: Node) => {
const wrappedItem = this._getDataByNode(node)
// 如果 wrappedItem 中已经存储了计算过的高度，
// 则直接返回，不访问 clientHeight
// 以避免性能开销（IE 11 中访问 clientHeight 性能非常差）
if (wrappedItem.realHeight) {
return
}
const height = this.itemHeightMethod(node, wrappedItem) >> 0
if (wrappedItem.height !== height) {
batch.push({ wrappedItem, height })
} else {
// 计算出来的高度跟默认值一致，
// 则无需更新，但是设置已经计算状态
// 以便下次可以直接使用缓存
wrappedItem.realHeight = true
}
})
if (batch.length) {
this.batchUpdateHeight(batch)
}
}
// 滚动事件处理器
private _onScroll() {
this._updateSliceRange()
}
}
заявление
После реализации виртуального списка существует множество применений.
- Обычный список. Например, список очень длинная статья.
- компонент формы. Подходят большие таблицы данных.
- компонент дерева. Компонент дерева может быть реализован простой обработкой логики отступа и свертывания нижнего уровня, проверкой связи и т.д.
В некоторых сценариях, когда большой объем данных должен быть загружен за один раз, например, большой древовидный компонент с множественным выбором, трудно удовлетворить требования к производительности без виртуальных списков. Например, компонент дерева в Element UI на процессоре PC i5 7-го поколения имеет 1000 узлов, и для переключения на выделение всех требуется несколько секунд, что ужасно.
В настоящее время, если вы не можете использовать спрос на продукт и клиентов, вы можете рассмотреть возможность создания виртуального списка для этого.
Полный текст готов.