Анализ библиотек с открытым исходным кодом и лучшие практики «длинного списка внешнего интерфейса»

оптимизация производительности

предисловие

Длинный список обычно называют виртуальным списком.Это схема оптимизации, которая отображает только видимые узлы, чтобы избежать зависания страницы при больших объемах данных.

В лонг-листе тоже есть практика разделения по времени, которая используется реже, если интересно, можете почитать.Высокопроизводительный рендеринг 100 000 фрагментов данных (квантование по времени)

Есть два элемента, которые являются более известными передними частями:

  • react-window
  • vue-virtual-scroller

и Ant Design 4virtual-list

В этой статье будут проанализированы эти библиотеки с открытым исходным кодом, проанализирован принцип реализации и оценен каждый показатель, и, наконец, реализован высокодоступный компонент длинного списка.

В основном оценивайте следующие моменты:

  1. Рендеринг: перекомпоновка, стратегия рендеринга и т. д.
  2. Расчет: расчет начальных и конечных элементов и позиций смещения, расчет общей высоты
  3. Функция: адаптивная высота, другое
  4. Надежный: Есть ли ошибка, что мышь не синхронизируется с полосой прокрутки (общая высота увеличивается при расчете, полоса прокрутки будет направлена ​​вверх относительно мыши)

Затем поговорим о стратегии просмотра исходного кода, в основном обратите внимание на следующие моменты:

  1. дом структура
  2. Найдите начальную локацию
  3. Рассчитать расстояние смещения
  4. Рассчитать общую высоту

Начало работы с длинными списками

Если вы не знаете, что такое длинный список, вы можете сначала прочитать эту статью«Передний расширенный» высокопроизводительный рендеринг 100 000 элементов данных (виртуальный список)

Быстрый старт с графиком

Давайте посмотрим, как это делают другие библиотеки с открытым исходным кодом.

vue-virtual-scroller

адрес проекта

Функция: поддержка адаптивной высоты, горизонтальной прокрутки, адаптивной высоты изображения.

оказывать

Структура дом выглядит следующим образом

<!-- position: relative;overflow-y: auto; -->
<div class="vue-recycle-scroller">
  <div class="vue-recycle-scroller__item-wrapper" :style="{ 'minHeight': totalSize + 'px' }">
    <div
        v-for="view of pool"
        :key="view.nr.id"
        :style="{ transform: `translateY(${view.position}px)` }"
        class="vue-recycle-scroller__item-view"
      >
        <slot
          :item="view.item"
          :index="view.nr.index"
          :active="view.nr.used"
        />
      </div>
  </div>
</div>

относительно позиционированный список, состоящий изmin-heightРаспространите обертку для создания полос прокрутки

Каждый элемент списка переводится (translateY), а значение смещения представляет собой накопленную высоту элемента в списке.

осталось немного-9999pxНевидимые элементы, на самом деле это элементы списка кэш-пула, это вУтилизация и повторное использование узловРаздел расскажет о

Структура данных элемента списка:

listItem = {
  // 数据项内容
  item:Object,
  // 非响应式数据
  nr:{
    id,// 唯一标识
    index,// 数据项中的索引
    used: Boolean,// 是否已用来显示在可视区域
    key,// 数据项中的key
    type,// 在对应类型的缓冲池中存取
  }
  // translateY 值
  position: Number,
}

Нет обратного потока (в случае неадаптивной высоты)

браузерБыстрый рендеринг: Элементы списка, которые изменяются во время прокрутки, будут максимально использовать элемент пула кеша и модифицировать translateY, а позиции других элементов списка, которые не изменились, останутся неизменными в структуре dom.

рассчитать

Есть три сценария

① Использовать высоту по умолчанию

В простейшем случае вам нужно установить itemSize

Индекс начального элемента может быть передан через~~(scrollTop / itemSize)получать

общая высота списка =itemSize * itemCount

② Определите поле высоты

itemSize имеет значение null, а высота каждого элемента списка определяется полем высоты в элементе данных.

Поскольку высота всех элементов списка фиксирована, высота и значение смещения каждого элемента вычисляются в начале.

O(n) временная сложность

При этом определяется общая высота списка, которая фиксируется как最后一项的偏移值+高度

