Luku 2.3: Tehtävä: Alkulukuja ja testausta
Tästä sivusta:
Pääkysymyksiä: Kuinka yksikkötestataan ohjelma?
Mitä käsitellään? Opitaan yksikkötestauksesta ja kerrataan Pythonin perusteita.
Mitä tehdään? Tutustutaan yksikkötestaukseen. Tutustutaan myös uusiin kirjastoihin niiden omien sivujen kautta.
Suuntaa antava vaativuusarvio: Keskivaikea lähinnä uusien asioiden vuoksi. Itse tehtävä ei lopulta ole kovin haastava.
Suuntaa antava työläysarvio: 1-2 tuntia
Pistearvo: S150
Bonus: +5 % omista pisteistä aikaisesta palautuksesta.
Intro
Hajautustaulu (Hash Table) on tietorakenne, johon voit halutessasi tutustua tarkemmin tietorakennekurssilla.
Tässä tehtävässä ei tarvitse toteuttaa hajautustaulua vaan vain osata lukea kuinka sellainen toimii ja sitten testata lähes valmista hajautustaulun toteutusta. Hajautustaulun sijaan testattava luokka voisi olla mikä tahansa. Taulumme tukee seuraavia operaatioita:
- Uuden alkion lisäys
- Alkion poisto
- Alkion haku
- Uudelleenhajautus
Taustoja: Mikä on hajautustaulu? (Epäformaali johdanto)
Taulukko hakurakenteena
Puhutaanpa ensin taulukosta. Taulukko on rakenne, johon voi laittaa haluamaansa dataa tietyn haluamansa indeksin kohdalle. Taulukosta voi vastaavasti hakea tuon tiedon käyttämällä indeksiä.
Kuvitellaan että haluaisimme tehdä tietojärjestelmän tälle kurssille, jonka avulla opiskelijalle voi antaa pisteitä opiskelijanumeroa indeksinä käyttäen. Pistetään opiskelijat taulukkoon - jokainen oman opiskelijanumeronsa kohdalle. Aallolla:lla on käytössä viisinumeroiset opiskelijanumerot, joten kunkin opiskelijan tiedot voisi sijoittaa taulukkoon jossa on satatuhatta paikkaa.
opiskelijat = [None] * 100000
Anteeksi? Kurssillahan on vain parisataa opiskelijaa, joten taulukosta on käytössä vain 0.2%. Ei vaikuta oikein tehokkaalta tilankäytöltä. Toisaalta tiedon kyllä saa nopeasti. Olisiko mahdollista saada viittaus opiskelijaolioon yhä nopeasti, mutta käyttää paljon vähemmän tilaa?
Voisiko opiskelijat vain laittaa taulukkoon peräkkäin järjestykseen opiskelijanumeron mukaan? tällaisesta järjestetystä taulukosta saa kyllä tiedon suht’ nopeasti etsittyä, mutta opiskelijoiden poistaminen ja lisääminen vaatii pahimmillaan kaikkien muiden opiskelijoiden siirtämistä taulukossa.
Hajautus
Hajautuksen idea on ottaa suuri avainavaruus (100000) ja “puristaa” se kasaan niin että tauluun laitettavat alkiot saadaan sijoitettua pienempään tilaan. Vaikka tilaa varaisi 2,5 kertaa tallennettavien alkioiden määrän, olisi tilankäyttö esimerkissämme 200 kertaa tehokkaampaa.
opiskelijat = [None] * 503
Kuinka avaimet sitten sijoitetaan pienempään tauluun? Yksinkertainen idea voisi olla että opiskelijanumero jaetaan taulukon koolla ja jakojäännös kertoo sijoitettavan alkion paikan.
hash_value = student_number % len(opiskelijat)
Jos opiskelijanumerot ovat jakautuneet tasaisesti, jakojäännös levittää kurssilla olijoiden opiskelijanumerot tasaisesti pienemmän taulukon indekseille. On kuitenkin selvää, että useampi alkio tulee kuvautumaan samoille indekseille. Tätä kutsutaan törmäykseksi. Menetelmiä, joilla tämä ratkaistaan on useita. Tässä harjoituksessa tutkittava luokka käyttää kaksoishajautusta. Tässä menetelmässä ensimmäinen kokeiltu paikka lasketaan yhdellä funktiolla ja jos paikka on jo käytössä, niin lasketaan toisella funktiolla arvo jonka välein kokeillaan uudelleen. Esim:
# olkoon toinen kaava vaikka (1 + student_number % 7)
place = (student_number + (k * (1 + student_number % 7))) % len(opiskelijat)
| Haku: | Kun etsitään alkiota, lasketaan kaavalla paikkoja kunnes vastaan tulee täysin käyttämätön paikka tai oikea alkio löytyy. Matkan varrella voi olla myös merkkejä käytössä olleista paikoista. |
|---|---|
| Lisäys: | Kun sijoitetaan alkioita kelpaa täysin käyttämättömän paikan lisäksi myös aiemmin käytössä ollut paikka. Tällaisia paikkoja syntyy kun alkioita poistetaan hajautusrakenteesta. Jos poistettavan alkion kohdalle ei jäisi mitään merkkiä, ei alkioita etsivä rutiini löytäisi niitä, koska se keskeyttäisi liian aikaisin. |
| Poisto: | Poistaminen on aluksi samanlainen kuin haku. Jos alkio löytyy, laitetaan sen tilalle merkki
(Hashable.DELETED) siitä että paikka oli käytössä, jotta hakurutiini pääsee paikan ohi. |
| Rehash: | Jos taulussa oleva käyttämätön tila käy liian vähiin, alkaa taulu toimimaan huonosti. Tällaisessa tilanteessa suoritetaan ns. uudelleenhajautus (rehash), jossa kaikki taulukon alkiot lisätään yksi kerrallaan suurempaan tauluun. |
Esimerkki
Sijoitetaan tauluun jossa on 11 paikkaa kolme pupua jotka on numeroitu 30, 49 ja 16. Sijoittamiskaava on
place = (number + (k * (1+ number % 7))) % 11) (30 menee paikkaan 8 ja 49 paikkaan 5) nyt
pupua 16 lisättäessä kokeillaan ensin varattua paikkaa 5, sitten varattua paikkaa 11 ja vasta lopuksi vapaata
paikkaa 0.
Poistetaan nyt pupu numero 30 ja yritetään sitten löytää pupu numero 16. Ylempi allaolevista kuvista esittää kolmannen pupun lisäämisen (kokeillaan paikkoja 5, 8 ja 0), alempi pupun 16 etsimisoperaation (etsitään paikoista (5, 8 ja 0). Poistuneen pupun kohdalla on “haamu”.
Vinkki: Googlen laskin
Jos jakojäännösten laskeminen tuntuu työläältä, niin pupua numero 16 lisättäessä kokeillut paikat saa hakemalla googlesta seuraavia rivejä :
“(16 + 0 * ( 1 + 16 mod 7)) mod 11”.
“(16 + 1 * ( 1 + 16 mod 7)) mod 11”.
“(16 + 2 * ( 1 + 16 mod 7)) mod 11”.
Lisää tietoa
Paremman käsityksen algoritmin toiminnasta saa kun käy tutkimassa luokan DoubleHash koodia. Koodin pitäisi olla sen verran yksinkertainen että algoritmit pystyy ymmärtämään ylläolevan selostuksen avulla.
Tehokkuudesta
Selityksen perusteella tietorakenteen toiminta voi kuulostaa monimutkaiselta, mutta hajautustaulun lisäys,
poisto ja haku ovat kaikki käytännössä erittäin tehokkaita operaatioita. Python tarjoaa kaksi valmista toteutusta:
luokat dictionary ja set. Näitä tullaan hyödyntämään seuraavilla harjoituskierroksilla.
Tehtävänanto
Lue molemmat PyUnit-ohjeet, mikäli et vielä ole lukenut niitä. Halutessasi tee Eclipseen projekti jossa PyUnit:ia on helppo suorittaa.
Tehtävänanto löytyy A+:sta.
Huom!
Muutoksia voi vielä tulla.
`
`