Kaip pasirinkti tarp maišos lentelės ir „Trie“ (prefikso medis)?

Taigi, jei man reikia pasirinkti tarp maišymo stalo ar priešdėlį, kokie diskriminaciniai veiksniai leis man pasirinkti vieną iš jų. Mano pačių naivų požiūriu, atrodo, kad naudojant trie yra papildomos pridėtinės vertės, nes jis nėra saugomas kaip masyvas, o vykdymo metu (jei ilgiausias raktas yra ilgiausias angliškas žodis), tai gali būti iš esmės O (1) (palyginti su viršutine riba). Galbūt ilgiausias anglų kalbos žodis yra 50 simbolių?

„Hash“ lentelės iškart peržiūrimos, kai tik gausite indeksą. Atrodo, kad raktas, norint gauti indeksą, gali lengvai užtrukti apie 50 žingsnių.

Ar kas nors man gali suteikti daugiau patirties? Ačiū!

109
29 окт. Justin Bozonier yra nustatytas spalio 29 d 2008-10-29 08:19 '08, 08:19, 2008-10-29 08:19
@ 8 atsakymai

Bandymo nauda:

Pagrindai:

  • Numatomas paieškos laikas yra O (k), kur k yra raktų dydis
  • Paieška gali užtrukti mažiau nei k kartus, jei nėra.
  • Palaiko užsakytą judėjimą
  • Nereikia maišos funkcijos
  • Išimtis yra paprasta.

Naujos operacijos:

  • Galite greitai ieškoti raktų priešdėlių, išvardyti visus įrašus su nurodytu prefiksu ir pan.

Susijusios struktūros privalumai:

  • Jei yra daug bendrų prefiksų, erdvė, kurioje jie yra reikalingi, yra dažnas.
  • Neišvengiami bandymai gali atskirti struktūrą. Vietoj to, kad atnaujintumėte „trie“, galite sukurti naują, kuri skiriasi tik viename filiale, kitoje vietoje, nukreiptoje į senąjį. Tai gali būti naudinga lygiagrečiai, daugialypėms lentelės versijoms ir pan.
  • Nepakeičiamos trys yra suspaustos. Tai reiškia, kad jis gali dalintis sufikso struktūra naudodamas maišymo konfigūraciją.

Maišos lentelių privalumai:

  • Visi žino hashtables, ar ne? Jūsų sistema jau bus tinkamai optimizuota, greičiau nei bandoma daugeliu tikslų.
  • Jūsų raktai neturėtų turėti specialios struktūros.
  • Daugiau vietos nei akivaizdi su trie susijusi struktūra ( žr. Komentarus žemiau )
95
29 окт. atsakymą pateikė Darius Bacon spalio 29 d. 2008-10-29 09:38 '08 at 9:38 2008-10-29 09:38

Viskas priklauso nuo to, kokią problemą bandote išspręsti. Jei viskas, ką jums reikia padaryti, yra įterpti ir ieškoti, eikite į maišos lentelę. Jei jums reikia išspręsti sudėtingesnes problemas, pvz., Su prefiksais susijusias užklausas, geriausias sprendimas gali būti trie.

41
29 окт. Adam Rosenfield atsakymas, pateiktas spalio 29 d 2008-10-29 08:25 '08, 08:25 2008-10-29 08:25

Kiekvienas žino maišos lentelę ir jos naudojimą, bet tai nėra tiksliai pastovus paieškos laikas, tai priklauso nuo to, kaip didelė maišos lentelė, skaičiavimo sudėtingumo funkcija.

Didelių hash lentelių sukūrimas efektyviai paieškai nėra elegantiškas sprendimas daugelyje pramoninių scenarijų, kai netgi mažas latentumas / mastelis yra svarbus (pvz., Didelis prekybos dažnis). Turite užtikrinti, kad duomenų struktūros būtų optimizuotos atminties užimam vietai, taip pat sumažintų talpyklos praleidimą.

Labai geras pavyzdys, kai trie geriau tinka, yra pranešimų tarpinė programinė įranga. Jūs turite milijoną abonentų ir pranešimų leidėjų skirtingoms kategorijoms (pagal JMS temas ar mainus), tokiais atvejais, jei norite filtruoti pranešimus pagal temas (kurios iš tikrųjų yra stygos), jūs tikrai nenorite sukurti milijono maišos lentelės parašų su milijonais temų. Geriausias būdas yra išsaugoti temas, todėl, kai filtravimas atliekamas pagal atitikimo temas, jo sudėtingumas nepriklauso nuo temų / abonentų / leidėjų skaičiaus (tai priklauso tik nuo linijos ilgio). Man tai patinka, nes jūs galite būti kūrybingi su šia duomenų struktūra, kad optimizuotumėte erdvės reikalavimus ir dėl to sumažintumėte talpyklą.