При прокрутке, поскольку определяется положение смещения каждого элемента, индекс начального элемента можно искать методом дихотомии.

O(logn) временная сложность

③ Адаптивная высота

Вам необходимо настроить минимальную высоту элемента данных и инициализировать значение высоты и смещения каждого элемента данных на основе этого значения -- размеры

O(n) временная сложность

Общая высота списка最后一项的偏移值+高度

расчет размеров

for (let i = 0, l = items.length; i < l; i++) {
  current = items[i][field] || minItemSize
  accumulator += current
  sizes[i] = { accumulator, size: current }
}

Прокрутите, получите индекс начального элемента путем дихотомии размеров, а индекс конечного элемента - это индекс начального элемента плюс可视高度/最小列高

O(logn) временная сложность

Затем выполните рендеринг узлов, получите фактическую высоту по завершении рендеринга и пересчитайте размеры и общую высоту списка.

O(n) временная сложность

В целом, низкая производительность, есть возможности для оптимизации

[Преимущество] Утилизация и повторное использование узлов

连续滚动(continuous): 前后两次查找的数据范围有重叠，比如第一次为 1~10 第二次为 5~14 或者相反
已使用的列表项(views): 记录已使用项的 Map ，key 为列表项的 key
pool: 页面中所有渲染的列表项，包括未使用的
类型-缓存池 Map (unusedViews): 记录类型和缓存池的 Map
缓存池(unusedPool): 某种类型的缓存池，其中的列表项在页面中偏移位置为 -9999px

Для примера непрерывной прокрутки:

  1. В начале я нашел 1~10, вставил в просмотры, прокрутил и нашел 5~14
  2. Поместите 1~4 в неиспользуемый пул соответствующего типа, установите его как неиспользуемый и удалите из представлений.
  3. Установите исходные 5 ~ 10 элементов как используемые
  4. Когда 11 найдено, посмотрите, есть ли неиспользуемые пулы того же типа, что и 11. Если есть, извлеките его для повторного использования, замените содержимое и позицию смещения, если нет, создайте новое представление и поместите его в пул.

Соответственно, прерывистая прокрутка определяется какпрокручивать быстро, инициализировать пустую карту -- unusedIndex, функция состоит в том, чтобы записать, с какого индекса должен начинаться unusedPool того же типа.

Если в unusedPool есть элементы, используйте его для повторного использования; если тот же тип пула израсходован, addView

чувствовать себя здесьv++Возникла проблема с обработкой

Подобно прокрутке списка в Android, переработка выполняется по типу, а вновь найденные элементы списка будут повторно использовать тот же тип в кеше, что может сократить время компоновки.

Похож на Weexrecycle-list

крепкий

Поскольку высота индикатора выполнения изменяется, возникает ошибка, из-за которой мышь не синхронизируется с полосой прокрутки.

Суммировать

Богатые функции, плохая производительность обработки с точки зрения адаптивной высоты (попробуйте учесть pr), плохая структура проекта и сложность в обслуживании

Не рекомендуется для использования

react-window

Доступны четыре компонента:

  • FixedSizeList
  • FixedSizeGrid
  • VariableSizeList
  • VariableSizeGrid

Адаптивная высота не поддерживается

Сетка не анализируется, FixedSizeList — простейший сценарий фиксированной высоты, практика та же, анализируем непосредственно VariableSizeList

Сперва поговорим об этом, для повторного использования react-window инкапсулирует код слой за слоем, рендер по-прежнему использует createElement... Исходник смотреть очень неудобно, и он по-прежнему пишется в потоке, а редактор выдает разные ошибки.

Не знаю почему, но установка зависимостей не проходит, и локально не запускается, в этот раз я смотрю исходный код напрямую.

оказывать

<div style="{{position: 'relative', height: `${height}px`, overflow: 'auto'}}">
  <div style="{{height: `${totalSize}px`, width: '100%'}}">
    <div style="position: absolute; left: 0px; top: 38px; height: 30px; width: 100%;">
      Row 1
    </div>
    <div style="position: absolute; left: 0px; top: 68px; height: 65px; width: 100%;">
      Row 2
    </div>
    ....
    <div style="position: absolute; left: 0px; top: 133px; height: 70px; width: 100%;">
      Row 3
    </div>
  </div>
