Optymalizacja drzew prefiksowych: od 825 MB do 18 MB dla uzupełniania automatycznego
Drzewo prefiksowe do wyszukiwania 50 tys. poleceń zajmowało 825 MB pamięci i działało 8 razy wolniej niż tablica mieszająca (4,8 mln cykli w porównaniu do 600 tys.). Każdy węzeł miał 2064 bajty z tablicą 256 wskaźników, co powodowało wiele przestrajek bufora podczas wyszukiwania.
Benchmark perf stat wykazał 125 tys. przestrajek bufora w porównaniu do 18 tys. w przypadku tablicy mieszającej. Wyszukiwanie ciągu o długości 5 znaków generuje 5 przestrajek, ponieważ żaden węzeł nie mieści się w linii bufora.
Struktura węzła i zużycie pamięci
Typowa implementacja węzła:
typedef struct trie_node {
struct trie_node *children[256]; // 2048 bajtów
void *value; // 8 bajtów
bool is_end; // 1 bajt
// Razem: 2064 bajty
} trie_node_t;Dla zbioru danych z 50 tys. poleceń (średnia długość 8 znaków) potrzeba ok. 400 tys. węzłów. Łącznie 825 MB w porównaniu do 1,2 MB w tablicy mieszającej — różnica 687-krotna.
Drzewa bazowe: kompresja łańcuchów
Rozwiązanie to drzewa bazowe (Patricia tries), gdzie łańcuchy pojedynczych węzłów są zwężane do prefiksów. Węzeł przechowuje ciąg prefiksu zamiast poszczególnych znaków.
typedef struct radix_node {
char *prefix;
int prefix_len;
struct radix_node *children[256];
void *value;
} radix_node_t;Algorytm wyszukiwania:
void* radix_search(radix_node_t *node, const char *key) {
while (node) {
int i = 0;
while (i < node->prefix_len && key[i] == node->prefix[i]) {
i++;
}
if (i < node->prefix_len) return NULL;
if (key[i] == '\0') return node->value;
node = node->children[(unsigned char)key[i]];
key += i + 1;
}
return NULL;
}Wynik: pamięć spadła do 330 MB, cykle do 2,4 mln, przestrajki bufora do 6,8. Prędkość wzrosła dwukrotnie.
Adaptacyjne drzewa bazowe (ART)
Problem pozostał: tablice 256 wskaźników są wypełnione tylko na 2%. Rozwiązanie — adaptacyjne węzły według liczby dzieci.
- Node4 (1–4 dzieci): 40 bajtów
- Node16 (5–16 dzieci): 152 bajty
- Node48 (17–48 dzieci): 640 bajtów
- Node256 (49+ dzieci): 2048 bajtów
Strategia rozwoju: Node4 → Node16 → Node48 → Node256 przy przekroczeniu limitu.
Średni węzeł: 40–152 bajtów zamiast 2048. Oszczędność pamięci 10–50 razy.
Benchmarki optymalizacji
Porównanie przy 1 mln wyszukiwań w 50 tys. poleceń:
| Struktura | Pamięć | Cykle | Przestrajki bufora | Przyspieszenie |
|-----------|--------|-------|-------------------|----------------|
| Trie | 825 MB | 4 800 | 12,5 | 1× |
| Radix | 330 MB | 2 400 | 6,8 | 2× |
| ART | 18 MB | 1 200 | 3,2 | 4× |
| Hash | 1,2 MB | 600 | 1,8 | 8× |
ART jest 45 razy bardziej kompaktowe niż standardowe drzewo trie, a węzły Node4/Node16 mieszczą się w 1–2 liniach bufora.
Scenariusze zastosowania drzew prefiksowych
Użyj ART, gdy potrzebujesz operacji prefiksowych:
- Uzupełnianie automatyczne: przeglądanie poddrzewa w czasie O(k + m), gdzie m to liczba pasujących wyników. Tablica mieszająca wymaga pełnego skanowania.
- Trasowanie IP: dopasowanie najdłuższego prefiksu według bitów adresu.
- Sprawdzanie pisowni: wyszukiwanie według odległości edytorskiej przez prefiksy.
- Tablice rozrzedzone: jak w jądrze Linux (bufor stron, IDR, XArray).
Unikaj dla dokładnego wyszukiwania, małych zbiorów danych (<1000 elementów) lub ciągów bez wspólnych prefiksów.
Drzewa bazowe w jądrze Linux
Jądro używa radix_tree_node z 64 slotami (6 bitów poziomu). Dla indeksu 32-bitowego – 6 poziomów, ~6 przestrajek bufora w porównaniu do 32 w BST.
Zalety:
- Operacje na zakresach
- Przewidywalna złożoność O(log₆₄ n)
- Skuteczne dla danych rozrzedzonych
Co ważne
- Standardowe drzewa trie zużywają 687× więcej pamięci ze względu na tablice 256 wskaźników
- ART zmniejsza pamięć do 18 MB i przestrajki bufora do 3,2 dzięki adaptacyjnym węzłom
- Używaj dla zapytań prefiksowych; tablice mieszające wygrywają w dokładnym wyszukiwaniu
- Drzewa bazowe zwężają łańcuchy, dając 2-krotne przyspieszenie
- W jądrze Linux — standard dla tablic rozrzedzonych i dystrybucji ID
— Editorial Team
Brak komentarzy.