21
15 апр. atsakymą pateikė vartotojo179156 balandžio 15 d 2012-04-15 08:57 '12 8:57 2012-04-15 08:57

Naudokite medį:

  • Jei jums reikia automatinio užbaigimo funkcijos
  • Rasti visus žodžius, prasidedančius „a“ arba „kirviu“ ir pan.
  • Sufikso medis yra speciali medžio forma. Sufiksų medžiai turi naudos, kurią maišos negali padengti, sąrašas.
8
12 янв. Dr.Sai sausio 12 d. Atsakymas 2012-01-12 13:27 '12 13:27 2012-01-12 13:27

Ką aš nieko nematau aiškiai paminėdamas, ir manau, kad tai svarbu nepamiršti. Tiek maišymo lentelėse, tiek skirtingų tipų bandymuose paprastai yra O(k) operacijos, kur k yra eilutės ilgis bitais (arba lygiaverčiai simboliais).

Tai rodo, kad turite gerą maišos funkciją. Jei nenorite, kad ūkyje ir ūkiuose auginamuose gyvūnuose būtų tokios pačios vertės maišos vertė, maišos funkcija turės naudoti visus raktų bitus, todėl ūkinių gyvūnų maišymas turėtų užtrukti maždaug dvigubai daugiau nei ūkio dydis. jei nesate tam tikru scenarijumi su pasirinktiniu hash, bet yra keli panašūs scenarijai, kaip taupyti operacijas ir su bandymais). Ir su vanilės bandymu aišku, kodėl įterpiant „ūkinius gyvūnus“ prireiks maždaug dvigubai daugiau nei „ūkis“. Galiausiai tai pasakytina apie suspaustus bandymus.

1
16 окт. atsakymą pateikė user3391564 16 okt. 2014-10-16 15:40 '14, 15:40 2014-10-16 15:40

„HashTable“ įgyvendinimas yra erdvinis efektyvumas, lyginant su pagrindiniu „ Trie“ diegimu . Tačiau, kai naudojate stygas daugelyje praktinių programų, reikia racionalizuoti. Bet „HashTable“ visiškai pažeidžia miško grafikos tvarką. Dabar, jei jūsų paraiška atlieka operacijas, pagrįstas leksine tvarka (pavyzdžiui, dalinė paieška, visos eilutės su nurodytu prefiksu, visi žodžiai surūšiuota tvarka), turėtumėte naudoti Tries. Jei norite peržiūrėti tik „HashTable“ (kaip įmanoma, tai suteikia minimalų paieškos laiką).

PS: Be to, Ternary Search Trees (TST) bus puikus pasirinkimas. Jo paieškos laikas yra ilgesnis nei „HashTable“, bet veiksmingas visose kitose operacijose. Be to, jos efektyvesnė erdvė nei bando.

1
18 июня '17 в 19:05 2017-06-18 19:05 Atsakymą pateikė Jay Jodiwal birželio 17 d. 17:05 2017-06-18 19:05

Įterpimas ir paieška pagal Trie yra tiesinės su einamosios linijos O (-ų) ilgiu.

„Hash“ suteiks jums O (1), kad įterptų paieškos ansą, bet pirmiausia turite apskaičiuoti maišą pagal įvesties eilutę, kuri vėl yra O (s).

Atspindėjimas, asimptotinis laikinasis sudėtingumas abiem atvejais yra tiesinis.

Trie turi tam tikrą papildomą pridėtinę vertę duomenų atžvilgiu, tačiau galite pasirinkti suspaustą trie, kuris vėl priverčia jus prijungti prie maišos lentelės.

Norėdami nutraukti kaklaraištį, užduokite sau šį klausimą: ar turiu ieškoti tik išsamių žodžių? Arba turiu grąžinti visus žodžius, kurie atitinka prefiksą? (Kaip ir nuspėjamojoje teksto įvedimo sistemoje). Pirmuoju atveju eikite į maišą. Tai paprastesnis ir švaresnis kodas. Lengviau išbandyti ir prižiūrėti. Norint geriau panaudoti, jei tai yra prefiksai ar priesagos, eikite į trie.

Ir jei tai padarysite tik linksmam laikui, įvedus „trie“, sekmadienis bus tinkamai naudojamas.

0
19 нояб. Atsakymą pateikė Visiedo lapkričio 19 d. 2017-11-19 20:16 '17 at 20:16 2017-11-19 20:16

Kai kurioms (paprastai įterptoms, realaus laiko) programoms reikalingas apdorojimo laikas, nepriklausantis nuo duomenų. Tokiu atveju maišos lentelė gali garantuoti žinomą vykdymo laiką, o trie yra priklausomas nuo duomenų.

-1
29 окт. atsakymą pateikė Adam Liss 29 okt. 2008-10-29 08:31 '08, 08:31, 2008-10-29 08:31

Kiti klausimai apie žymes, kurias galima arba užduoti klausimą