Chapter 15: Hakualgoritmit

Hakualgoritmit ovat tärkeitä ja yleisiä operaatioita tietojenkäsittelyssä. Hakuja tehdään esimerkiksi yksittäiseltä websivulta näppäinyhdistelmällä ctrl+f tai haku tehdään käyttäjän antaman hakuehdon mukaisesti webserveriltä ja palautetaan käyttäjän kyselyn mukainen tieto.

Tiedon hakuun on monta eri tapaa. Google on luonut tiedonhakuun perustuen miljardiluokan liiketoiminnan. Tässä kappaleessa esitetään kaksi yksinkertaista hakualgoritmia, lineaarinen haku ja binaarihaku.

15.1 Tiedoston lukeminen

Ennen kuin selvitämme hakualgoritmeja tarkemmin, katsotaan se, miten tietoa luetaan tiedostoista. Tiedostosta lukeminen on paljon tehokkaampaa kuin kirjoittaa syötettä aina uudelleen ja uudelleen.

Kuvitellaanpa tilanne, jossa ohjelman pitää nopeasti löytää tiedostosta tietyn pahiksen nimi. Aluksi tarvitaan tiedosto, jossa nimet ovat. Voit ladata oheisen tekstitiedoston omalle koneellesi:
http://ProgramArcadeGames.com/chapters/16_searching/super_villains.txt
Tekstitedostossa on nine.frenchboys.net websivustolla generoituja satunnaisia nimiä. Tosin sivuston nimigeneraattori ei taida olla enää käytössä.

Tallenna tiedosto omaan kansioosi.

Luo samaan kansioon super_villains.txt kanssa seuraava python-ohjelma ja suorita se:

file = open("super_villains.txt")

for line in file:
    print(line)

Ohjelmassa on vain yksi uusi komento open. Koska komento on sisäänrakennettu, kuten print, ei tarvita import lausetta. Koska open-funktion dokumentaatio on varsin tekninen, sitä ei tässä kohtaa ole syytä tarkastella enempää. Dokumentaatio löytyy tarvittaessa oheisesta linkistä Python documentation.

Yllä olevassa ohjelmassa on pari puutetta, mutta se on selkeä esimerkki tiedoston lukemisesta. Rivin 1 open-komento avaa tiedoston lukua varten. Tiedoston nimi kirjoitetaan lainausmerkkeihin. Uusi muuttuja file on ns objektityyppinen muuttuja, joka viittaa luettavaan tiedostoon. Rivillä 3 on tavallinen for silmukka, jossa luetaan tiedosto rivi riviltä. Muuttujan file voisi ajatella olevan taulukko, jonka alkiot ovat rivejä. line muuttuja saa arvoikseen rivin kerrallaan, kun silmukkaa käydään läpi.

Kokeile ajaa ohjelma. Tiedosto tulostuu harmillisesti tupla riviväleillä. Tämä johtuu siitä, että jokainen tiedostosta muuttujaan line luettuihin riveihin sisältyy mukaan rivinvaihtomerkki. Muistat, että rivinvaihto (CR ja LF) merkki esitettiin kappaleessa 1. print lause sisältää myös rivinvaihdon, joten tuloksena on tuplamäärä rivinvaihtoja.

Toinen ongelma on, että tiedosto avataan, mutta sitä ei suljeta. Tämä ongelma ei ole yhtä näkyvä, mutta se on kuitenkin tärkeä. Windows järjestelmässä voidaan avata useita tiedostoja luettavaksi samanaikaisesti. Samaa tiedostoa ei kuitenkaan voida avata luettavaksi kuin yhdelle ohjelmalle kerrallaan. Jos tiedostoa ei lukemisen jälkeen suljeta, sitä ei voida lukea millään muullakaan ohjelmalla. Tiedoston sulkeminen on tärkeää, jotta Windows järjestelmä 'tietää' tiedoston olevan muiden ohjelmien käytettävissä. Päivitetään siis ohjelmamme seuraavanlaiseksi:

