Azərbaycan
Deutschland
Lietuva
ශ්රී ලංකාව
Türkiyə
Gegutės maiša informatikos metodas padedantis išspręsti maišos funkcijų reikšmių susidūrimo arba kolizijos problemą maiš
Gegutės maiša
Gegutės maiša - informatikos metodas, padedantis išspręsti maišos funkcijų reikšmių susidūrimo, arba kolizijos problemą maišos lentelėje. Pirmieji gegutės maišą aprašė Rasmus Pagh ir Flemming Friche Rodler 2001 m.
Idėja
Pagrindinė idėja - naudoti dvi maišos funkcijas, o ne vieną. Kiekvienam raktui jos duoda dvi galimas vietas maišos lentelėje.
Rakto įterpimui naudojamas godusis algoritmas: naujas raktas yra įterpiamas vienoje iš dviejų galimų vietų. Jei vieta nėra tuščia, jis išmeta toje vietoje buvusį raktą: išstumtas raktas keliauja į savo antrąją vietą, išmeta ten buvusį raktą ir t. t., kol kuris nors išmestasis raktas atranda laisvą vietą. Priešingu atveju procesas užsitęsia be galo. Pastaruoju atveju maišos lentelė yra perdaroma naudojant naujas maišos funkcijas.
Rakto paieška reikalauja peržiūrėti tik dvi vietas lentelėje, t. y. trunka konstantinį laiką. Dauguma kitų maišos lentelės algoritmų gali neturėti konstantinio blogiausio atvejo rėžio rakto paieškai.
Taip pat galima parodyti, kad įterpimai vidutiniškai trunka konstantinį laiką, netgi atsižvelgiant į retkarčiais vykstančius lentelės perdarymus, vienintelis reikalavimas - kad lentelėje būtų užpildyta mažiau negu pusė vietų.
Apibendrinimai
Gegutės maišos apibendrinimai naudoja daugiau nei dvi maišos funkcijas ir gali sėkmingai dirbti išnaudodami didesnę dalį maišos lentelės talpos, nors šiuo atveju šiek tiek sumažėja paieškos ir įterpimo greitis. Trijų maišos funkcijų naudojimas leidžia apkrauti lentelę 91 %. Kitas gegutės maišos apibendrinimas - naudoti daugiau negu vieną raktą "kibirėliui" (angl. bucket). Naudojant 2 raktus "kibirėliui" leidžia panaudoti 80 % lentelės. Gegutės maiša gali būti naudojama realizuojant duomenų struktūrą ekvivalenčią .
Kita
Metodas pavadintas pagal kai kurių rūšių gegučių elgesį: jų gegučiukai išsiritę išmeta kitus kiaušinius ar jauniklius iš lizdo. Zukowski ir kiti parodė, kad gegutės maiša yra žymiai greitesnė nei mažoms, liekančio podėlio (angl. cache - resident) maišos lentelėms naudojant šiuolaikinius procesorius. K. Ross parodė, kad "sukibirintos" (angl. bucketized) gegutės maišos versijos (t. y., tos, kurios naudoja daugiau nei vieną raktą "kibirėliui") yra greitesnės nei tradiciniai metodai didelėms maišos lentelėms, kai lentelės apkrovimas didelis. Deja, bet kol kas gegutės maiša lieka mažai žinoma už mokslinės visuomenės ribų.
Taip pat žiūreti
Literatūra
- Gegutės maiša, teorija ir praktika (2 dalis, 3 dalis)
Autorius: www.NiNa.Az
Išleidimo data:
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu, mobilusis, porn, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, pornografija, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris, Informacija apie Gegutės maiša, Kas yra Gegutės maiša? Ką reiškia Gegutės maiša?
Gegutes maisa informatikos metodas padedantis isspresti maisos funkciju reiksmiu susidurimo arba kolizijos problema maisos lenteleje Pirmieji gegutes maisa aprase Rasmus Pagh ir Flemming Friche Rodler 2001 m Gegutes maisos pavyzdys Rodykles rodo alternatyvia vieta kiekvienam raktui Naujas elementas A butu įterptas perkeliant A į jo alternatyvia vieta uzimta B ir perkeliant B į jo alternatyvia vieta kuri siuo metu laisva Naujo elemento įterpimas H vietoje nepavyktu kadangi H yra ciklo dalis naujas elementas vel butu ismestas ir maisos lentele reiktu perdaryti IdejaPagrindine ideja naudoti dvi maisos funkcijas o ne viena Kiekvienam raktui jos duoda dvi galimas vietas maisos lenteleje Rakto įterpimui naudojamas godusis algoritmas naujas raktas yra įterpiamas vienoje is dvieju galimu vietu Jei vieta nera tuscia jis ismeta toje vietoje buvusį rakta isstumtas raktas keliauja į savo antraja vieta ismeta ten buvusį rakta ir t t kol kuris nors ismestasis raktas atranda laisva vieta Priesingu atveju procesas uzsitesia be galo Pastaruoju atveju maisos lentele yra perdaroma naudojant naujas maisos funkcijas Rakto paieska reikalauja perziureti tik dvi vietas lenteleje t y trunka konstantinį laika Dauguma kitu maisos lenteles algoritmu gali netureti konstantinio blogiausio atvejo rezio rakto paieskai Taip pat galima parodyti kad įterpimai vidutiniskai trunka konstantinį laika netgi atsizvelgiant į retkarciais vykstancius lenteles perdarymus vienintelis reikalavimas kad lenteleje butu uzpildyta maziau negu puse vietu ApibendrinimaiGegutes maisos apibendrinimai naudoja daugiau nei dvi maisos funkcijas ir gali sekmingai dirbti isnaudodami didesne dalį maisos lenteles talpos nors siuo atveju siek tiek sumazeja paieskos ir įterpimo greitis Triju maisos funkciju naudojimas leidzia apkrauti lentele 91 Kitas gegutes maisos apibendrinimas naudoti daugiau negu viena rakta kibireliui angl bucket Naudojant 2 raktus kibireliui leidzia panaudoti 80 lenteles Gegutes maisa gali buti naudojama realizuojant duomenu struktura ekvivalencia KitaMetodas pavadintas pagal kai kuriu rusiu geguciu elgesį ju geguciukai issirite ismeta kitus kiausinius ar jauniklius is lizdo Zukowski ir kiti parode kad gegutes maisa yra zymiai greitesne nei mazoms liekancio podelio angl cache resident maisos lentelems naudojant siuolaikinius procesorius K Ross parode kad sukibirintos angl bucketized gegutes maisos versijos t y tos kurios naudoja daugiau nei viena rakta kibireliui yra greitesnes nei tradiciniai metodai didelems maisos lentelems kai lenteles apkrovimas didelis Deja bet kol kas gegutes maisa lieka mazai zinoma uz mokslines visuomenes ribu Taip pat ziuretiMaisos funkcijaLiteraturaGegutes maisa teorija ir praktika 2 dalis 3 dalis