Книга продолжается выше, в предыдущемРасскажите о длинных списках во фронтенд-разработкеВ статье автор представляет список «рендеринга видимой области» и пишет упрощенный пример, чтобы показать, как этого добиться. Такие списки обычно называются виртуальными списками, и в этой статье мы будем использовать термин «виртуальные списки». В этой статье автор шаг за шагом усилит упрощенный пример из предыдущей статьи до относительно общего и высокопроизводительного компонента виртуального списка, чтобы прояснить идеи реализации виртуального списка. Вам не нужно читать предыдущую статью, чтобы прочитать эту статью, но код реализован с использованием Vue.js, поэтому вам нужно иметь Опыт работы с Vue.js. Кроме того, предоставляется JSFiddle для каждого шага.Если вы что-то не понимаете, рекомендуется запускать и отлаживать онлайн, изменяя JSFiddle.
Реализовать идеи
Прежде чем объяснять следующее содержание, давайте дадим простое определение виртуального списка.
Из-за больших затрат времени на создание и визуализацию элементов DOM в случае больших данных время, необходимое для визуализации всего списка, неприемлемо. Одним из решений является рендеринг только «видимой области» в любом случае, что может обеспечить чрезвычайно высокую начальную производительность рендеринга.
Виртуальный список относится к списку «рендеринга видимой области», и в основном это две важные концепции:
- Прокручиваемая область: если имеется 1000 элементов данных и высота каждого элемента списка равна 30, тогда высота прокручиваемой области составляет 1000 * 30. Когда пользователь изменяет текущее значение прокрутки полосы прокрутки списка, это приводит к изменению содержимого видимой области.
- Видимая область: например, высота списка составляет 300, правая сторона вертикальная полоса прокрутки для прокрутки, затем визуально наблюдаемая область является видимой областью.
Реализация виртуального списка заключается в обработке изменения видимой области после прокрутки полосы прокрутки. Конкретные шаги заключаются в следующем:
- Вычислить startIndex начальных данных текущей видимой области
- Вычислить endIndex конечных данных текущей видимой области
- Рассчитать данные текущей видимой области и отобразить их на странице
- Вычислить позицию смещения startOffset данных, соответствующих startIndex во всем списке, и установить его в список
Для понимания вышеуказанных шагов рекомендуется обратиться к следующему рисунку:
Простейший пример
В этой главе описывается, как превратить описанные выше шаги в код и заставить эту логику работать в браузере.
Чтобы сделать этот пример достаточно простым, сделана настройка: высота каждого элемента списка составляет 30 пикселей. Согласно этому соглашению, основной код JavaScript не превышает 10 строк, но рендеринг и обновление видимой области могут быть реализованы полностью.
Первое, что нам нужно рассмотреть, это как реализовать HTML и CSS виртуального списка, добавив следующие стили:
- Элементы списка (.list-view) используют относительное позиционирование
- Используйте невидимый элемент (.list-view-phantom), чтобы удерживать список, чтобы отображалась полоса прокрутки списка.
- Видимые элементы списка (.list-view-content) используют абсолютное позиционирование, где слева, справа, сверху установлено значение 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);
}
}
}
- Визуализация данных видимой области выполняется Vue.js с использованием элементов массива visibleData.
- Логикой обновления виртуального списка является метод 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 是为了更好的性能）
}
- Чтобы полоса прокрутки правильно отображалась в виртуальном списке, вычисляемое свойство contentHeight Vue.js используется для вычисления реальной высоты области прокрутки.
Простейшая реализация этого может быть выполнена с помощьюздесьЗапуск онлайн, рекомендуется внести некоторые изменения в код и затем запускать, углублять понимание вышеизложенного.
убрать ограничения по высоте
В простейшей реализации есть ограничение, что все элементы имеют одинаковую высоту, если это ограничение нарушено, как реализовать код?
В примере используется свойство itemHeight для определения высоты элемента списка. Есть два варианта достижения динамической высоты элемента списка:
- Добавьте реквизит типа массива, высота каждого элемента списка получается по индексу
- Добавьте метод для получения высоты элемента списка, передайте элемент и индекс этому методу и верните высоту соответствующего элемента списка.
Очевидно, что второе решение является более гибким, поэтому добавляется свойство itemSizeGetter для получения высоты каждого элемента списка.
- Добавьте свойство itemSizeGetter, код выглядит следующим образом:
itemSizeGetter: {
type: Function
}
- Поскольку высота каждой строки разная, необходимо обновить алгоритм 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;
}
- В предыдущем примере для вычисления начального и конечного индексов а-региона требуется только несколько простых вычислений с использованием 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;
}
- Таким же образом элемент списка тоже можно просто вычислить по индексу перед вершиной в списке.Теперь нам нужно добавить метод для вычисления.Код реализации такой:
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
};
}
- Метод 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 будет вызываться многократно во время первоначального обновления рендеринга и прокрутки, а производительность не идеальна. Чтобы оптимизировать эту производительность, необходимо кэшировать информацию о размере и смещении и получать результаты непосредственно из кэша в следующий раз.
В нормальных условиях прокрутка пользователем начинается сверху и непрерывна. Можно применить очень простую стратегию кэширования для записи индекса последнего вычисленного размера и смещения.
- Назовите эту переменную lastMeasuredIndex, значение по умолчанию равно -1; переменная, в которой хранится кэшированный результат, называется sizeAndOffsetCahce, типом является объект, а код реализации выглядит следующим образом:
data() {
return {
lastMeasuredIndex: -1,
startIndex: 0,
sizeAndOffsetCahce: {},
...
};
}
- Результат вычисления высоты элемента кэшированного списка в основном заключается в изменении метода 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];
}
- В методе 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
Если вы добавите строку console.log в itemSizeGetter, вы обнаружите, что contentHeight будет выполнять itemSizeGetter всех элементов списка в первый раз при первом отображении.
Чтобы решить эту проблему, необходимо ввести еще одно свойство оцениваемого размера элемента. Смысл этого свойства в том, чтобы сделать оценку для тех элементов, высота которых не была рассчитана, тогда contentHeight равен высоте кэшированного элемента списка и + количество некешированных элементов списка * предполагаемыйItemSize.
- Во-первых, необходимо увеличить атрибут компонента, значение по умолчанию равно 30, следующим образом:
estimatedItemSize: {
type: Number,
default: 30
}
- Поскольку вам нужно знать сумму высот элементов списка, высота которых была рассчитана, вам нужно добавить метод getLastMeasuredSizeAndOffset, код выглядит следующим образом:
getLastMeasuredSizeAndOffset() {
return this.lastMeasuredIndex >= 0 ? this.sizeAndOffsetCahce[this.lastMeasuredIndex] : { offset: 0, size: 0 };
}
- Модифицированный код по вышеописанному алгоритму выглядит следующим образом:
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 может быть передана черезздесьЗапустив онлайн, вы можете добавить console.log к свойству itemSizeGetter, чтобы увидеть, как работает itemSizeGetter.
Оптимизация производительности поиска для кешированных результатов
Используемый кешированный виртуальный список на самом деле имеет место для оптимизации, например, метод findNearestItemIndex для поиска состоит в том, чтобы найти порядок, временная сложность которого составляет O (N). На самом деле элементы списка результатов представляют собой естественный и упорядоченный массив, бинарный поиск можно использовать для оптимизации производительности кэшированных результатов поиска, временная сложность снижается до O (lgN).
- Добавляем в компонент метод 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, можно подумать, почему такая логика.
- Измените метод 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;
}
Реализация с использованием бинарного поиска может быть выполнена с помощьюздесьЗапуск онлайн ничем не отличается от предыдущего примера по эффекту.
Оптимизирована производительность поиска для некешированных результатов
Поиск некэшированных результатов по-прежнему является последовательным поиском.Есть две идеи оптимизации поиска некэшированных результатов:
- Найдите количество нескольких элементов за раз, разумное значение — contentHeight / предполагаемый размер, найдите индекс, который превышает ваши собственные результаты поиска, а затем используйте двоичный поиск.
- Найдите по экспоненциальному числу, например 1, 2, 4, 8, 16, 32... чтобы найти диапазон, затем используйте двоичный поиск
Автор выбрал второй путь, название этого алгоритма поискаExponential Search, процесс поиска этого алгоритма может относиться к следующему рисунку:
- Добавьте метод 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);
}
Этот алгоритм немного отличается от стандартного экспоненциального поиска, главное отличие заключается не в том, чтобы искать из заголовка, а начиная с местоположения LastMeasureDex.
- Измените метод 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, чтобы наблюдать за процессом выполнения поиска.
использованная литература
В процессе написания этой статьи автор ссылался на множество проектов с открытым исходным кодом, а также ссылался на множество статей, из которых мне очень помогли следующие:
напиши в конце
Если вам интересно узнать, как реализовать виртуальный список, я надеюсь, что эта статья поможет вам.
Для виртуального списка статических данных оптимизации, которые можно выполнить, в основном описаны в этой статье. Если вам все еще очень интересна эта тема, вы можете попробовать добавить эти две функции в виртуальный список:
- Динамически обновлять высоту элемента списка на основе результата рендеринга
- Недействительный кеш после обновления данных и максимально сведите к минимуму объем кеша аннулирования.
Спасибо за ваше терпение, чтобы прочитать эту статью, если в статье есть какие-либо ошибки или если у вас есть какие-либо вопросы, пожалуйста, оставьте сообщение прямо в области комментариев к статье.