</div>

По-прежнему используйте контейнер высоты totalSize для создания индикатора выполнения, и каждый элемент списка смещается абсолютным позиционированием

здесь практичноtransform: translateYЭффект тот же, конечно, я не знаю разницы в производительности при рендеринге.

рассчитать

В соответствии с реализацией этой статьи --Поговорим о реализации внешнего виртуального списка

Кажется, вы неправильно поняли поиск по индексу?

Пусть lastMeasureItem будет самым дальним измеренным элементом,

lastMeasureItem.offset — значение смещения элемента

lastMeasureItem.index — это индекс элемента

Общая высота списка = lastMeasureItem.offset + неизмеряемые элементы * высота по умолчанию

Первоначально прокат, смещение и индекс и кэш прокат начало измерения от 0 через элемент, обновите lastmeasureitem

O(n) временная сложность

Когда значение смещения прокрутки меньшеlastMeasureItem.offsetКогда это означает, что начальный элемент находится в диапазоне от 0 до lastMeasureItem.index.Поскольку значения смещения всех элементов списка в этом диапазоне были рассчитаны, индекс начального элемента можно быстро получить с помощью двух точки.

O(logn)

Когда значение смещения прокрутки меньшеlastMeasureItem.offset, затем сlastMeasureItem.indexНачать измерение и кэшировать смещение и индекс прокручиваемого элемента, обновить lastMeasureItem

O(n) временная сложность

Наблюдайте за LastMeasureItem.index. Если вы измените, общая высота списка будет следующей.

Демо

Эта схема имеет два недостатка:

  • Плохое расширение, невозможность адаптивной высоты
  • Предыдущая прокрутка занимает много времени, а неиспользованные тоже учитываются.

крепкий

Поскольку высота индикатора выполнения изменяется, возникает ошибка, из-за которой мышь не синхронизируется с полосой прокрутки.

Суммировать

Не поддерживает адаптивную высоту, производительность не очень хорошая, не лучший выбор для длинных списков реагирования

Если это полезно для Grid, его можно использовать

virtual-list

адрес проекта

Тот, у кого самый высокий общий балл в анализе

Поддержка адаптивной высоты, поддержка анимационных эффектов, поддержка восстановления положения прокрутки

оказывать

  <!-- 用户可见的容器高度可能只有 300px -->
  <div
    class="container"
    style="width: 200px; height: 300px;"
    @scroll.passive="handleScroll"
  >
    <!-- 总的列表 div ，用于撑起列表的高度 -->
    <div
      class="total-list"
      :style="{
        height: `${itemHeight * data.length}px`,
      }"
    >
      <div
        class="visible-list"
        :style="{
        transform: `translateY(${topHeight}px)`,
      }"
      >
        <div
          v-for="item in visibleList"
          :key="item.id"
          class="visible-list-item"
          :style="{
          height: `${itemHeight}px`,
        }"
        >{{ item.value }}</div>
      </div>
    </div>

    <!-- 此处只需渲染可见列表即可，无需渲染全部数据 -->

  </div>

В отличие от приведенной выше схемы, здесь создается контейнер total-list, и к этому контейнеру напрямую применяется смещение translateY.

рассчитать

Общая высота всегда фиксирована и равна列表项个数(itemCount) * 列表项最小高度(itemHeight)

Логика обработки следующая:

  1. Прокрутите, определите расположение элементов, а также начальные и конечные элементы.
  2. Отображение начального и конечного элементов списка
  3. После рендеринга элемента списка вычислите и отрегулируйте положение смещения начального элемента.
  4. перерисовать

Примечание. Рендеринг здесь означает работу с домом и еще не достиг фактической стадии рендеринга в браузере.

Основная идея заключается в том, что элементы списка любой высоты занимают один и тот же диапазон полосы прокрутки.

① Определите элемент позиционирования, а также начальный и конечный элементы.

Элемент позиционирования соответствует положению полосы прокрутки, что можно понимать как элемент списка, на который указывает полоса прокрутки в горизонтальном направлении.