file = open("super_villains.txt")

for line in file:
    line = line.strip()
    print(line)

file.close()

Nyt ohjelma toimii paremmin. Siinä on kaksi lisäystä. Rivillä 4 kutsutaan strip metodia, joka on String luokan metodi ja se palauttaa tekstirivistä uuden merkkijonon ilman rivinvaihtoja ja lopussa olevia välilyöntejä. Metodi ei muuta alkuperäisen merkkijonon sisältöä, vaan se luo uuden merkkijonon. Seuraava ohjelmarivi ei toimisi:

line.strip()

Metodin strip palauttama merkkijono pitää sijoittaa johonkin muuttujaan, kuten edellä rivillä 4 tehtiin.

Toinen lisäys on tehty rivillä 7. Tämä rivi sulkee tiedoston ja vapauttaa sen muiden ohjelmien käyttöön.

15.2 Luetaan tiedosto taulukkoon

Tiedoston sisällön lukeminen taulukkoon helpottaa tietojen käsittelyä ohjelmassa. Taulukkoon lukeminen onnistuu seuraavalla koodilla:

# Luetaan tiedosto levyltä nimilistaan (yksiulotteiseen taulukkoon)
file = open("super_villains.txt")

name_list = []
for line in file:
    line = line.strip()
    name_list.append(line)

file.close()

Ohjelmassa yhdistetään tiedoston lukeminen ja tyhjän taulukon luominen. Tietojen lisääminen tyhjään taulukkoon käsiteltiin edellä kappaleessa 7. Luetun tiedoston pituus voidaan tarkistaa tulostamalla listan pituus (alkioiden määrä):

print( "There were",len(name_list),"names in the file.")

Ja sitten voidaan tulostaa listan kaikki alkiot:

for name in name_list:
    print(name)

Ennen kuin jatkat eteenpäin, varmista, että ymmärrät tiedostojen lukemisen.

15.3 Lineaarihaku

Jos ohjelmassa on tallennettu tietoja taulukkoon, miten voidaan hakea tietyn arvon sisältävä alkio? Tämä onnistuu kahdella eri tavalla. Ensimmäinen tapa on käyttää lineaarihakua. Lineaarihaku aloittaa ensimmäisestä alkiosta ja vertaa sen arvoa hakuehtoon. Tätä jatketaan alkio kerrallaan kunnes ehdon täyttävä alkio löytyy tai lista loppuu.

15.3.1 Lineaarihaun algoritmi

# Linear search

key = "Morgiana the Shrew"

i = 0
while i < len(name_list) and name_list[i] != key:
    i += 1

if i < len(name_list):
    print( "The name is at position", i)
else:
    print( "The name was not in the list." )

Lineaarihaku on melko yksinkertainen. Rivillä 2 alustetaan silmukkalaskuri, joka askeltaa taulukon elementit yksi kerrallaan. Ensimmäisen alkion indeksi on 0, joten i asetetaan nollaksi.

Seuraava rivi on monimutkaisempi boolean ehdon yhdistelmä. Ohjelma kasvattaa while-silmukkaa indeksilaskurin i arvoa kunnes etsitty alkio löytyy tai lista loppuu. If-lauseessa varmistetaan, että silmukkalaskurin i arvo pienempi kuin listan pituus. Jos on, niin tämä arvo on löytyneen alkion indeksin arvo ja tulostetaan if-lohkossa tämä paikka. Else-haara suoritetaan vain, jos haettavaa arvoa ei löytynyt listasta.

Silmukkaehdossa tulee tarkistaa ensin, onko listan loppu saavutettu. Ellei tätä tarkistusta tehdä ennen hakuarvon tarkistusta, tulee silmukasta virhe listan lopussa. Muistathan, että lista-alkioiden indeksit alkavat 0:sta ja päättyvät indeksiin n-1. Siksi, jos i silmukkalaskurin arvo on yhtä suuri kuin listan viimeinen indeksi, päättyy while-lauseen suoritus. Jos i:n arvo on pienempi, niin hakuarvo on löydetty.

