Оптимизация фильтров

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

Базовая реализация фильтрации в библиотеке опирается на простое сравнение подстрок. Однако при росте списка до нескольких тысяч элементов основным узким местом становится не DOM-рендеринг, а именно CPU-стоимость фильтрации.

Классическая проблема:

  • каждая клавиша запускает полный проход по массиву;
  • для каждого элемента выполняется нормализация строки;
  • создаются временные строки;
  • возможны регулярные выражения или toLowerCase() в цикле.

Даже O(n) без оптимизаций превращается в ощутимую задержку при высокой частоте ввода.

Нормализация данных вне цикла

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

Типичная ошибка:

list.filter(item =>
  item.toLowerCase().includes(input.toLowerCase())
);

Проблема здесь в том, что toLowerCase() вызывается для каждого элемента при каждом вводе.

Оптимизированный подход:

const prepared = list.map(item => ({
  raw: item,
  norm: item.toLowerCase()
}));

Фильтрация:

const q = input.toLowerCase();

prepared.filter(item =>
  item.norm.includes(q)
);

Такой подход убирает повторную аллокацию строк и уменьшает нагрузку на GC.

Использование префиксных проверок вместо includes

includes() имеет более высокую стоимость по сравнению с startsWith(), так как выполняет поиск подстроки по всей длине строки.

Если сценарий допускает ограничение поиска префиксом, производительность возрастает существенно:

item.norm.startsWith(q)

Особенно это важно для автодополнения, где пользователь чаще вводит начало слова, а не его середину.

Кэширование результатов фильтрации

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

  • "a" → результат A
  • "ap" → результат B (частично пересекается с A)
  • "app" → результат C

Можно использовать инкрементальный кэш:

const cache = new Map();

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

  const result = prepared.filter(x => x.norm.startsWith(query));
  cache.set(query, result);

  return result;
}

Важно ограничивать размер кэша, иначе он начнёт деградировать по памяти:

if (cache.size > 100) {
  cache.clear();
}

Сужение множества кандидатов на раннем этапе

Эффективная стратегия — уменьшать список до фильтрации.

Вместо:

весь список → фильтр → результат

используется:

индекс → кандидаты → фильтр → результат

Практические варианты:

Группировка по первой букве

const index = new Map();

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

Фильтрация:

const pool = index.get(query[0]) || [];
pool.filter(x => x.norm.startsWith(query));

Это уменьшает сложность с O(n) до O(k), где k — размер подмножества.

Ограничение длины выборки (early cutoff)

Отрисовка большого числа элементов в dropdown часто дороже фильтрации.

Практика:

  • ограничение до 10–20 элементов;
  • прекращение фильтрации после достижения лимита.
const result = [];

for (const item of pool) {
  if (item.norm.startsWith(q)) {
    result.push(item);
    if (result.length === 15) break;
  }
}

Это снижает не только CPU, но и стоимость layout/reflow.

Сортировка как отдельная стадия

Сортировка внутри фильтрации увеличивает стоимость до O(n log n), что недопустимо на каждом input.

Оптимизация:

  • фильтрация → минимальный набор → сортировка только результата.
const filtered = pool.filter(x => x.norm.startsWith(q));

filtered.sort((a, b) =>
  a.norm.length - b.norm.length
);

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

Минимизация работы с DOM

Хотя фильтрация — CPU-bound операция, рендеринг списка часто становится вторым узким местом.

Основные принципы:

  • не пересоздавать элементы;
  • переиспользовать DOM-узлы;
  • обновлять только текстовое содержимое.

Пример паттерна:

function render(list) {
  for (let i = 0; i < items.length; i++) {
    const el = items[i];
    if (list[i]) {
      el.textContent = list[i].raw;
      el.style.display = "";
    } else {
      el.style.display = "none";
    }
  }
}

Ленивая фильтрация (lazy evaluation)

Вместо полного вычисления результата можно использовать генератор:

function* filterGen(pool, q) {
  for (const item of pool) {
    if (item.norm.startsWith(q)) {
      yield item;
    }
  }
}

И собирать только необходимое количество:

const result = [];
for (const x of filterGen(pool, q)) {
  result.push(x);
  if (result.length === 10) break;
}

Это снижает нагрузку при частых коротких запросах.

Уменьшение стоимости строковых операций

Строковые операции часто становятся скрытым bottleneck:

  • toLowerCase()
  • normalize()
  • регулярные выражения

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

  • хранение нормализованных строк заранее;
  • отказ от regex в горячем пути;
  • использование простых сравнений.

Пример замены regex:

// хуже
/^abc/i.test(str)

// лучше
str.toLowerCase().startsWith("abc")

Асинхронное вынос вычислений

При больших списках (>50k элементов) фильтрация может блокировать UI.

Решение — перенос вычислений в Web Worker:

worker.postMessage({ list: prepared, query });

Worker:

onmess age = (e) => {
  const { list, query } = e.data;

  const result = list.filter(x =>
    x.norm.startsWith(query)
  );

  postMessage(result);
};

Это полностью убирает блокировку основного потока.

Предсказуемость фильтрации и UX-ограничения

Производительность фильтров тесно связана с UX-решениями:

  • сокращение числа вариантов;
  • приоритет точных совпадений;
  • ранний выход из цикла;
  • отказ от сложной fuzzy-логики в реальном времени.

Чем проще функция фильтрации, тем стабильнее задержка отклика, а значит — более ровный ввод без скачков.

Оглавление