Devlog #17 — Budowa szybkiego wyszukiwania i filtrowania…

250+

zindeksowanych symulacji

<5 ms

opóźnienie wyszukiwania

18 KB

indeks wyszukiwania po gzip

zależności

Problem: 250 pozycji w siatce

Pierwotna strona główna pokazywała wszystkie symulacje w responsywnej siatce — w porządku przy 50, do zniesienia przy 100, nie do przejścia przy 250. Analityka potwierdziła problem: użytkownicy trafiający z wyszukiwarki lądowali na konkretnych stronach symulacji, ale ci, którzy trafiali na stronę główną, przewijali ją przez kilka sekund i wychodzili.

Potrzebowaliśmy wyszukiwania i filtrowania. Ograniczenia: żadnego serwera, żadnego etapu budowania, żadnej zewnętrznej usługi wyszukiwania. Wszystko musiało działać w przeglądarce, korzystając wyłącznie ze statycznego pliku JSON.

Krok 1 — Indeks wyszukiwania jako JSON

Skrypt w Pythonie przechodzi przez każdy katalog symulacji, czyta metadane z każdego pliku index.html (tytuł, opis, tagi kategorii, słowa kluczowe) i generuje kompaktowy plik search-index.json:

          // search-index.json (skrócone)
          [ {
          "id": "double-slit", "title":
          "Double-Slit Experiment",
          "desc":
          "Quantum wave-particle duality...",
          "cats": ["quantum", "optics"], "tags": ["interference",
          "wave", "photon"],
          "difficulty":
          "intermediate"
          }, ... ]
        

Pełny indeks dla 250 symulacji waży 142 KB nieskompresowane, 18 KB po gzip — dużo poniżej progu pamięci podręcznej HTTP przeglądarki, co daje natychmiastowe ładowanie przy kolejnych wizytach.

Krok 2 — Indeks odwrócony dla wyszukiwania pełnotekstowego

Zwykłe przeszukiwanie tablicy 250 elementów przy każdym naciśnięciu klawisza byłoby wystarczająco szybkie (250 obiektów to dla CPU nic), ale chcieliśmy dopasowania prefiksów i rankingu wyników. Indeks odwrócony mapuje każdy token słowny na listę identyfikatorów dokumentów, które go zawierają:

          function
          buildInvertedIndex(docs) {
          const index =
          new Map();
          // token → zbiór ID dokumentów
          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);
          // pomijamy stop-słowa
          }
        

Krok 3 — Trie do dopasowywania prefiksów

Użytkownik wpisuje „fluid” i oczekuje, że pojawią się „fluid dynamics”, „SPH fluid” oraz „microfluid”. Indeks odwrócony dopasowuje tylko dokładne tokeny. Rozwiązuje to trie (drzewo prefiksowe): każdy węzeł reprezentuje jeden znak; wszystkie ścieżki od korzenia do liścia reprezentują pełny token. Znalezienie wszystkich słów zaczynających się od „flu” ma złożoność O(długość_prefiksu) — stałą względem rozmiaru biblioteki.

          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);
          // propagujemy ID w dół każdego węzła prefiksu
          } }

          search(prefix) {
          let node = this.root;
          for (const ch
          of prefix) {
          if (!node[ch]) return
          new Set(); node = node[ch]; }
          return node._ids;
          // wszystkie dokumenty zawierające słowo zaczynające się od
            prefiksu
          } }
        

Krok 4 — Filtrowanie wielotagowe kategorii

Panel filtrów wykorzystuje przecięcie flag bitowych. Każdej kategorii przypisana jest pozycja bitowa; każda symulacja jest reprezentowana jako maska bitowa swoich kategorii. Filtrowanie wielotagowe to pojedyncza operacja AND:

          // Budowa maski bitowej dla każdej symulacji przy wczytywaniu
          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); });

          // Sprawdzenie, czy symulacja pasuje do wszystkich wybranych filtrów
          function
          matchesFilter(sim, selectedMask) {
          return selectedMask ===
          0 || (sim.mask & selectedMask) ===
          selectedMask; }
        

Krok 5 — Serializacja stanu w URL

Zapytanie wyszukiwania i aktywne filtry są serializowane do URL przy każdej zmianie, dzięki czemu użytkownicy mogą dodawać do zakładek i udostępniać przefiltrowane widoki: /?q=fluid&cat=physics,chemistry&diff=beginner. Stan jest odczytywany ponownie przy ładowaniu strony, a interfejs jest przywracany bez żadnego przejścia strony.

          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()); }
        

Wyniki wydajnościowe

Przedtem

250 widocznych

Wszystkie symulacje zawsze renderowane — 250 węzłów DOM, szarpanie layoutu przy zmianie rozmiaru okna

Potem

<5 ms wyszukiwania

Wyszukiwanie w trie + filtr maski bitowej + aktualizacja DOM tylko dla pasujących symulacji — niezauważalne na żadnym urządzeniu

Przedtem

~40 s

Czas znalezienia konkretnej symulacji przez przewijanie dla nowych odwiedzających

Potem

~3 s

Czas znalezienia symulacji dzięki 2-znakowemu wyszukiwaniu prefiksowemu i jednemu filtrowi kategorii

Wnioski

Nie sięgaj od razu po bibliotekę. Lunr.js i Fuse.js są świetne, ale ważą 20–40 KB po gzip. Nasze własne rozwiązanie waży 2 KB razem z drzewem trie i łatwiej się je dostrajało.
Debounce dla pola wyszukiwania. Zdarzenie input odpala się przy każdym naciśnięciu klawisza; z debounce 120 ms całkowicie pomijamy stany pośrednie podczas szybkiego pisania.
Wstępnie oblicz maski bitowe przy ładowaniu, nie przy wyszukiwaniu. Budowa indeksu odbywa się raz, przy ładowaniu strony (~8 ms); każde kolejne wyszukiwanie to czyste wyszukanie w strukturze.
Wirtualne przewijanie przydałoby się przy 500+ elementach — na razie CSS content-visibility: auto daje darmowe 60% redukcji kosztu renderowania dla kart poza ekranem.

Otwarta architektura: Indeks wyszukiwania JSON jest generowany przez skrypt w Pythonie, który czyta metadane symulacji. Dodanie nowej symulacji automatycznie włącza ją do wyników wyszukiwania — bez ręcznego utrzymania.