Девлог #17 — Швидкий пошук і фільтрація за категоріями для…

250+

проіндексованих симуляцій

<5 мс

затримка пошуку

18 КБ

пошуковий індекс у gzip

залежностей

Проблема: 250 елементів у сітці

Початкова головна сторінка показувала всі симуляції в адаптивній сітці — прийнятно при 50, ще стерпно при 100, але неможливо орієнтуватися при 250. Аналітика підтвердила проблему: користувачі, що приходили через пошук, потрапляли на конкретні сторінки симуляцій, а от ті, хто потрапляв на головну сторінку, погортали кілька секунд і йшли геть.

Нам були потрібні пошук і фільтрація. Обмеження: жодного сервера, жодного кроку збірки, жодного зовнішнього пошукового сервісу. Усе мало працювати в браузері зі статичного JSON-файлу.

Крок 1 — JSON-файл пошукового індексу

Python-скрипт обходить кожну директорію симуляції, зчитує метадані з кожного файлу index.html (заголовок, опис, теги категорій, ключові слова) і формує компактний search-index.json:

          // search-index.json (скорочено)
          [ {
          "id": "double-slit",
          "title":
          "Double-Slit Experiment",
          "desc":
          "Quantum wave-particle duality...",
          "cats": ["quantum",
          "optics"], "tags":
          ["interference",
          "wave", "photon"],
          "difficulty":
          "intermediate"
          }, ... ]
        

Повний індекс для 250 симуляцій важить 142 КБ у нестисненому вигляді, 18 КБ після gzip — значно нижче порогу браузерного HTTP-кешу для миттєвого завантаження при повторному відвідуванні.

Крок 2 — Інвертований індекс для повнотекстового пошуку

Звичайне лінійне сканування масиву з 250 елементів на кожне натискання клавіші було б достатньо швидким (250 об'єктів — тривіальне навантаження для процесора), але нам були потрібні префіксне зіставлення та ранжовані результати. Інвертований індекс зіставляє кожен токен-слово зі списком ID документів, що його містять:

          function
          buildInvertedIndex(docs) {
          const index =
          new Map();
          // токен → Set з ID документів
          for (const doc
          of docs) {
          const tokens =
          tokenise(doc.title +
          ' ' + doc.desc +
          ' ' + doc.tags.join(' ')); for (const tok
          of tokens) {
          if (!index.has(tok)) index.set(tok,
          new Set()); index.get(tok).add(doc.id); } }
          return index; }

          function
          tokenise(text) {
          return text .toLowerCase() .replace(/[^a-z0-9 ]/g, ' ') .split(/\s+/) .filter(t => t.length > 2);
          // ігноруємо стоп-слова
          }
        

Крок 3 — Дерево (trie) для префіксного зіставлення

Користувач вводить «fluid» і очікує побачити «fluid dynamics», «SPH fluid» і «microfluid». Інвертований індекс зіставляє лише точні токени. Trie (префіксне дерево) вирішує цю проблему: кожен вузол представляє один символ; усі шляхи від кореня до листа утворюють повний токен. Пошук усіх слів, що починаються з «flu», виконується за O(довжина_префікса) — константно відносно розміру бібліотеки.

          class Trie {
          constructor() {
          this.root = {}; }

          insert(word, docId) {
          let node = this.root;
          for (const ch
          of word) {
          if (!node[ch]) node[ch] = { _ids:
          new Set() }; node = node[ch];
          node._ids.add(docId);
          // поширюємо ID вниз по кожному вузлу-префіксу
          } }

          search(prefix) {
          let node = this.root;
          for (const ch
          of prefix) {
          if (!node[ch]) return
          new Set(); node = node[ch]; }
          return node._ids;
          // усі документи, що містять слово з цим префіксом
          } }
        

Крок 4 — Мультитегова фільтрація за категоріями

Панель фільтрів використовує перетин бітових прапорців. Кожній категорії присвоюється позиція біта; кожна симуляція представлена бітовою маскою своїх категорій. Мультитегова фільтрація — це одна побітова операція AND:

          // Побудова бітової маски для кожної симуляції при завантаженні
          const CAT_BITS = { physics:
          1, quantum: 2,
          biology: 4, chemistry:
          8, economics: 16 };
          sims.forEach(s => { s.mask = s.cats.reduce((acc, c) => acc | (CAT_BITS[c] ?? 0),
          0); });

          // Перевірка, чи симуляція відповідає всім обраним фільтрам
          function
          matchesFilter(sim, selectedMask) {
          return selectedMask ===
          0 || (sim.mask & selectedMask) ===
          selectedMask; }
        

Крок 5 — Серіалізація стану в URL

Пошуковий запит і активні фільтри серіалізуються в URL при кожній зміні, тож користувачі можуть додавати відфільтровані види в закладки та ділитися ними: /?q=fluid&cat=physics,chemistry&diff=beginner. Стан зчитується назад при завантаженні сторінки, а інтерфейс відновлюється без будь-якого переходу сторінки.

          function
          pushState(query, cats, difficulty) {
          const params =
          new URLSearchParams();
          if (query) params.set('q', query); if (cats.length) params.set('cat', cats.join(','));
          if (difficulty) params.set('diff', difficulty); history.replaceState({},
          '', '?' +
          params.toString()); }
        

Результати продуктивності

До

250 видимих

Усі симуляції завжди рендерилися — 250 DOM-вузлів, зависання макета при зміні розміру

Після

<5 мс на пошук

Пошук у дереві + фільтрація за бітовою маскою + оновлення DOM лише для відповідних симуляцій — непомітно на будь-якому пристрої

До

~40 с

Час пошуку конкретної симуляції прокручуванням для нового відвідувача

Після

~3 с

Час пошуку симуляції за 2-символьним префіксом і одним фільтром категорії

Отримані уроки

Не хапайтеся за бібліотеку одразу. Lunr.js і Fuse.js чудові, але важать 20–40 КБ у gzip. Наше власне рішення важить 2 КБ разом із деревом (trie) і його було простіше налаштувати.
Застосовуйте дебаунс до поля пошуку. Подія вводу спрацьовує на кожне натискання клавіші; з дебаунсом 120 мс ми повністю пропускаємо проміжні стани під час швидкого набору тексту.
Обчислюйте бітові маски заздалегідь, при завантаженні, а не під час пошуку. Побудова індексу виконується один раз при завантаженні сторінки (~8 мс); кожен наступний пошук — це чисте зчитування.
Віртуальний скрол став би у пригоді при 500+ елементах — наразі CSS-властивість content-visibility: auto дає безкоштовне зниження вартості рендерингу на 60% для карток поза екраном.

Відкрита архітектура: JSON пошукового індексу генерується Python-скриптом, що зчитує метадані симуляцій. Додавання нової симуляції автоматично включає її в результати пошуку — без жодного ручного обслуговування.