Когда полоса прокрутки равна 0, она указывает на 0-й элемент, а элемент позиционирования в это время является 0-м элементом.

Когда полоса прокрутки имеет максимальное значение, она указывает на последний элемент, а элемент позиционирования является последним элементом в это время.

const itemCount = this.data.length
const scrollTopMax = scrollHeight - clientHeight
/** 进度条滚动百分比 */
const scrollPtg = scrollTop / scrollTopMax
/** 确定定位项 */
const itemIndex = Math.floor(scrollPtg * itemCount);
/** 可见列表项个数 = 可见容器高度 / 每个列表项高度 ，记得向上取整 */
const visibleCount = Math.ceil(this.$el.clientHeight / this.itemHeight)
/** 确定起始项和结束项 */
const startIndex = Math.max(0, itemIndex - Math.ceil(scrollPtg * visibleCount))
const endIndex = Math.min(itemCount - 1, itemIndex + Math.ceil((1 - scrollPtg) * visibleCount))

② Элементы списка рендеринга

Элементы списка рендеринга из startIndex ~ endIndex

③ Отрегулируйте смещение

После отображения элемента списка активируйте обратный вызов обновления.

Получить и подсчитать фактическую общую высоту s2iHeight элементов списка startIndex ~ itemIndex

Вычислите высоту смещения начального элемента startItemTop следующим образом:

const startItemTop = 定位项绝对高度(itemAbsoluteTop) - 起始项至定位项的高度(s2iHeight)
const itemAbsoluteTop = scrollTop + 定位项相对视口高度(itemRelativeTop)
const itemRelativeTop = 滚动过的视口高度(scrollPtg * clientHeight) - 定位项偏移高度(itemOffsetPtg * itemHeight)

как показано на рисунке:

крепкий

Поскольку общая высота фиксирована, нет проблем с рассинхронизацией мыши и полос прокрутки.

Суммировать

Отличная производительность, начальную и конечную позиции можно определить с помощью нескольких математических формул (еще есть место для оптимизации)

Если вам нужно адаптировать высоту, вам нужно выполнить два рендера, в противном случае положение смещения может быть рассчитано в первом рендере.

В настоящее времяТолькоРешение, которое не вызывает проблемы рассинхронизации мыши и полос прокрутки.

Сильная масштабируемость, в конце концов, это один из основных компонентов Ant Design 4.

Реагировать на длинный список предпочтительных решений

Vue может попытаться построить колесо

Другие варианты лечения

Этот раздел предназначен для некоторых других решений для обработки длинных списков, в основном в разнице между поиском начального элемента и высотой списка обновления.

Появятся несколько упомянутых здесь опций.Мышь и полоса прокрутки не синхронизированыЭта проблема

① Последовательный поиск, общая высота обновления разницы

Решение с низкой производительностью

Определите массив itemHeightRecord для записи фактической высоты элемента списка, которая может быть высотой, рассчитанной адаптивно, или высотой, рассчитанной методом определения высоты.

В начале общая высота списка = количество элементов списка * высота по умолчанию

Чтобы найти начальный элемент, поскольку нет записанного значения смещения, о нем можно судить только по последовательному стеку.Есть значение в itemHeightRecord, и высота по умолчанию используется, если нет значения.

Временная сложность O (n)

Визуализирует элемент списка и обновляет разницу между полученной высотой и значением по умолчанию дообщая высота спискаи присвойте значение itemHeightRecord

Недостаток: эффективность поиска стартового предмета слишком низкая.

② Двоичный поиск, последовательное обновление значения смещения

Идея исходит из«Передний расширенный» высокопроизводительный рендеринг 100 000 элементов данных (виртуальный список)и оптимизируйте значение смещения обновления

Вам необходимо настроить минимальную высоту элемента данных и инициализировать значение высоты и смещения каждого элемента данных на основе этого значения -- размеры

общая высота списка =sizes[length-1].offset + sizes[length-1].height

Найдите начальные предметы и разделите по размерам

Временная сложность O(logn)

Отрисовывает элементы списка (при условии, что есть m элементов) и заменяет высоту в размерах полученной высотой, а также обновляет разницу между высотой и значением по умолчанию до смещения каждого последующего элемента.

