V súčasnosti ukladám veľké množstvo nepodpísaných 32-bitových celých čísel v a bit trie (efektívne vytvára binárny strom s uzlom pre každý bit v 32-bitovej hodnote.) Toto je veľmi efektívne pre rýchle vyhľadávanie presných hodnôt.
Teraz by som chcel mať možnosť vyhľadať kľúče, ktoré môžu alebo nemusia byť v trii a nájsť hodnotu pre prvý kľúč, ktorá je menšia alebo rovná vyhľadávaciemu kľúču. Je to možné s trochou snahy, alebo by som mal použiť inú štruktúru údajov?
Používam trie kvôli svojej rýchlosti a cache pamäti, a v ideálnom prípade chcem obetovať ani jeden.
Predpokladajme napríklad, že trie má pridané dva kľúče:
0x00AABBCC0x00AABB00
a teraz hľadám kľúč, ktorý neexistuje, 0x00AABB11, Chcel by som nájsť prvý kľúč prítomný v strome s hodnotou <= vyhľadávací kľúč, ktorý by v tomto prípade bol uzlom pre 0x00AABB00.
Aj keď som na to myslel možný algoritmus, hľadám konkrétne informácie o tom, či to tak je účinne možné a / alebo ak existujú známe algoritmy za to, čo bude bezpochyby lepšie ako moje.
odpovede:
1 pre odpoveď č. 1Môžeme si predstaviť bit trie ako binárny vyhľadávací strom. V skutočnosti je to binárny vyhľadávací strom. Zoberme si napríklad 32-bitový trie, predpokladajme, že ľavé dieťa je 0, pravé dieťa ako 1. Pre koreňový adresár je ľavá podstrom pre čísla menšie ako 0x80000000 a pravá podstrom pre čísla nie menšie ako 0x80000000 atď. tak ďalej. Takže podobnú metódu môžete použiť len na nájdenie najväčšej položky, ktorá nie je väčšia ako kľúč vyhľadávania v binárnom vyhľadávacom strome. Len sa nemusíte báť o spätných doskách, príliš nezíska späť a nezmení zložitosť vyhľadávania. Ak v bitovej trii zlyhá zápas, jednoducho nájdite najsprávnejšie dieťa najbližšieho predka zlyhaného uzla.
1 pre odpoveď č. 2
Ak sú dáta statické - nepridávate aleboodstraňovanie položiek - potom by som sa dobre pozrel pomocou jednoduchého poľa s binárnym vyhľadávaním. Obetujete miesto v vyrovnávacej pamäti, ale to nemusí byť katastrofické. Nevidím miesto v vyrovnávacej pamäti ako samoúčelné, ale skôr ako prostriedok zrýchlenia štruktúry údajov.
Lepšiu lokalizáciu vyrovnávacej pamäte môžete získať vytvorenímvyvážený binárny strom v poli. Pozícia 0 je koreňový uzol, pozícia 1 je ľavý uzol, pozícia 2 je pravý uzol atď. Je to rovnaká štruktúra, akú by ste použili pre binárnu haldu. Ak ste ochotní prideliť ďalšie 4 bajty na uzol, môžete z neho urobiť binárny strom s ľavými vláknami, takže ak hľadáte X a skončíte na najbližšej väčšej hodnote, po tomto ľavom vlákne by ste dostali ďalšiu menšiu hodnotu. Všetci sme však povedali, nechápem, kde by to vo všeobecnom prípade mohlo prekonať rovinu.
Veľa záleží na tom, aké riedke sú vaše údaje a čorozsah je. Ak sa pozeráte na niekoľko tisíc možných hodnôt v rozmedzí od 0 do 4 miliárd, potom vyzerá binárne vyhľadávanie celkom atraktívne. Ak hovoríte o 500 miliónoch rôznych hodnôt, potom by som sa mal pozrieť na pridelenie bitového poľa (500 megabajtov) a priame vyhľadávanie pomocou lineárneho spätného skenovania, čo by vám poskytlo veľmi dobrú lokalizáciu vyrovnávacej pamäte.
1 pre odpoveď č. 3
Bit trie chodí 32 uzlov v najlepšom prípade, keď je položka nájdená.
Napríklad milión záznamov v červeno-čiernom strome std::map alebo java.util.TreeMap by vyžadoval iba log2 (1 000 000) alebo zhruba 20 uzlov na dotaz, najhorší prípad. A nemusíte vždy chodiť na spodok stromu, aby ste mali priemerný prípad príťažlivý.
Pri hľadaní späť <= rozdiel je ešte výraznejší.
Čím menej záznamov máte, tým je lepší prípad červeno-čierneho stromu
Minimálne by som porovnal akékoľvek riešenie s červeno-čiernym stromom.