15.4 Lineaarihaun muunnelmia

Muuntelemalla lineaarihaun algoritmia saadaan aikaiseksi hyödyllisiä yleiskäyttöisiä algoritmeja. Esimerkiksi, jos meillä olisi lista avaruusolioista. Haluaisimme etsiä listasta vihreitä olioita. Vai ovatko kaikki oliot vihreitä? Mitkä olioit ovat vihreitä?

Aluksi määrittelemme avaruusolio- luokan Alien

class Alien:
    """ Class that defines an alien"""
    def __init__(self, color, weight):
        """ Constructor. Set name and color"""
        self.color = color
        self.weight = weight

Seuraavaksi teemme funktion, jolla voidaan tarkistaa, löytyykö etsityn ominaisuuden 'oliota'. Tässä tapauksessa siis vihreää. Oletetaan, että väri on esitetty merkkijonona ja muutetaan merkkijono ISOIKSI kirjaimiksi, jolloin saadaan poistettua erikokoisten kirjainten eroavaisuudesta johtuva epätarkkuus.

def has_property(my_alien):
    """ Check to see if an item has a property.
    In this case, is the alien green? """
    if my_alien.color.upper() == "GREEN":
        return True
    else:
        return False

15.4.1 Onko vähintään yhdellä oliolla kysytty ominaisuus?

Onko vähintään yksi oavaruusotus vihreä? Alla on perusalgoritmi tämän tarkistamiseen:

def check_if_one_item_has_property_v1(list):
    """ Return true if at least one item has a
    property. """
    i = 0
    while i < len(list) and not has_property(list[i]):
        i += 1

    if i < len(list):
        # Found an item with the property
        return True
    if i == len(list):
        # There is no item with the property
        return False

Tämä voidaan toteuttaa myös for silmukalla. Tässä silmukan suorittaminen lopetetaan return lauseella, kun etsitty olio löydetään. Koodi on saatu varsin lyhyeksi, mutta jotkut koodaajaat eivät suosi tällaista tapaa. Algoritmin lopettaminen ennenaikaisesti silmukassa olevilla return tai break lauseilla ei ole kaikkien koodaajien mieleen. Usein nämä asiat ovat koodaajan omien mieltymysten mukaisesti toteutettavissa.

def check_if_one_item_has_property_v2(list):
    """ Return true if at least one item has a
    property. Works the same as v1, but less code. """
    for item in list:
        if has_property(item):
            return True
    return False

15.4.2 Onko kaikilla olioilla kysytty ominaisuus?

Ovatko kaikki avaruusoliot vihreitä? Seuraava koodi on pitkälti samanlainen kuin edellä esitetty. Voit yrittää selvittää eron koodien välillä ja selvittää syyn tähän eroavaisuuteen.

def check_if_all_items_have_property(list):
    """ Return true if at ALL items have a property. """
    for item in list:
        if not has_property(item):
            return False
    return True

15.4.3 Luodaan lista niistä olioista, joilla on kysytty ominaisuus?

Miten saadaan tehtyä lista niistä avaruusolioista, joilla on kysytty ominaisuus? Tarvittava koodi saadaan yhdistämällä aiemmin esitettyjä koodeja. Alkioiden lisääminen listaan käsiteltiin edellä kappaleessa 7.

def get_matching_items(list):
    """ Build a brand new list that holds all the items
    that match our property. """
    matchingList = []
    for item in list:
        if has_property(item):
            matchingList.append(item)
    return matchingList

Miten kaikki edellä oleva koodit saadaan testattua? Alla on koodi, jolla testaus voidaan tehdä:

