Snažím sa zistiť, čo bude viacefektívne z hľadiska rýchlosti vyhľadávania, či už trie alebo B-Tree. Mám slovník anglických slov a chcem v ňom efektívne nájsť slovo.
odpovede:
1 pre odpoveď č. 1Ak výrazom „efektívnejšie v čase hľadania“ odkazujete na teoretickú časovú zložitosť, potom ponúka B Tree O(logn * |S|)1 časová náročnosť vyhľadávania, zatiaľ čo trie ponúka O(|S|) časová zložitosť, kde |S| je dĺžka hľadaného reťazca a n je počet prvkov v slovníku.
Ak „efektívnejšie v čase hľadania“ vássa vzťahujú na skutočnú dobu chodu, ktorá závisí od skutočnej implementácie, skutočných údajov a skutočného správania pri vyhľadávaní. Niekoľko príkladov, ktoré by mohli ovplyvniť odpoveď:
- Veľkosť údajov
- Úložný systém (napríklad: RAM / Flah / disk / distribuovaný súborový systém / ...)
- Rozdelenie vyhľadávaní
- Optimalizácia kódu každej implementácie
- (a oveľa viac)
(1) Existujú O(logn) porovnania a každé porovnanie trvá O(|S|) krát, pretože musíte prejsť celým reťazcom, aby ste sa rozhodli, ktorá je vyššia (analýza najhoršieho prípadu).
0 pre odpoveď č. 2
Záleží na tom, čo potrebujete. Ak chcete získať celok subtree, a B+Tree je vaša najlepšia voľba, pretože je priestorovo efektívny a tiež rozvetvovací faktor stromu B + ovplyvňuje jeho výkon (počet sprostredkujúcich uzlov). Ak h je výška stromu, potom nmax ~~ bh, teda h ~~ log (nmax) / log (b).
s n = 1 000 000 000 a b = 100, máme h ~~ 5. Znamená to teda iba 5 dereferencia ukazovateľa pre prechod od koreňa k listu. Je to priateľskejšie k vyrovnávacej pamäti ako Trie.
Ale ak chcete získať prvý N deti z a podstrom, potom je Trie najlepšou voľbou, pretože jednoducho navštívite menej uzlov ako v scenári stromu B +. Aj slovo predpona pre doplnenie je dobre spracované v jazyku trie.