ITI0140:Ülesanne 17

Jaanuse maavälised sõbrad

Eelmine teisipäev külastas meid tohutu tulnukatsivilisatsioon. Neile meeldis Tallinn väga, nii et nad otsustasid siia jääda. Jaanus käis reedel väljas ja sai mitme tulnukaga sõbraks. Jama on vaid selles, et tulnukaid on nii palju, et Jaanus ei leia oma sõpru enam üles. Ta tahab, et sa katsetaksid erinevaid meetodeid ta sõprade leidmiseks, et teada, millist meetodit peaks millal kasutama.

Peate realiseerima kolm erinevat otsingualgoritmi.

1. Lineaarne otsing Käite kõik tulnukad läbi, ja kontrollite kas tulnuka nimi on võrdne otsitavaga, kui on, siis tagastate tulnuka.

2. Ühekordse sorteerimisega kahendotsing Sorteerite tulnukad nime järgi (üks kord), ja kõigi otsitavate tulnukate jaoks realiseerite kahendotsingu sorteeritud tulnukate peal.

3. Mitmekordse sorteerimisega kahendotsing Iga otsitava tulnuka jaoks sorteerite tulnukad ära ja realiseerite kahendotsingu.

Kui algoritmid on realiseeritud, tuleb nende efektiivsust mõõta. Selleks võiks kasutada timeit moodulit, mille dokumentatsiooni leiab siit: https://docs.python.org/3.4/library/timeit.html

Mõõtmisteks anname teile mooduli alienutils.py, kust leiab klassi AlienGenerator. Looge uus objekt sellest klassist ja kasutage selle meetodeid tulnukate saamiseks. AlienGenerator-itel on kolm meetodit:

gen = AlienGenerator()
alien_amount = 50000
aliens = gen.get_aliens(alien_amount) # loob listi, kus on 50000 tulnukat.
search_alien = next(gen.get_search_aliens())
#get_search_aliens on generaator, mis genereerib järjest otsitavaid tulnukaid.
gen.reset()
#algsätestab generaatori seisundi, et mõõtmised ausad oleksid.

Mõõtmiseid võiks teha erinevate kogustega , nt 10 .. 100 .. 1000 .. 10000 jne, ühtlasi võiks mõõtmisi teha iga suuruse kohta mitu korda, kasutades järjest get_search_aliens-ist tulevaid väärtuseid. Iga algoritmi juures tuleks kõigepealt algsätestada generaator, või luua uus, et oleks kindel, et kõik mõõtmised toimuvad samade andmetega (et need oleks ausad).

Kui mõõtmised on tehtud, tuleks algoritmide aegasid võrrelda graafikul, milleks võiks kasutada matplotlib-i. Kasutage kindlasti logaritmilist mõõteskaalat.