alien_list = []
alien_list.append(Alien("Green", 42))
alien_list.append(Alien("Red", 40))
alien_list.append(Alien("Blue", 41))
alien_list.append(Alien("Purple", 40))

result = check_if_one_item_has_property_v1(alien_list)
print("Result of test check_if_one_item_has_property_v1:", result)

result = check_if_one_item_has_property_v2(alien_list)
print("Result of test check_if_one_item_has_property_v2:", result)

result = check_if_all_items_have_property(alien_list)
print("Result of test check_if_all_items_have_property:", result)

result = get_matching_items(alien_list)
print("Number of items returned from test get_matching_items:", len(result))

Kokonaan toimiva esimerkki löytyy tästä:
programarcadegames.com/python_examples/show_file.php?file=property_check_examples.py

Näitä yleisiä koodiesimerkkejä voidaan käyttää osanan laajempien ohjelmien ratkaisuja, esimerkiksi osoitteen hakemiseen asiakaslistasta.

15.5 Binaarihaku

Lineaarihakua nopeampi haku on binary search. Binaarihakua voidaan esittää klassisella numeron arvauspelillä, “arvaa luku väliltä 1 ja 100”. Tehdään esimerkki helpommaksi esittää ja valitaan arvattavaksi lukualueeksi 1 ja 128. Lukualueeseen kuuluvat myös 1 ja 128 ja ovat siis mahdollisia.

Jos arvaaja käyttäisi lineaarihakua, tulisi pelistä pitkäveteinen, kun numerot luetellaan peräkkäin yksi kerrallaan.

Guess a number 1 to 128: 1
Too low.
Guess a number 1 to 128: 2
Too low.
Guess a number 1 to 128: 3
Too low.
....
Guess a number 1 to 128: 93
Too low.
Guess a number 1 to 128: 94
Correct!

Useimmat käyttäisivät tässä binaarihakua, jolloin arvaus asetetaan sen mukaan, oliko luku yli vai alle arvauksen:

Guess a number 1 to 128: 64
Too low.
Guess a number 1 to 128: 96
Too high.
Guess a number 1 to 128: 80
Too low.
Guess a number 1 to 128: 88
Too low.
Guess a number 1 to 128: 92
Too low.
Guess a number 1 to 128: 94
Correct!

Jokaisella arvauskerralla arvaaja saa puolitettua haettavan lukualueen.

Binaarihaussa arvaus asetetaan lukualueen puoleen väliin alarajasta ja ylärajasta. Tietokone tai arvaaja poimii lukualueen keskikohdan luvun. Huomaa, että lukujen tulee olla järjestetty suuruusjärjestykseen. Ensimmäisen arvaus saadaan seuraavalla kaavalla:

Alaraja 0n 1 ja yläraja on 128, keskikohta löytyy $\dfrac{1+128}{2} = 64.5$.

Arvataan väliltä 1 - 128: 64
Liian pieni.

Saadaan uusi alaraja 65, yläraja on edelleen 128, keskikohta on $\dfrac{65+128}{2} = 96.5$.

Tehdään uusi arvaus: 96
Liian suuri.

Alaraja säilyy 65, uusi yläraja on 95, keskikohta $\dfrac{65+95}{2} = 80$.

Arvataan: 80
Liian pieni.

Alaraja on nyt 81, yläraja on edelleen 95, keskikohta $\dfrac{81+95}{2} = 88$.

Arvaus: 88
Liian pieni.

Alarajaksi asetetaan 89, ylärjana on 95, keskikohta $\dfrac{89+95}{2} = 92$.

Uusi arvaus: 92
Liian pieni.

Alarajaksi 93, ylärajana 95, puoliväli on $\dfrac{93+95}{2} = 94$.

Arvataan: 94
Osui oikein!

