Haku listasta

Hyvin usein ohjelmia kirjoitettaessa pitää tutkia, löytyykö jokin haluttu arvo listasta ja jos löytyy, niin miltä indeksiltä. Tarkastellaan esimerkkinä tapausta, jossa listaan on tallennettu pelaajien eräästä pelistä saamat pisteet (kokonaislukuja). Halutaan selvittää, onko jollain pelaajalla määrätty pistemäärä ja jos on, niin mille listan indeksille tämä pistemäärä on tallennettu. Tässä kappaleessa katsotaan, miten haku voidaan toteuttaa.

Peräkkäishaku

Jos luvut on tallennettu listaan mielivaltaisessa järjestyksessä, ei ole sen tehokkaampaa vaihtoehtoa kuin käydä listan alkiot järjestyksessä läpi ja verrata jokaista listan alkiota etsittävään arvoon. Läpikäyntiä jatketaan niin kauan, kunnes etsitty arvo löytyy tai lista on käsitelty loppuun asti. Tällaista menettelyä kutsutaan peräkkäishauksi.

Alla on esimerkkiohjelma, jonka funktio hae_pistemaara etsii ensimmäisenä parametrina annetusta listasta toisena parametrina annetun arvon ja palauttaa sen indeksin listassa. Jos etsittyä arvoa ei löydy lainkaan, funktio palauttaa arvon -1 kertomaan sen, että arvoa ei löytynyt.

Esimerkkiohjelmassa on lisäksi funktio, jolla luetaan pisteet listaan, ja pääohjelma.

def lue_pisteet():
    lkm = int(input("Monenko pelaajan pisteet haluat antaa? "))
    pistelista = [0] * lkm
    i = 0
    while i < len(pistelista):
        pistelista[i] = int(input("Anna seuraavan pelaajan pisteet: "))
        i += 1
    return pistelista

def hae_pisteet(lista, arvo):
    for i in range(0, len(lista)):
        if lista[i] == arvo:
            return i
    return -1

def main():
    pisteet = lue_pisteet()
    haettava_arvo = int(input("Mita arvoa etsitaan? "))
    paikka = hae_pisteet(pisteet, haettava_arvo)
    if paikka == -1:
        print("Haettavaa arvoa ei loytynyt pistelistasta")
    else:
        print("Haettava arvo on listassa indeksilla", paikka)

main()

Jos haluttu arvo esiintyy listassa useamman kerran, esimerkin funktio etsii niistä vain ensimmäisen ja palauttaa sen indeksin. Jos halutaan hakea kaikki arvon esiintymät, voidaan sopivat indeksit kerätä esimerkiksi listaan ja palauttaa tämä lista. Näin on tehty seuraavassa esimerkissä.

def lue_pisteet():
    lkm = int(input("Monenko pelaajan pisteet haluat antaa? "))
    pistelista = [0] * lkm
    i = 0
    while i < len(pistelista):
        pistelista[i] = int(input("Anna seuraavan pelaajan pisteet: "))
        i += 1
    return pistelista

def hae_pisteet_kaikki(lista, arvo):
    tuloslista = []
    for i in range(0, len(lista)):
        if lista[i] == arvo:
            tuloslista.append(i)
    return tuloslista

def main():
    pisteet = lue_pisteet()
    haettava_arvo = int(input("Mita arvoa etsitaan? "))
    tuloslista = hae_pisteet_kaikki(pisteet, haettava_arvo)
    if len(tuloslista) == 0:
        print("Haettavaa arvoa ei loytynyt pistelistasta")
    else:
        print("Haettava arvo on listassa seuraavilla indekseilla")
        print(tuloslista)

main()

Pythonissa on myös valmiita rakenteita, joiden avulla voidaan tutkia, onko haluttu alkio annetussa listassa ja millä listan indeksillä alkio on. Operaattorin in avulla voidaan tutkia, onko haluttu alkio listassa, esimerkiksi ensimmäisen peräkkäishakuesimerkin pääohjelmassa olisi voitu kirjoittaa myös

if haettava_arvo in pisteet:
    print("Haettava arvo on pistelistassa")
else:
    print("Haettava arvo ei ole pistelistassa")

tai vaihtoehtoisesti

if haettava_arvo not in pisteet:
    print("Haettava arvo ei ole pistelistassa")
else:
    print("Haettava arvo on pistelistassa")

Haettavan alkion indeksin voi selvittää metodin index avulla. Kutsussa metodille annetaan käsiteltävä listamuuttuja jo ennen metodin nimeä. Listamuuttuja ja metodi erotetaan toisistaan pisteellä. Mahdolliset parametrit annetaan metodin nimen jälkeen sulkujen sisällä aivan samalla tavalla kuin funktioita kutsuttaessa.

