Оптимизация больших списков

Awesomplete изначально проектировалась как лёгкая клиентская библиотека автодополнения, ориентированная на небольшие и средние списки. При увеличении объёма данных до десятков тысяч элементов начинают проявляться ограничения, связанные с линейной фильтрацией, DOM-рендерингом и синхронной обработкой событий ввода.

Ключевым фактором становится то, что стандартный алгоритм поиска выполняет последовательный проход по массиву list, применяя функцию фильтрации к каждому элементу. Это приводит к сложности O(n) на каждый ввод символа.

Ограничение объёма отображаемых результатов

Встроенный параметр maxItems напрямую влияет не только на UX, но и на производительность. Чем меньше элементов отображается, тем быстрее происходит:

  • построение DOM-списка
  • вычисление позиций
  • обновление aria-атрибутов
  • перерисовка выпадающего блока

Практическая оптимизация для больших списков начинается с жёсткого ограничения количества отображаемых подсказок:

new Awesomplete(input, {
  maxItems: 8
});

Даже при наличии 50 000 элементов в источнике данных, итоговый DOM будет содержать фиксированное малое число узлов.

Предварительная нормализация данных

Существенная часть времени тратится на повторные операции приведения строк к одному формату. Часто используется toLowerCase() при каждом вводе символа, что создаёт лишние вычисления.

Оптимизация заключается в предварительной нормализации списка:

const data = rawData.map(item => ({
  label: item,
  value: item,
  norm: item.toLowerCase()
}));

Далее фильтрация выполняется по уже подготовленному полю:

filter: Awesomplete.FILTER_CONTAINS,
item: function (text, input) {
  return data.filter(d => d.norm.includes(input.toLowerCase()));
}

Однако даже этот подход не устраняет O(n), но снижает стоимость каждой операции.

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

Стандартный фильтр Awesomplete ориентирован на универсальность, а не на масштабируемость. При больших объёмах данных эффективнее полностью заменить механизм фильтрации.

Индексирование по первым символам

Простейшая оптимизация — создание префиксного индекса:

const index = new Map();

for (const item of data) {
  const key = item.norm[0];
  if (!index.has(key)) index.set(key, []);
  index.get(key).push(item);
}

Фильтрация сокращается до работы с подмножеством:

function search(input) {
  const key = input[0].toLowerCase();
  return (index.get(key) || []).filter(i =>
    i.norm.includes(input.toLowerCase())
  );
}

Таким образом уменьшается размер проверяемого массива в десятки раз.

Ограничение частоты обработки ввода

Каждое нажатие клавиши вызывает пересчёт списка. При быстром вводе это приводит к избыточным вычислениям.

Решение — дебаунсинг обработчика:

function debounce(fn, delay) {
  let t;
  return function (...args) {
    clearTimeout(t);
    t = setTimeout(() => fn.apply(this, args), delay);
  };
}

input.addEventListener("input", debounce(() => {
  awesomplete.evaluate();
}, 120));

Задержка 100–150 мс снижает нагрузку без заметной потери отзывчивости интерфейса.

Использование серверной фильтрации

При объёмах свыше 100 000 элементов клиентская фильтрация становится нецелесообразной. В таких случаях список не передаётся целиком, а запрашивается частями.

input.addEventListener("input", async function () {
  const res = await fetch(`/search?q=${this.value}`);
  const items = await res.json();

  awesomplete.list = items;
  awesomplete.evaluate();
});

Серверная сторона может использовать специализированные структуры:

  • B-деревья
  • полнотекстовые индексы
  • trie
  • поисковые движки (Elasticsearch, Meilisearch)

Минимизация стоимости DOM-операций

Основное узкое место после фильтрации — создание элементов списка <li>.

Оптимизация достигается за счёт:

  • ограничения maxItems
  • переиспользования экземпляра Awesomplete вместо пересоздания
  • минимизации HTML внутри элементов

Пример упрощённого item-render:

item: function (text, input) {
  const li = document.createElement("li");
  li.textContent = text;
  return li;
}

Использование innerHTML с подсветкой совпадений следует избегать при больших списках, так как это добавляет лишние парсинг-операции.

Кэширование результатов поиска

При повторяющихся запросах (например, при стирании символов) целесообразно использовать кэш:

const cache = new Map();

function search(query) {
  if (cache.has(query)) return cache.get(query);

  const result = data.filter(d =>
    d.norm.includes(query.toLowerCase())
  );

  cache.set(query, result);
  return result;
}

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

Использование Web Workers для разгрузки основного потока

При больших объёмах данных фильтрация может блокировать UI-поток. Перенос вычислений в Web Worker устраняет зависания интерфейса.

Основной поток:

const worker = new Worker("searchWorker.js");

input.addEventListener("input", function () {
  worker.postMessage(this.value);
});

worker.onmess age = function (e) {
  awesomplete.list = e.data;
  awesomplete.evaluate();
};

Worker:

self.onmess age = function (e) {
  const query = e.data.toLowerCase();
  const result = data.filter(item =>
    item.norm.includes(query)
  );

  self.postMessage(result);
};

Предфильтрация и сегментация данных

Для статических наборов данных эффективным является разбиение списка на сегменты:

  • по буквам
  • по категориям
  • по языковым группам
  • по частоте использования

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

Снижение стоимости сортировки

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

Оптимизация заключается в:

  • отключении сортировки (sort: false)
  • использовании заранее отсортированных структур
  • переходе к приоритетным спискам
new Awesomplete(input, {
  sort: false
});

Итеративная стратегия масштабирования

При росте объёма данных производительность поддерживается не одной оптимизацией, а комбинацией подходов:

  • ограничение maxItems
  • префиксные индексы
  • дебаунсинг ввода
  • кэширование запросов
  • серверная фильтрация
  • Web Workers для тяжёлых вычислений

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

Оглавление