Binaarihaku vaatii merkittävästi vähemmän arvauksia. Huonoimmassa tapauksessa tarvitaan seitsemän arvauskertaa lukuväliltä 1 ja 128. Yksi arvauskerta enemmän laajentaa lukualueen 256. 9 arvausta olisi lukualueelta 1 ja 512 tarvittava maksimimäärä. 32:lla arvauksella saataisin luku selville lukuväliltä 1 - 4.2 miljardia.

Lukulistan suuruus ja arvausten määrän yhteys saadaan selville seuraavalla potenssikaavalla, $n=x^{g}$ jossa $n$ on listan koko ja $g$ on arvausten lukumäärä. Esimerkiksi:
$2^7=128$ (7 arvausta tarvitaan 128 luvun listalle)
$2^8=256$
$2^9=512$
$2^{32}=4,294,967,296$

Jos tiedossa on lukulistan (probleeman) koko, saadaan tarvittavien arvauksien määrä log funktiolla. Tarkkaan ottaen, log base 2, eli kaksikantaisella logaritmilla. Jos kantaa ei määritetä, niin oletuksena useimmat käyttävät luonnollista logaritmia $e \approx 2.71828$, joka ei tässä kelpaa. Kaksikantaisella logaritmilla saadaan esimerkiksi seuraavat arvausten määrät:
$log_2 128 = 7$
$log_2 65,536 = 16$

Nyt matematiikasta takaisin koodaamiseen. Binaarihaun algoritmi on monimutkaisempi kuin lineaarihaun:

# Binary search
key = "Morgiana the Shrew"
lower_bound = 0
upper_bound = len(name_list)-1
found = False
while lower_bound <= upper_bound and not found:
    middle_pos = (lower_bound+upper_bound) // 2
    if name_list[middle_pos] < key:
	    lower_bound = middle_pos + 1
    elif name_list[middle_pos] > key:
	    upper_bound = middle_pos - 1
    else:
        found = True

if found:
    print("The name is at position", middle_pos)
if not found:
    print("The name was not in the list.")

Rivillä 3 asetetaan listan alarajaksi nolla. Rivillä 4 ylärajaksi asetetaan listan pituus -1. Esimerkikiksi 100 luvun listassa viimeisen alkion indeksi on 99.

Boolean muuttuja rivillä 5 ilmaisee etsityn alkion löytymisen.

While-silmukan ehdossa tarkistetaan onko lista käyty loppuun tai onko etsitty alkio löytynyt.

Silmukassa haetaan listan keskikohta. Jotta vältetään keskikohdaksi saatava desimaalilukuarvo, esim. 64.5, käytetään jakolaskussa operaattoria // (esitettiin kappaleessa 5). Tämä on samanlainen kuin / operaattori, mutta se palauttaa tuloksena kokonaisluvun. Esimerkiksi, 11 // 2 antaa tuloksen 5, eikä 5.5.

Seuraavaksi if-lauseilla testataan, onko arvaus liian suuri tai liian pieni vai onko se oikea. Jos arvaus oli liian pieni, siirretään alarajaa ylemmäs ja suoritetaan testaus uudelleen. Jos arvaus oli liian suuri, vaihdetaan ylärajaksi arvauksesta edellinen luku. Jos luku löytyy, found asetetaan arvoon True ja haku lopetetaan.

100 alkion listasta haettaessa lineaarihaulla, arvaus osuu oikeaan keskimäärin 50:llä arvauksella. Binaarihaulla päästään oikeaan tulokseen maksimissaan vain seitsemällä arvauksella. Tässä yhteysessä keskimääräistä voidaan samalla pitää huonoimpana vaihtoehtona.

15.6 Review

15.6.1 Multiple Choice Quiz

Klikkaa tästä monivalintatehtävään.

15.6.2 Short Answer Worksheet

Klikkaa tästä kappaleen kertaustehtäviin.

15.6.3 Lab

Klikkaa tästä ohjelmointitehtäviin.

You are not logged in. Log in here and track your progress.