Esimerkin aikaisemmin esitetyssä yhden arvon hakevan ohjelman pääohjelmassa voitaisiin kutsua index-metodia esimerkiksi seuraavasti sen sijaan, että käytetään omaa hae_pisteet-metodia:

paikka = pisteet.index(haettava_arvo)

Metodin index kutsuminen johtaa kuitenkin virhetilanteeseen ja ohjelman kaatumiseen siinä tapauksessa, että parametrina annettua arvoa ei löydy lainkaan listasta. Sen vuoksi on ensin syytä tarkistaa, onko haettava arvo listassa lainkaan, ja vasta tämän jälkeen kannattaa kutsua index-metodia, esimerkiksi seuraavasti:

if haettava_arvo not in pisteet:
    print("Haettava arvo ei ole pistelistassa")
else:
    paikka = pisteet.index(haettava_arvo)
    print("Haettava arvo on listassa indeksilla", paikka)

Vaikka Pythonin in-operaattoria ja index-metodia käytettäessä haku saadaan toteutettua yhdellä rivillä, ei näin tehty haku ole olennaisesti sen tehokkaampi kuin edellä kirjoitetun oman hae_pisteet-funktion käyttäminen. Pythonin in-operaattori ja index-metodi joutuvat käymään annetun listan läpi alkio kerrallaan ihan samalla tavalla kuin edellä esitetty oma funktio. Läpikäynti on vain piilotettu Pythonin omiin rakenteisiin eikä näy suoraan ohjelman lukijalle.

Binäärihaku

Jos ennakolta tiedetään, että listassa olevat alkiot ovat suuruusjärjestyksessä (joko pienimmästä suurimpaan tai päinvastoin), voidaan haku suorittaa paljon peräkkäishakua tehokkaammin.

Tarkastellaan tilannetta, jossa pisteet on tallennettu listaan nousevassa suuruusjärjestyksessä. Otetaan listan keskimmäinen alkio ja verrataan haettavaa arvoa siihen. Jos keskimmäinen alkio on suurempi, haettavan arvon on pakko olla listan alkuosassa (jos se on listassa). Vastaavasti jos keskimmäinen alkio on pienempi kuin haettava arvo, haettavan arvon on pakko olla listan loppuosassa.

Oletetaan, että keskimmäinen arvo on suurempi kuin haettava arvo. Siinä tapauksessa voidaan hakua jatkaa listan alkuosasta vastaavalla menetelmällä. Otetaan nyt alkuosan keskimmäinen arvo ja verrataan haettavaa arvoa siihen. Jos haettava arvo on pienempi, hakua voidaan jatkaa vastaavalla menetelmällä listan alkuosan alkuosasta (siis alkuperäisen listan ensimmäisestä neljänneksestä), ja jos haettava arvo on suurempi, hakua voidaan jatkaa listan alkuosan loppuosasta (siis alkuperäisen listan toisesta neljänneksestä). Näin jatketaan, kunnes tarkasteltavan hakualueen keskimmäinen alkio on sama kuin haettava arvo (jolloin haluttu arvo on löytynyt) tai hakualue on tyhjä (joilloin voidaan todeta, että haluttua arvoa ei ole listassa lainkaan).

Tällaista hakutapaa kutsutaan binäärihauksi. Kirjoitetaan binäärihaun periaate vähän täsmällisemmin:

Aloita niin, että hakualueena on koko alkuperäinen lista.
Jos hakualue on tyhjä eli hakualueen alaindeksi on suurempi kuin hakualueen yläindeksi, lopeta haun suoritus. Haettavaa arvoa ei ole listassa lainkaan. Muussa tapauksessa laske hakualueen keskimmäisen alkion indeksi. (Keskimmäinen tarkoittaa tässä sitä alkiota, joka on hakualueen keskimmäisessä paikassa.)
Vertaa haettavaa arvoa hakualueen keskimmäiseen alkioon:
- Jos haettava arvo ja keskimmäinen alkio ovat yhtäsuuret, haettava arvo on löytynyt. Lopeta haun suoritus ja palauta keskimmäisen alkion indeksi.
- Jos haettava arvo on pienempi kuin hakualueen keskimmäinen alkio, jatka kohdasta 2, mutta niin, että hakualueena on nykyisen hakualueen alkupuolisko.
- Jos haettava arvo on suurempi kuin hakualueen keskimmäinen alkio, jatka kohdasta 2, mutta niin, että hakualueena on nykyisen hakualueen loppupuolisko

