Ker je Odgovori na vprašanja s predstavitev Algoritma/PS že zelo "polna" in dolga, predlagam, da sedaj stvari (torej odgovore na nova vprašanja iz SN objavljate tukaj, pri tej temi ...
Odgovori na vprašanja s predstavitve skip list.
V odgovor na Jure Lilija
če bi večkrat odstranili elemente, ki so na višjih nivojih, bi potem popolnoma pokvarili strukturo?
od Jure Lilija -
Pri
optimalnem skip listu bi pokvarili strukturo. Pri skip listu pa čisto odvisno
od velikosti, če skip list ne bi bil velik in bi imeli to smolo, ki seveda ni
zelo verjetna, da bi odstranjevali samo elemente, ki so v višjih nivojih bi se
tudi struktura pokvarila. Pri velikih skip listih se nam pa tega ni treba bati.
V odgovor na Jure Lilija
kako poteka odstranjevanje vozlišč na višjih nivojih? (saj do njih iz spodnjih nivojev nimamo direktnega dostopa)
od Petra Kogovšek -
To lahko naredimo tako, da ko pridemo do elementa, ki ga želimo izbrisati element odstranimo na tem nivoju in povežemo njegovega 'predhodnika' z
njegovim 'naslednikom'. Nato se po njegovem 'predhodniku' prestavimo en nivo
nižje in postopek ponavljamo dokler elementa ne odstranimo iz vseh nivojev.
Ko imamo dva nivoja vemo, da lahko gremo po celem zgornjem, po spodnjem pa samo po delu. In če je zgornji del razporejen enakomerno, to pomeni, da lahko gremo največ po spodnjem delu (n/število elementov v zgornjem). Če imamo zgoraj koren(n) elementov imamo časovno zahtevnost 2*koren(n). Če bi imeli manj elementov v zgornjem nivoju, bi to pomenilo, da je izraz (n/št. elementov v zgornjem nivoju) večji od koren(n) in to pomeni, da bi časovna zahtevnost bila večja od koren(n). Če bi pa imeli več elementov od koren(n) v zgornjem nivoju bi pa to že avtomatično pomenilo, da bo zaradi možnega celega prehoda po zgornjem nivoju, časovna zahtevnost večja od koren(n).
O
različnih primerih uporabe pa si lahko prebereš na spletni strani https://en.wikipedia.org/wiki/Skip_list
v poglavju Usages.
V odgovor na Jure Lilija
zakaj je naključno vstavljanje v višje nivoje boljše od tistega, kjer vsak drug element vstavimo v višji nivo? primeri uporabe?
od Jure Lilija -
Ko imamo že postavljen skip list in ga želimo spreminjati bi morali vedno preverjati kakšna je struktura skip lista, da bi lahko optimalno vstavili nov element. Poleg tega bomo skip list uporabljali samo, če imamo veliko elementov in več kot bo elementov večja je možnost, da bosta imela oba načina enako časovno zahtevnost.
Primeri uporabe so pa odgovorjeni v prejšnjem vprašanju.
V odgovor na Matija Lokar
Ali je rotacija desno-desno isto kot če izvedemo desno rotacijo dvakrat? če ni: Kakšna je razlika? če je: Zakaj ne bi potem obravnavali samo dve možnosti rotacij.
od Andreja Lapajne -
Pri lomljenu dreves si želimo obravnavani element spraviti v koren drevesa. Kot sva povedali, to storimo s pomočjo rotacij in to tako, da pogledamo v kakšnem odnosu sta obravnavani element, njegov oče, ter oče očeta. Glede na to se nato odločimo kateri tip rotacije bomo uporabili. Če bi v primeru desno - desne/ levo - leve rotacije uporabili dvakrat desno/levo rotacijo, obstaja nevarnost da pridemo do izorjenega drevesa, kar pa si ne želimo. Tudi sam postopek rotacije bi bil drugačen. Če uporabimo desno- desno rotacijo najprej zamenjamo vlogi očeta in njegovega očeta, nato pa še vlogi obravnavanega elementa in njegovega očeta. Če pa bi uporabili dvakrat desno rotacijo, pa bi najprej zamenjali vlogi obravnavanega elementa in očeta, nato pa še obravnavanega elementa in očeta očeta. Kot pa sem omenila, lahko v tem primeru pride do izrojevanja drevesa. Vedno ko lomimo drevo, pogledamo dva nivoja višje od obravnavanega elementa in se nato odločimo, katero rotacijo bomo uporabili.
V odgovor na Andreja Lapajne
Re: Ali nam je pri rotacijah pomembno, da bo drevo na koncu uravnoteženo?
od Andreja Lapajne -
Pri lomljenih drevesih je pomembno le, da niso izrojena in iskalna ob vsakem posegu v drevo.
Nič posebnega, le lomljenje drevesa bo vsebovalo večje število rotacij, da bomo obravnavani element spravili v koren drevesa.
V odgovor na Andreja Lapajne
Re: Kako to, da nočemo pri vstavljanju elementov ohranjati to, da je drevo iskalno.
od Andreja Lapajne -
Pri predstavitvi je lahko prišlo do kašne napake, pri vsaki operaciji (tj. vstavljanje elementa, brisanje elementa, iskanje elementa) moramo ohranjati iskalnost drevesa. Ko element vstavimo/ izbrišemo / poiščemo ga moramo nato z lomljenjem prestaviti v koren. Lomljenje pa je sestavljeno iz rotacij, ki poskrbijo, da drevo ohrani iskalnost.
V odgovor na Andreja Lapajne
Ne razumem, zakaj je lomljenje potrebno, tudi če iskalnega podatka ni v drevsu?
od hana kranjec kelbel -
Da ugotovimo, da podatka ni v drevesu moramo posegati vanj in opravljati operacije za iskanje podatka. Pri vsakem posegu moramo lomiti drevo, saj ravno to omogoči, da nikoli ne bo izrojeno.
Za lomljenja drevesa je značilno, da se lomijo ob vsakem posegu v drevo. S tem ko smo element v drevesu iskali smo posegali v drevo, kar pomeni, da je lomljenje potrebno. Ker iskanega elementa ni v drevesu, v koren premakanemo zadnje vozlišče na poti iskanja elementa.
V odgovor na Andreja Lapajne
Zakaj damo zadnje vozlišče v koren, če pri isknaju elementa ni v drevesu.
od hana kranjec kelbel -
Iskanje elementa je prav tako poseganje v drevo in rdeča nit lomljenja dreves je, da drevo nikoli ni izrojeno. S tem ko ga premaknemo v koren preprečimo izrojevanje. Prav tako pa z zaporedjem rotacij zagotovimo, da je drevo še vedno iskalno.
V odgovor na Andreja Lapajne
Kaj so prednosti in primeri uporabe te podatkovne strukture?
od hana kranjec kelbel -
Prednosti podatkovne strukture Lomljena drevesa je ravno v tem, da ne glede na to kakšen poseg naredimo v drevesu, drevo nikoli ne bo izrojeno.
V odgovor na hana kranjec kelbel
Re: Kaj so prednosti in primeri uporabe te podatkovne strukture?
od Matija Lokar -
No, osnovna ideja lomljenih dreves je tudi v tem, da ta PS poskuša upoštevati "empirično" dejstvo, da se pogosto zgodi, da je naslednji podatek, s katerim delamo pri podatkovni strukturi (iščemo, vstavljamo, brišemo ...) zelo podoben (ali celo isti) kot podatek, s katerim smo ravnokar delali. In zato je smiselno, da je "tekoči" podatek v korenu drevesa, saj bomo na ta način na naslednjem koraku zelo hitro prišli do želenega podatka.
Ali če sem še bolj konkreten ... Če nek algoritem potrebuje podatek 42, potem bo na naslednjem koraku verjetno potreboval 42 ali pa 43 ali pa 41. Zato je smisleno, da podatkovna struktura na nek način poskrbi, da bo do teh treh podatkov možen hiter dostop.
Ali če sem še bolj konkreten ... Če nek algoritem potrebuje podatek 42, potem bo na naslednjem koraku verjetno potreboval 42 ali pa 43 ali pa 41. Zato je smisleno, da podatkovna struktura na nek način poskrbi, da bo do teh treh podatkov možen hiter dostop.
V odgovor na Andreja Lapajne
Zakaj bi uporabljali lomljena drevesa namesto iskalnih dreves?
od hana kranjec kelbel -
Ker želimo uporabiti različne operacije v drevesu in naše drevo ima lahko veliko razliko med levim in desnim poddrevesom. Razlika med levim in desnim poddrevesom bi lahko privedla do izrojenega drevesa. Pri tej podatkovni strukturi z lomljenjem oziroma z zaporedjem rotacij ravno preprečimo izrojevanje drevesa ob enem pa ohranimo iskalnost drevessa.
V odgovor na hana kranjec kelbel
Re: Zakaj bi uporabljali lomljena drevesa namesto iskalnih dreves?
od Matija Lokar -
No, ena razlog je v izrojevanju, drugi pa tisti, ki je naveden pri komentarju prejšnjega vprašanja!
V odgovor na Andreja Lapajne
Re: Kako to, da nočemo pri vstavljanju elementov ohranjati to, da je drevo iskalno.
od Matija Lokar -
Verjetno je prišlo do nerazumevanja tudi zato, ker nista vsaj po eni prikazani rotaciji pokazali, da je dobljeno drevo vedno ostalo iskalno (in to v splošnem, ne le na konretnem primeru).
Odgovori na vprašanja na temo Bloomovega filtra
V odgovor na Martina Spasić
Če dobimo lažen pozitiven odgovor, kako lahko potem z zagotovostjo vrnemo, da je element v množici?
od Martina Spasić -
Bloomov filter se uporablja za preverjanje ali je element član množice. Nikoli z zagotovostjo ne trdimo, da je element v množici. Pri Bloomovemu filtru so lažno pozitivna ujemanja mogoča, lažno negativna pa ne – z drugimi besedami, edina dva odgovora, ki ju lahko s pomočjo Bloomovega filtra dobimo sta: 'morda je v nizu' ali pa 'zagotovo ni v nizu'.
Spomnimo
se, m predstavlja velikost bitnega polja. Potrebna velikost bitnega polja je odvisna od stopnje
lažne pozitivnosti ε, ki si jo lahko privoščimo. Čim večje je bitno
polje, manjša je verjetnost za lažno pozitivne rezultate in obratno, čim manjše
bitno polje imamo, večja je verjetnost, da dobimo lažno pozitivni odgovor. Pri željenem
ε in številu vstavljenih
elementov n, ob predpostavki, da
uporabimo optimalno število zgoščevalnih funkcij k, lahko izračunamo
velikost bitnega polja iz spodnje formule:
Pri
Bloomovemu filtru je pomembno, da so hash funkcije različne ter med sabo
neodvisne, oziroma da za isto vhodno vrednost vsaka hash funkcija vrne različno
izhodno vrednost. Optimalna vrednost hash funkcij se izračuna po formuli:
V odgovor na Martina Spasić
Bi lahko podali rezultate verjetnosti pri prvem primeru, ko ga je Martina reševala na tablo? tam kjer se je pri tabeli dolžine 5 pojavil lažno pozitiven rezultat?
od Martina Spasić -
Poglejmo si ta primer še enkrat. Velikost bitnega polja je m = 5, imamo dve hash funkciji in sicer:
- h1(x) = x mod 5
- h2(x) = (2x + 3) mod 4
Na začetku vstavimo dva elementa, x = 10 in x = 9.
Račun:
- h1(10) = 10 mod 5 → 0
- h2(10) = (2*10 + 3) mod 4 → 3
- h1(9) = 9 mod 5 → 4
- h2(9) = (2*9 + 3) mod 4 → 1
V bitnem polju pri indeksih 0, 1, 3 in 4 vrednosti bitov spremenimo iz 0 na 1.
Sedaj preverimo, ali je element 16 v naši množici. Izračunajmo njegovi hash vrednosti:
- h1(16) = 16 mod 5 → 1
- h2(16) = (2 * 16 + 3) mod 4 → 3
Kot vidimo na sliki, sta bita pri indeksih 1 in 3 že nastavljena na 1, zato bi naša poizvedba vrnila odgovor »element 16 je morda v nizu«. Mi pa vemo, da to ni res, saj smo vstavili le dva elementa in sicer 10 in 9, zato tukaj pride do lažne pozitivnosti.
Verjetnost lažno pozitivnih rezultatov lahko izračunamo po formuli
kjer je n število elementov, m velikost bitnega polja in k število hash funkcij.
V našem primeru je m = 5, k = 2 in n = 2, zato je stopnja lažne pozitivnosti enaka 34.86%.
Če pa bi bitno polje povečali le za 1 (m = 6), bi verjetnost lažno pozitivnega rezultata znašala 26.81%.
V odgovor na Martina Spasić
A morajo različne hash funkcije vrniti različne izhodne podatke za isti vhodni podatek?
od Ajla Sović -
Da, to je nujna zahteva pri Bloomovem filtru; lastnosti dobre hash funkcije so, da jo izračunamo hitro ter da vrne različne izhodne vrednosti za isti vhodni podatek.
V odgovor na Martina Spasić
Ali obstaja tudi kakšen algoritem za generiranje zgoščevalnih funkcij, ki so primerne za to podatkovno strukturo?
od Ajla Sović -
Pri generiranju zgoščevalnih funkcij moramo imeti v mislih hitro računanje vrednosti in zmanjšanje podvajanj izhoda. Za najboljše razmerje med hitrostjo in enakomernostjo rezultatov bi lahko uporabili program Murmur3 in SHA256.
Več o njihovi uporabi si lahko preberete na https://datagy.io/python-sha256/ in https://pypi.org/project/mmh3/.
V odgovor na Martina Spasić
Ali lahko samo z brisanjem elementov pridemo do lažnih negativnih izidov?
od Ajla Sović -
Kot primer zakaj odstranjevanje elementov v navadnem Bloomovem filtru ni mogoče, sva navedli dejstvo, da bi zaradi tega lahko prišlo do lažno negativnih izidov, ko bi bite na določenih indeksih iz 1 nastavili na 0.
Če bi pri iskanju elementa, za katerega vemo, da je v množici, dobili točno isto hash vrednost, kot jo je imel izbrisani element, bi poizvedba vrnila, da našega iskanega elementa zagotovo v množici ni, kar pa seveda ni res.
Sva mnenja, da je brisanje elementa edina pot do lažne negativnosti v navadnem Bloomovem filtru.