Временная сложность O (n)

Подобно адаптивной обработке высоты vue-virtual-scroller, за исключением того, что нам нужно только начать обработку с начального элемента.

Онлайн-демонстрация

Цитата из «Front-end Advanced» высокопроизводительного рендеринга 100 000 фрагментов данных (виртуальный список), временная сложность обновления значения смещения составляет O (n * m).

Недостаток: требуется много времени для обновления размеров

③ Значение смещения обновления оптимизации древовидного массива

Решение, которое я придумал, может выполнить как запрос, так и обновлениеO(logn)временная сложность

не виделvirtual-listЯ думал, что это было лучшим решением раньше

С точки зрения эффективности они похожи, но эта схема будет иметьМышь и полоса прокрутки не синхронизированыЭта проблема

Сначала мы устанавливаем модель данных.Список высоты элементов списка представляет собой положительный массив nums длины len.Есть две операции:

  1. Обновить значение элемента в массиве
  2. Найдите наименьшее n, сумма первых n элементов больше или равна целевому значению target , 1

Очевидно, что это проблема шаблона массива дерева, обе операции имеют временную сложность O (logn), шаблон может ссылаться на то, что я написалBinaryIndexedTree

Принцип работы с древовидным массивом см. в статье --Двоичные индексированные деревья

Предусмотрено несколько способов

function findGe(target) {} //找到最小的一个n，其前n项和大于等于 target
function update (i, val) {} // 第 i 项增加差值val, 1<=i<=len
function prefixSum (n = this.tree.length - 1) {} //计算前 n 项的和 , 1<=n<=len

Чтобы найти начальный элемент, вы можете использовать findGe, чтобы найти позицию смещения начального элемента и общую высоту списка, вы можете использовать prefixSum, а чтобы обновить значение смещения, используйте update

Эффект теста: время расчета для обработки прокрутки данных 10 Вт составляет около 1 мс.

Заинтересованные могут увидеть мою библиотеку с открытым исходным кодомvirtual-list-demo

Оптимизация перекомпоновки

Высота списка видимой области вообще неизменна, и каждый раз передавать ее не нужно$el.clientHeightПолучите (вызовет перекомпоновку), измените его при изменении размера

Если это адаптивная высота, то эта операция необязательна.

Комплексная реализация

Изначально я планировал написать отдельный раздел и в итоге решил использовать метод проектирования виртуального списка.

элемент списка занимаетRender Propsформе используйте cloneElement для создания фактического элемента списка.

Будь то адаптивная высота или фиксированная высота, она настраивается с помощью параметров, и только один компонент предоставляется извне.

Перспектива

Тест на совместимость с браузером

Я тестировал только хром в своем личном плане и не тестировал другие браузеры.Когда я посмотрел на библиотеку с открытым исходным кодом, я увидел, что она выполнила некоторую обработку совместимости.

Например, проблема с белым экраном прокрутки в Firefox, проблема с прокруткой Safari может иметь отрицательную проблему, проблема с мобильной станцией

Объем ограничен, и это выходит за рамки этой статьи.Предложение состоит в том, чтобы как можно больше использовать библиотеки с открытым исходным кодом в производственной среде.

Адаптивная высота изображения

Если высота элемента списка зависит от высоты изображения, из-за медленной загрузки изображения реальная высота списка не может быть получена в конце первоначального рендеринга (в жизненном цикле обновления), и вычисление необходимо подождать для загрузки изображения.

Конкретный метод заключается в использовании API ResizeObserver, но эта совместимость немного проблематична,

Это действительно полезно в vue-virtual-scroller, вы можете обратиться к нему, если вам интересно

В ответ на события клавиатуры

Чтобы переключать элементы списка с помощью клавиш со стрелками, вам нужно перехватить события клавиатуры по умолчанию и назначить scrollTop

Это скорее выбор на основе длинного списка, который будет использоваться в дереве и будет использоваться позже.

исходный адрес, если интересно, поставь звезду~

Ссылаться на

  1. virtual-list-demo
  2. «Передний расширенный» высокопроизводительный рендеринг 100 000 элементов данных (виртуальный список)
  3. Поговорим о реализации внешнего виртуального списка
Категории