Seuraavassa kuvassa on vielä esitetty, miten binäärihaku etenee, kun kuvassa olevasta listasta haetaan arvoa 14. Listan alapuolelle on merkitty alkioiden indeksit. Eri vaiheissa listasta on esitetty vain se osa, joka vielä kuuluu hakualueseen. Hakualueen keskimmäinen alkio on merkitty nuolella.

Seuraava funktio hakee binäärihaulla ensimmäisenä parametrina annetusta listasta toisena parametrina annetun arvon. Funktion sisällä pidetään muuttujien ala ja yla avulla tietoa siitä, mikä on hakualue milläkin hetkellä. Aluksi muuttujan ala arvoksi asetetaan nolla ja muuttujan yla arvoksi listan viimeisen alkion indeksi. Joka kierroksella lasketaan aina hakualueen keskimmäinen indeksi, jonka arvo tallennetaan muuttujaan keski. Tämän jälkeen verrataan haettavaa arvoa hakualueen keskimmäisellä indeksillä olevaan alkioon. Vertailun tuloksen mukaan joko poistutaan funktiosta tai muutetaan hakualueen ylä- tai alaindeksin arvoa.

def binaarihaku(lista, arvo):
    ala = 0
    yla = len(lista) - 1
    while ala <= yla:
        keski = (ala + yla) // 2
        if lista[keski] == arvo:  # arvo loytyi, lopetetaan
            return keski
        elif lista[keski] < arvo:
            ala = keski + 1  # jatketaan hakua loppuosasta
        else:
            yla = keski - 1  # jatketaan hakua alkuosasta
    return -1   # hakualue on tyhja, mutta arvoa ei loytynyt

Annettu funktio toimii oikein vain siinä tapauksessa, että parametrina annetussa listassa luvut ovat suuruusjärjestyksessä. Funktio ei mitenkään tarkista, pitääkö tämä paikkansa. Jos listan alkiot ovat satunnaisessa järjestyksessä, funktion paluuarvo voi olla täysin väärä eikä funktio anna mitään ilmoitusta siitä, että se ei toiminut oikein.

Binäärihaku on hyvin tehokas verrattuna peräkkäishakuun. Tarkastellaan esimerkiksi hakua listasta, jossa on miljoona alkiota. Peräkkäishakua käytettäessä joudutaan pahimmassa tapauksessa suoritamaan funktiossa hae_pisteet olevaa for-käskyä miljoona kierrosta (kaikki listan alkiot pitää käydä läpi, jos haettava alkio ei ole listassa tai on siinä viimeisellä indeksillä). Binäärihakua käytettäessä riittää, että while-käskyä suoritetaan pahimmassakin tapauksessa noin 20 kierrosta. Vielä paremmin ero tulee näkyviin, kun mietitään tilannetta, jossa listan koko kasvaa kahteen miljoonaan. Peräkkäishakua käytettäessä pahimmassa tapauksessa tarvittavien for-käskyn kierrosten määrä kasvaa miljoonalla, kun taas binäärihaussa while-käskyn kierrosten määrä kasvaa vain yhdellä.

Alla on vielä esimerkkinä koko ohjelma, jossa on ensin pyydetty käyttäjää antamaan pelipisteet suuruusjärjestyksessä ja sen jälkeen on käytetty binaarihaku-funktiota halutun arvon hakemiseen.

def lue_pisteet():
    print("Anna pelaajien pisteet suuruusjarjestyksessa pienimmasta alkaen.")
    lkm = int(input("Monenko pelaajan pisteet haluat antaa? "))
    pistelista = [0] * lkm
    i = 0
    while i < len(pistelista):
        pistelista[i] = int(input("Anna seuraavan pelaajan pisteet: "))
        i += 1
    return pistelista

def binaarihaku(lista, arvo):
    ala = 0
    yla = len(lista) - 1
    while ala <= yla:
        keski = (ala + yla) // 2
        if lista[keski] == arvo:  # arvo loytyi, lopetetaan
            return keski
        elif lista[keski] < arvo:
            ala = keski + 1  # jatketaan hakua loppuosasta
        else:
            yla = keski - 1  # jatketaan hakua alkuosasta
    return -1   # hakualue on tyhja, mutta arvoa ei loytynyt


def main():
    pisteet = lue_pisteet()
    haettava_arvo = int(input("Mita arvoa etsitaan? "))
    paikka = binaarihaku(pisteet, haettava_arvo)
    if paikka == -1:
        print("Haettavaa arvoa ei loytynyt pistelistasta")
    else:
        print("Haettava arvo on listassa indeksilla", paikka)

main()