Kaikki materiaali (I-osa)

1. Johdanto

Kurssin Tietorakenteet ja algoritmit tavoitteena on syventää ohjelmointitaitoa ja opettaa ajattelua ja tekniikoita, joiden avulla voi toteuttaa ohjelmia, jotka toimivat oikein ja tehokkaasti kaikissa tilanteissa.

Tutustumme kurssin aiheisiin Python-kielen kautta, mutta kurssin asiat pätevät muissakin ohjelmointikielissä. Kurssilla on paljon ohjelmointia, minkä lisäksi käsittelemme myös aiheeseen liittyvää teoriaa.

Mikä on algoritmi?

Algoritmi (algorithm) on menetelmä, jonka avulla voidaan ratkaista jokin laskennallinen tehtävä. Kun algoritmi toteutetaan ohjelmointikielellä, se voidaan suorittaa tietokoneella.

Algoritmin syöte (input) tarkoittaa, mitä lähtötietoja algoritmille annetaan. Algoritmin tuloste (output) puolestaan tarkoittaa, minkä vastauksen algoritmi antaa suorituksen jälkeen. Pythonissa algoritmi voidaan toteuttaa funktiona, jolloin algoritmin syöte annetaan funktion parametreina ja algoritmin tuloste on funktion palautusarvo.

Tarkastellaan esimerkkinä tehtävää, jossa algoritmille annetaan lista lukuja ja algoritmin pitää laskea, moniko luku on parillinen. Esimerkiksi jos lista on [5, 4, 1, 7, 9, 6], haluttu vastaus on 2, koska luvut 4 ja 6 ovat parillisia.

Tämä tehtävä voidaan ratkaista algoritmilla, joka käy läpi listan luvut ja pitää muuttujassa yllä tietoa, moniko luku on parillinen. Algoritmi voidaan toteuttaa seuraavasti Pythonilla funktiona count_even:

def count_even(numbers):
    result = 0
    for x in numbers:
        if x % 2 == 0:
            result += 1
    return result

Funktiota voidaan testata seuraavan pääohjelman avulla:

print(count_even([1, 2, 3])) # 1
print(count_even([2, 2, 2, 2, 2])) # 5
print(count_even([5, 4, 1, 7, 9, 6])) # 2

Tämä pääohjelma testaa funktion toimintaa kolmella eri listalla. Jokaisen testin yhteydessä kommentissa lukee, mikä vastaus testistä pitäisi tulla. Kun ohjelma suoritetaan, sen tulostus on seuraava:

1
5
2

Tämän perusteella vaikuttaa siltä, että funktio toimii halutulla tavalla eli olemme saaneet aikaan toimivan algoritmin tehtävään.

Mikä on tietorakenne?

Tietorakenne (data structure) on tapa pitää muistissa tietoa ohjelmassa. Pythonin perustietorakenne on lista, jonka lisäksi kielessä on muita valmiita tietorakenteita. Sopivien tietorakenteiden valinta on tärkeä osa algoritmien suunnittelua, koska tietorakenteet vaikuttavat paljon algoritmien tehokkuuteen.

Tutustumme tällä kurssilla moniin tietorakenteisiin ja niiden käyttötarkoituksiin algoritmien suunnittelussa. Käymme läpi Pythonin valmiita tietorakenteita, minkä lisäksi opimme toteuttamaan myös itse tietorakenteita, joita ei ole valmiina Pythonissa eikä muissa kielissä.

Algoritmin toteuttaminen

Minkä tahansa algoritmin pystyy toteuttamaan ohjelmoinnin perusasioiden avulla. Pythonissa tällaisia perusasioita ovat:

• muuttujat
• ehdot (if)
• silmukat (for, while)
• listat
• funktiot
• luokat

Näiden lisäksi ohjelmointikielissä on usein paljon muita ominaisuuksia, joiden avulla voi esimerkiksi tiivistää koodia mutta jotka eivät pohjimmiltaan muuta koodin toimintalogiikkaa. Näitä ominaisuuksia voi käyttää algoritmien toteuttamisessa, mutta niitä ilmankin pärjää mainiosti.

Tarkastellaan vielä äskeistä funktiota count_even, joka on toteutettu käyttäen ohjelmoinnin perusasioita:

def count_even(numbers):
    result = 0
    for x in numbers:
        if x % 2 == 0:
            result += 1
    return result

Tämän funktion voi toteuttaa tiiviimmin käyttämällä Python-kielelle erityistä generaattorilauseketta:

def count_even(numbers):
    return sum(x % 2 == 0 for x in numbers)

Tässä sum-funktion sisällä on generaattorilauseke, joka laskee jokaiselle listan alkiolle x lausekkeen x % 2 == 0 arvon (True tai False). Kun nämä arvot lasketaan yhteen, jokainen True-arvo tulkitaan luvuksi 1, jolloin arvojen summa on yhtä suuri kuin parillisten lukujen määrä.

Vaikka jälkimmäinen funktio on paljon lyhyempi, se kuitenkin tekee pohjimmiltaan saman asian kuin ensimmäinen funktio. Molemmat funktiot käyvät läpi listan luvut ja laskevat yhteen parillisten lukujen määrän, eikä funktioissa ole eroa algoritmin toimintalogiikan kannalta.

Ensimmäisen funktion etuna on, että se on helpompi ymmärtää henkilölle, joka ei tunne Python-kielen erikoisominaisuuksia. Funktion voisi toteuttaa melko samalla tavalla esimerkiksi JavaScriptilla:

function countEven(numbers) {
    let result = 0;
    for (let x of numbers) {
        if (x % 2 == 0) result++;
    }
    return result;
}

Jälkimmäisen funktion etuna on, että se on tiiviimpi ja sen voi ajatella olevan enemmän Python-kielen tyylin mukainen. Vaikka ohjelmoinnin perusasiat riittävät kaikkeen, voi olla kiinnostavaa oppia myös kielten erikoisominaisuuksia.

Algoritmin tehokkuus

Saman tehtävän ratkaisemiseen on olemassa usein monia erilaisia algoritmeja, joiden tehokkuudessa voi olla eroja. Usein tavoitteena on löytää tehokas algoritmi, jonka avulla tehtävä voidaan ratkaista nopeasti.

Tarkastellaan tehtävää, jossa annettuna on lista lukuja ja tavoitteena on laskea, mikä on suurin ero kahden luvun välillä. Esimerkiksi kun lista on [3, 2, 6, 5, 8, 5], haluttu vastaus on 6, koska suurin ero on lukujen 2 ja 8 välillä.

Seuraavassa on kolme algoritmia tämän tehtävän ratkaisemiseen:

Algoritmi 1

def max_diff(numbers):
    result = 0
    for x in numbers:
        for y in numbers:
            result = max(result, abs(x - y))
    return result

Tämä algoritmi muodostuu kahdesta for-silmukasta, jotka käyvät läpi kaikki tavat valita listalta kaksi lukua. Algoritmi laskee lukujen eron abs-funktion (itseisarvo) avulla ja pitää muistissa tietoa, mikä on suurin löytynyt ero.

Algoritmi 2

def max_diff(numbers):
    numbers = sorted(numbers)
    return numbers[-1] - numbers[0]

Tämän algoritmin ideana on, että suurin ero kahden luvun välillä saadaan valitsemalla listan pienin ja suurin luku.

Algoritmi järjestää ensin listan sisällön sorted-funktion avulla. Tämän jälkeen pienin luku on listan alussa ja suurin luku on listan lopussa, joten algoritmin riittää palauttaa listan viimeisen luvun (indeksi -1) ja ensimmäisen luvun (indeksi 0) erotus.

Algoritmi 3

def max_diff(numbers):
    return max(numbers) - min(numbers)

Tässä on vielä toinen tapa toteuttaa äskeiseen ideaan perustuva algoritmi. Listan järjestämisen sijasta algoritmi käyttää funktioita min ja max, jotka palauttavat listan pienimmän ja suurimman alkion.

Tehokkuuden tutkiminen

Algoritmin tehokkuutta voidaan tutkia testiohjelmalla, joka antaa algoritmille tietyn syötteen ja mittaa algoritmin suoritusajan. Usein hyvä tapa on laatia testiohjelma niin, että se muodostaa halutun kokoisen syötteen satunnaisesti. Tämän avulla algoritmia voidaan testata helposti erikokoisilla syötteillä.

Seuraavassa on ohjelma, joka testaa funktion max_diff tehokkuutta:

import random
import time

def max_diff(numbers):
    ...

n = 1000
print("n:", n)
random.seed(1337)
numbers = [random.randint(1, 10**6) for _ in range(n)]

start_time = time.time()
result = max_diff(numbers)
end_time = time.time()

print("result:", result)
print("time:", round(end_time - start_time, 2), "s")

Muuttujassa n annetaan testissä käytettävän listan pituus. Funktio random.seed määrittää siemenluvun (tässä 1337), jonka ansiosta satunnaisluvut muodostetaan aina samalla tavalla. Tästä on hyötyä, kun testi suoritetaan useita kertoja, jolloin listan sisältö on aina sama. Ohjelma luo funktiolla random.randint listan, jossa on n satunnaista lukua väliltä \(1 \dots 10^6\).

Ohjelma mittaa funktion ajankäytön funktion time.time avulla. Funktio palauttaa sekunteina kuluneen ajan vuoden 1970 alusta alkaen. Kun tämä aika laitetaan talteen ennen funktion kutsua ja funktion kutsun jälkeen, aikojen erotus kertoo, montako sekuntia funktion suoritus vei aikaa. Aika pyöristetään kahden desimaalin tarkkuudelle funktiolla round.

Ohjelman suoritus voi näyttää seuraavalta:

n: 1000
result: 999266
time: 0.09 s

Tämä tarkoittaa, että algoritmin syötteenä oli 1000-kokoinen lista, algoritmi antoi tuloksen 999266 ja algoritmin suoritukseen meni aikaa 0.09 sekuntia.

Seuraava taulukko näyttää, paljonko äskeiset algoritmit veivät aikaa erikokoisilla syötteillä testikoneella:

Taulukosta näkee, että algoritmien tehokkuudessa on suuria eroja. Algoritmi 1 on hidas suurilla syötteillä, ja kaksi suurinta testiä jouduttiin keskeyttämään, koska suoritus vei liikaa aikaa. Algoritmit 2 ja 3 ovat sen sijaan tehokkaita myös suurilla syötteillä. Viimeinen testi tuo näkyviin eron myös algoritmin 2 ja 3 välille, vaikkakaan ero ei ole niin suuri kuin verrattuna algoritmiin 1.

Algoritmin analysointi

Algoritmin tehokkuutta voidaan analysoida laskemalla, montako askelta algoritmi suorittaa, kun sille annetaan tietyn kokoinen syöte. Usein voidaan ajatella, että jokainen koodissa oleva rivi vastaa yhtä algoritmin askelta.

Tarkastellaan esimerkkinä seuraavaa algoritmia, joka laskee, montako parillista lukua on annetussa listassa.

1
2
3
4
5
6
def count_even(numbers):
    result = 0
    for x in numbers:
        if x % 2 == 0:
            result += 1
    return result

Merkitään \(n\):llä listan numbers alkioiden määrää. Koska algoritmi käy listan sisällön läpi, algoritmin askelten määrä riippuu \(n\):stä.

• Algoritmi suorittaa kerran rivit 2 ja 6, koska ne ovat silmukan ulkopuolella.

• Algoritmi suorittaa \(n\) kertaa rivit 3 ja 4, koska ne suoritetaan jokaiselle listalla olevalle alkiolle.

• Algoritmi suorittaa rivin 5 vähintään \(0\) kertaa ja enintään \(n\) kertaa, riippuen siitä, mitkä listan alkiot ovat parillisia.

Tämän perusteella algoritmi suorittaa vähintään \(2n+2\) askelta ja enintään \(3n+2\) askelta. Askelten tarkka määrä riippuu siitä, montako parillista lukua listalla on.

Aikavaativuus

Usein ei ole tarvetta laskea tarkasti algoritmin askelten määrää, vaan riittää määrittää algoritmin aikavaativuus (time complexity). Tämä antaa suuruusluokan sille, montako askelta algoritmi suorittaa tietyn kokoisella syötteellä.

Aikavaativuus ilmoitetaan usein muodossa \(O(\cdots)\), jossa kolmen pisteen tilalla on muuttujan \(n\) sisältävä kaava, joka antaa ylärajan algoritmin askelten määrälle. Muuttuja \(n\) kuvaa syötteen kokoa. Esimerkiksi jos syötteenä on lista, \(n\) tarkoittaa listan kokoa, ja jos syötteenä on merkkijono, \(n\) tarkoittaa merkkijonon pituutta.

Aikavaativuus voidaan usein päätellä algoritmin askelten määrän kaavasta ottamalla huomioon vain kaavan nopeiten kasvava osa ja poistamalla vakiokertoimet. Esimerkiksi äskeisen algoritmin aikavaativuus on \(O(n)\), koska algoritmi suorittaa enintään \(3n+2\) askelta.

Tarkasti määriteltynä algoritmin aikavaativuus on \(O(f(n))\), jos voidaan valita vakiot \(c\) ja \(n_0\) niin, että algoritmi suorittaa aina enintään \(c f(n)\) askelta, kun \(n \ge n_0\). Esimerkiksi äskeisen algoritmin tapauksessa aikavaativuus on \(O(n)\), koska voidaan valita \(c=5\) ja \(n_0=1\). Tämä valinta on toimiva, koska \(3n+2 \le 5n\), kun \(n \ge 1\).

Tavallisia aikavaativuuksia ovat:

Silmukat koodissa

Käytännössä algoritmin aikavaativuus liittyy usein siihen, millaisia silmukoita algoritmin koodissa on.

Vakioaikaisuus

Jos algoritmissa ei ole silmukkaa vaan se suorittaa samat askeleet riippumatta syötteestä, algoritmin aikavaativuus on \(O(1)\).

Esimerkiksi seuraavan algoritmin aikavaativuus on \(O(1)\):

def middle(numbers):
    n = len(numbers)
    return numbers[n // 2]

Yksittäinen silmukka

Jos algoritmissa on yksi silmukka, joka käy läpi syötteen alkiot, algoritmin aikavaativuus on \(O(n)\).

Esimerkiksi seuraavan algoritmin aikavaativuus on \(O(n)\):

def calc_sum(numbers):
    result = 0
    for x in numbers:
        result += x
    return result

Algoritmin aikavaativuus on \(O(n)\), koska siinä on yksi silmukka, joka käy läpi syötteen alkiot.

Sisäkkäiset silmukat

Jos algoritmissa on kaksi sisäkkäistä silmukkaa, jotka käyvät läpi syötteen alkiot, algoritmin aikavaativuus on \(O(n^2)\).

Esimerkiksi seuraavan algoritmin aikavaativuus on \(O(n^2)\):

def has_sum(numbers, x):
    for a in numbers:
        for b in numbers:
            if a + b == x:
                return True
    return False

Yleisemmin jos algoritmissa on \(k\) sisäkkäistä silmukkaa, jotka käyvät läpi syötteen alkiot, algoritmin aikavaativuus on \(O(n^k)\).

Peräkkäiset osat

Jos algoritmissa on peräkkäisiä osia, algoritmin aikavaativuus on suurin yksittäisen osan aikavaativuus.

Esimerkiksi seuraavan algoritmin aikavaativuus on \(O(n)\):

def count_min(numbers):
    # osa 1
    min_value = numbers[0]
    for x in numbers:
        if x < min_value:
            min_value = x

    # osa 2
    result = 0
    for x in numbers:
        if x == min_value:
            result += 1

    return result

Algoritmin ensimmäinen osa käy läpi syötteenä annetun listan alkiot ja etsii listan pienimmän alkion. Tämän osan aikavaativuus on \(O(n)\).

Algoritmin toinen osa käy läpi syötteen uudelleen ja laskee, montako kertaa pienin alkio esiintyy listalla. Tämän osan aikavaativuus on \(O(n)\).

Koska kummankin osan aikavaativuus on \(O(n)\), algoritmin aikavaativuus on \(O(n)\).

2. Lista

Lista (list) on monikäyttöinen tietorakenne, joka on Python-kielen perustietorakenne. Lista soveltuu usein ohjelmassa käsiteltävän tiedon tallentamiseen, mutta toisaalta on tilanteita, joissa listan sijasta kannattaa käyttää muita tietorakenteita.

Tutustumme tässä luvussa Pythonin listan toteutukseen ja ominaisuuksiin. Kiinnitämme erityisesti huomiota listan operaatioiden aikavaativuuteen: mitkä listan operaatiot ovat tehokkaita ja milloin listaa kannattaa käyttää.

Lista muistissa

Tietokoneen muisti muodostuu peräkkäisistä muistipaikoista, joihin voidaan tallentaa tietoa. Jokaisella muistipaikalla on osoite, jolla siihen voidaan viitata. Muistiin tallennetaan tiedot, joita ohjelma käsittelee suorituksensa aikana.

Tarkastellaan esimerkkinä seuraavaa Python-ohjelmaa:

a = 7
b = -3
c = [1, 2, 3, 1, 2]
d = 99

Oletetaan, että ohjelmassa määritellyt muuttujat ja lista on tallennettu muistiin osoitteesta 100 alkaen. Seuraavassa on yksinkertaistettu esitys siitä, miltä muistin sisältö voisi näyttää tässä tilanteessa:

Tässä muuttujan a sisältö on muistipaikassa 100 ja muuttujan b sisältö on muistipaikassa 101. Listalle c on varattu muistipaikat 102–109, joista tällä hetkellä on käytössä muistipaikat 102–106, koska listalla on 5 alkiota. Muuttujan d sisältö on puolestaan muistipaikassa 110.

Listan alkiot on tallennettu peräkkäisiin muistipaikkoihin, minkä ansiosta on helppoa selvittää, missä kohdassa muistia tietty listan alkio sijaitsee. Tässä tapauksessa alkion osoite muistissa saadaan lisäämällä alkion indeksi listan alkukohtaan 102. Esimerkiksi listan kohdassa 2 oleva alkio on osoitteessa 102 + 2 = 104.

Huomaa, että listalle on varattu enemmän muistia kuin olisi tällä hetkellä tarvetta. Tämän ideana on varautua siihen, että listan alkioiden määrä saattaa kasvaa myöhemmin. Listaan liittyy siis kaksi kokoa: listan todellinen koko (tässä 5) sekä listalle muistista varatun alueen koko (tässä 8).

Listan operaatiot

Pythonissa on monia valmiita operaatioita, joiden avulla voidaan käsitellä listoja. Tarkastellaan seuraavaksi näiden operaatioiden tehokkuutta aikavaativuuksien näkökulmasta olettaen, että listalla on \(n\) alkiota.

Listan operaatioiden aikavaativuuksien tunteminen on tärkeää algoritmien suunnittelussa, koska niistä voi päätellä, mitä operaatioita voi käyttää tehokkaan algoritmin osana. Yleisimmät aikavaativuudet ovat:

• \(O(1)\): operaatio toimii aina tehokkaasti riippumatta listan koosta
• \(O(n)\): operaation tehokkuus riippuu listan koosta ja operaatio voi olla hidas, jos listan koko on suuri

Indeksointi

Listan alkioita voidaan hakea tai muuttaa indeksin perusteella []-syntaksilla.

numbers = [4, 3, 7, 3, 2]
print(numbers[2]) # 7
numbers[2] = 5
print(numbers[2]) # 5

Alkion hakeminen tai muuttaminen vie aikaa \(O(1)\), koska alkiot ovat peräkkäin muistissa ja tietyn alkion muistiosoite voidaan laskea tehokkaasti.

Listan koko

Funktio len kertoo, montako alkiota listalla on:

numbers = [4, 3, 7, 3, 2]
print(len(numbers)) # 5

Funktio vie aikaa \(O(1)\), koska listan yhteyteen muistissa on tallennettu sen koko.

Etsiminen

Operaattori in kertoo, onko alkio listalla. Metodi index antaa ensimmäisen indeksin, jossa alkio esiintyy listalla. Metodi count laskee, montako kertaa alkio esiintyy listalla.

numbers = [4, 3, 7, 3, 2]

print(3 in numbers) # True
print(8 in numbers) # False

print(numbers.index(3)) # 1
print(numbers.count(3)) # 2

Kaikki nämä operaatiot vievät aikaa \(O(n)\), koska niiden täytyy käydä läpi listan alkiot. Esimerkiksi metodi count vastaa logiikaltaan seuraavaa funktiota, joka käy läpi listan alkiot silmukan avulla:

def count(items, target):
    result = 0
    for item in items:
        if item == target:
            result += 1
    return result

Huomaa, että operaatiot saattavat toimia tehokkaasti tietyissä tapauksissa. Esimerkiksi jos etsittävä alkio on listan alussa, operaattori in toimii nopeasti, koska se voi lopettaa listan läpikäynnin heti alkion löydyttyä. Kuitenkin pahimmassa tapauksessa alkio ei esiinny listalla ja koko lista täytyy käydä läpi.

Alkion lisääminen

Metodi append lisää alkion listan loppuun, ja metodi insert lisää alkion annettuun kohtaan listalla.

numbers = [1, 2, 3, 4]

numbers.append(5)
print(numbers) # [1, 2, 3, 4, 5]

numbers.insert(1, 6)
print(numbers) # [1, 6, 2, 3, 4, 5]

Näiden metodien aikavaativuuteen vaikuttaa listan tallennustapa muistissa. Listan ensimmäinen alkio on tallennettu tiettyyn kohtaan muistia, ja kaikki muut alkiot on tallennettu peräkkäin sen jälkeen. Esimerkiksi yllä olevan koodin alussa muistin sisältö voi näyttää seuraavalta ennen lisäyksiä:

Metodi append toimii ajassa \(O(1)\), koska alkion lisääminen listan loppuun ei aiheuta muutoksia muiden alkioiden paikkoihin. Esimerkissä alkio 5 voidaan lisätä tallentamalla se muistipaikkaan 104:

Jos listalle varatulla muistialueella ei ole tilaa uudelle alkiolle, listalle täytyy varata uusi suurempi muistialue ja siirtää listan sisältö sinne. Kuitenkin sopivalla toteutuksella tämä tilanne esiintyy harvoin ja metodi append toimii keskimäärin ajassa \(O(1)\).

Metodi insert toimii ajassa \(O(n)\), koska kun alkio lisätään muualle kuin listan loppuun, kaikkia sen jälkeisiä alkioita tulee siirtää eteenpäin. Esimerkiksi kun alkio 6 lisätään listalle kohtaan 1, alkioita täytyy siirtää muistissa näin:

Huomaa, että metodi insert on kuitenkin tehokas, jos alkio lisätään listan loppuosaan ja siirrettävien alkioiden määrä on pieni.

Alkion poistaminen

Metodi pop poistaa alkion listasta. Jos metodia kutsutaan ilman parametria, se poistaa listan viimeisen alkion. Jos metodille annetaan parametri, se poistaa alkion parametrin mukaisesta indeksistä.

numbers = [1, 2, 3, 4, 5, 6]

numbers.pop()
print(numbers) # [1, 2, 3, 4, 5]

numbers.pop(1)
print(numbers) # [1, 3, 4, 5]

Tarkastellaan taas, miten alkion poistaminen vaikuttaa muistin sisältöön. Koodin alussa muistin sisältö voi näyttää seuraavalta:

Kuten lisäämisessä, alkion poistaminen listan lopusta vie aikaa \(O(1)\), koska tämä ei vaikuta muihin alkioihin. Alkion 6 poistaminen muuttaa muistin sisältöä näin:

Alkion poistaminen listan keskeltä puolestaan vie aikaa \(O(n)\), koska poistetun alkion jälkeisiä alkioita täytyy siirtää taaksepäin. Alkion 2 poistaminen muuttaa muistin sisältöä näin:

Listalla on myös metodi remove, joka poistaa annetun alkion ensimmäisen esiintymän listasta:

numbers = [1, 2, 3, 1, 2, 3]

numbers.remove(3)
print(numbers) # [1, 2, 1, 2, 3]

Metodin aikavaativuus on \(O(n)\), koska metodin täytyy ensin etsiä poistettava alkio listalta (samaan tapaan kuin metodissa index) ja sen jälkeen poistaa alkio ja siirtää sen jälkeen listassa tulevat alkiot.

Yhteenveto

Seuraava taulukko näyttää yhteenvedon tässä käsiteltyjen listan operaatioiden tehokkuudesta:

Listan tehokkaita operaatioita ovat siis alkioiden indeksointi, alkioiden määrän laskeminen sekä alkion lisääminen ja poistaminen listan lopussa. Lista soveltuu erityisesti käytettäväksi algoritmeissa, joissa tehdään enimmäkseen näitä tehokkaita operaatioita ja vähän muita operaatioita.

Viittaukset ja kopiointi

Pythonissa listoja ja muita tietorakenteita käsitellään viittausten kautta, ja listan sijoittaminen muuttujaan kopioi vain viittauksen:

a = [1, 2, 3, 4]
b = a
a.append(5)

print(a) # [1, 2, 3, 4, 5]
print(b) # [1, 2, 3, 4, 5]

Tässä rivi b = a saa aikaan, että muuttujat a ja b viittaavat samaan listaan muistissa. Kun listalle a lisätään uusi alkio, tämä heijastuu myös listaan b.

Jos halutaan kopioida viittauksen sijasta listan sisältö, voidaan käyttää metodia copy seuraavasti:

a = [1, 2, 3, 4]
b = a.copy()
a.append(5)

print(a) # [1, 2, 3, 4, 5]
print(b) # [1, 2, 3, 4]

Tämän seurauksena muuttujat a ja b viittaavat eri listoihin muistissa eikä alkion lisääminen listalle a vaikuta listan b sisältöön.

Äskeisten koodien tehokkuudessa on merkittävä ero: viittauksen kopiointi vie aikaa \(O(1)\), kun taas sisällön kopiointi vie aikaa \(O(n)\). Niinpä rivi b = a vie aikaa \(O(1)\), kun taas rivi b = a.copy() vie aikaa \(O(n)\).

Funktion sivuvaikutukset

Kun funktion parametriksi annetaan tietorakenne, myös tässä tapauksessa kopioidaan vain viittaus. Tällöin funktio voi aiheuttaa sivuvaikutuksia, jos se muuttaa tietorakenteen sisältöä.

Tarkastellaan esimerkkinä seuraavaa funktiota double, joka palauttaa listan, jossa jokainen annetun listan luku on kaksinkertainen:

def double(numbers):
    result = numbers
    for i in range(len(result)):
        result[i] *= 2
    return result

Koska vain listan viittaus kopioidaan, funktion sivuvaikutuksena on, että se muuttaa parametrina annettua listaa:

numbers = [1, 2, 3, 4]
print(double(numbers)) # [2, 4, 6, 8]
print(numbers) # [2, 4, 6, 8]

Tämä ei ole hyvä tilanne, koska funktion tulisi palauttaa uusi lista eikä tehdä muutosta annettuun listaan. Voimme korjata asian esimerkiksi metodin copy avulla:

def double(numbers):
    result = numbers.copy()
    for i in range(len(result)):
        result[i] *= 2
    return result

Tämän jälkeen funktio ei enää muuta alkuperäisen listan sisältöä:

numbers = [1, 2, 3, 4]
print(double(numbers)) # [2, 4, 6, 8]
print(numbers) # [1, 2, 3, 4]

Listan ositus ja yhdistäminen

Pythonin slice-operaattori (syntaksi [:]) luo olemassa olevan listan pohjalta uuden listan, joka sisältää halutun listan välin:

numbers = [1, 2, 3, 4, 5, 6, 7, 8]
print(numbers[2:6]) # [3, 4, 5, 6]

Tämä operaattori vie aikaa \(O(n)\), koska operaattori kopioi uuteen listaan vanhan listan sisällön annetulta väliltä.

Koska slice-operaattori kopioi listan välin, sen avulla voidaan myös tehdä kopio koko listasta. Seuraavat kaksi riviä tarkoittavat samaa:

result = numbers.copy()

result = numbers[:]

Operaattorin + avulla voidaan yhdistää listoja:

first = [1, 2, 3, 4]
second = [5, 6, 7, 8]
print(first + second) # [1, 2, 3, 4, 5, 6, 7, 8]

Tämä vie myös aikaa \(O(n)\), koska operaattori kopioi uuteen listaan alkiot yhdistettäviltä listoilta.

Listat muissa kielissä

Tässä luvussa käsitelty listan toteutus tunnetaan yleisemmin nimellä taulukkolista (array list) tai dynaaminen taulukko (dynamic array).

Matalan tason kielissä (kuten C++ ja Java) perustietorakenne on yleensä taulukko (array). Listan tavoin taulukko sisältää peräkkäisiä alkioita, joita voidaan indeksoida. Kuitenkin taulukolle varataan kiinteä muistialue luontihetkellä, eikä taulukon kokoa voi muuttaa myöhemmin. Taulukon lisäksi kielissä on kuitenkin saatavilla listoja, joiden kokoa pystyy muuttamaan.

C++:ssa tietorakenne std::vector toteuttaa listan:

std::vector<int> numbers;

numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);

Javassa puolestaan tietorakenne ArrayList toteuttaa listan:

ArrayList<Integer> numbers = new ArrayList<>();

numbers.add(1);
numbers.add(2);
numbers.add(3);

JavaScriptin perustietorakenne on nimeltään taulukko (Array), mutta se on todellisuudessa lista, koska sen kokoa pystyy muuttamaan:

numbers = [];

numbers.push(1);
numbers.push(2);
numbers.push(3);

3. Tehokkaat algoritmit

Tässä ja kahdessa seuraavassa luvussa tutustumme tehokkaiden algoritmien suunnitteluun. Tavoitteemme on saada aikaan algoritmeja, jotka toimivat tehokkaasti myös silloin, kun syötteen koko \(n\) on suuri.

Tavallinen tilanne algoritmien suunnittelussa on, että on helppoa laatia suoraviivainen algoritmi, joka ratkaisee tehtävän kahdella silmukalla ajassa \(O(n^2)\). Tällaista algoritmia voidaan kutsua raa’an voiman (brute force) algoritmiksi. Tämä ei kuitenkaan riitä \(n\):n ollessa suuri, vaan tarvitaan tehokkaampi algoritmi.

Käytännössä tehokkaan algoritmin aikavaativuus on usein \(O(n)\) tai \(O(n \log n)\). Tutustumme ensin \(O(n)\)-algoritmeihin, jotka käyvät syötteen läpi yhdellä silmukalla ja pitävät muistissa sopivalla tavalla valittua tietoa. Aikavaativuus \(O(n \log n)\) liittyy usein järjestämiseen, jota käsittelemme luvussa 5.

Tehokkaan algoritmin runko

Tyypillinen tehokkaan algoritmin runko on seuraava:

# muuttujien määrittely
for ...
    # tehokas koodi
# vastauksen palautus

Tällaisessa algoritmissa on yksi for-silmukka, joka käy läpi algoritmille annetun syötteen vasemmalta oikealle. Silmukan sisällä tulee olla tehokasta koodia niin, että silmukan jokainen kierros vie aikaa \(O(1)\). Tällöin koko algoritmin aikavaativuus on \(O(n)\).

Tehokkaan algoritmin silmukan sisällä saa olla seuraavia:

• muuttujan arvon päivitys muiden muuttujien tai yksittäisten syötteen alkioiden perusteella
• laskutoimitus, joka liittyy muuttujan arvon päivittämiseen
• if-komento, joka vaikuttaa sihen, miten muuttujia päivitetään

Sen sijaan silmukan sisällä ei saa olla seuraavia:

• toinen silmukka, joka käy läpi syötteen alkioita
• hidas syötettä käsittelevä operaatio (esim. metodi count tai slice-operaatio [:])
• hidas funktiokutsu (esim. sum, min tai max koko syötteelle)

Monen algoritmin suunnittelussa keskeinen haaste on keksiä, miten algoritmin saa toteutettua niin, että silmukan sisällä on vain tehokasta koodia. Näemme seuraavaksi esimerkkejä siitä, miten silmukan sisällä oleva tehokas koodi voidaan toteuttaa.

Esimerkki: Osakekauppa

Tehtävä

Suoraviivainen algoritmi tehtävän ratkaisemiseen on käydä läpi kaikki vaihtoehdot osakkeen ostopäivän ja myyntipäivän valintaan kahdella silmukalla. Seuraava funktio best_profit toteuttaa algoritmin:

def best_profit(prices):
    n = len(prices)
    best = 0
    for i in range(n):
        for j in range(i + 1, n):
            best = max(best, prices[j] - prices[i])
    return best

Ideana on, että muuttuja i valitsee ostopäivän ja muuttuja j valitsee myyntipäivän. Jokaiselle valinnalle lasketaan näin saatava tuotto osakekaupasta, ja muuttuja best pitää muistissa parasta tuottoa. Tämä on toimiva algoritmi, mutta ongelmana on, että algoritmin aikavaativuus on \(O(n^2)\) eli se on hidas, kun \(n\) on suuri. Algoritmia tulisi tehostaa niin, että siinä ei ole kahta silmukkaa vaan vain yksi silmukka.

Mietitään nyt, millainen algoritmin tulisi olla, jotta siinä olisi vain yksi silmukka. Kun olemme tietyn päivän kohdalla, miten suuri voitto on mahdollinen, jos myymme osakkeen kyseisenä päivänä? Voitto on suurin silloin, kun olemme ostaneet osakkeen aiemmin mahdollisimman halvalla. Niinpä meidän kannattaa valita ostohinnaksi osakkeen halvin hinta kyseiseen päivään mennessä.

Voimme toteuttaa tällaisen algoritmin seuraavasti:

def best_profit(prices):
    n = len(prices)
    best = 0
    for i in range(n):
        min_price = min(prices[0:i+1])
        best = max(best, prices[i] - min_price)
    return best

Ideana on laskea silmukassa muuttujaan min_price osakkeen halvin hinta päivään i mennessä. Tämä on toteutettu hakemalla pienin alkio min-funktiolla listan alkuosassa prices[0:i+1]. Tämän jälkeen saamme laskettua kaavalla prices[i] - min_price voiton, kun myymme osakkeen päivänä i.

Tämä on toimiva algoritmi ja siinä on vain yksi silmukka, mutta algoritmi ei ole vielä tehokas. Ongelmana on, että muuttujan min_price laskeminen on hidasta silmukassa, koska min-funktio käy läpi listan prices alkuosan. Tämä vie aikaa \(O(n)\), minkä vuoksi algoritmin aikavaativuus on edelleen \(O(n^2)\).

Voimme kuitenkin korjata ongelman seuraavasti:

def best_profit(prices):
    n = len(prices)
    best = 0
    min_price = prices[0]
    for i in range(n):
        min_price = min(min_price, prices[i])
        best = max(best, prices[i] - min_price)
    return best

Nyt muuttujaa min_price ei lasketa tyhjästä silmukan joka kierroksella, vaan uusi arvo lasketaan tehokkaasti edellisen arvon perusteella. Tämän muutoksen ansiosta silmukan jokainen kierros vie aikaa \(O(1)\), jolloin algoritmin aikavaativuus on \(O(n)\) ja algoritmi toimii tehokkaasti.

Huomaa, että funktion min käyttäminen voi olla sekä hidasta että tehokasta. Jos funktiolla haetaan listan pienin alkio, tämä on hidasta. Jos kuitenkin funktiolla valitaan pienempi kahdesta arvosta, tämä on tehokasta.

Toimiiko algoritmi?

Tehokkaan algoritmin toimintalogiikka on yleensä monimutkaisempi kuin suoraviivaisessa raa’an voiman algoritmissa. Tämän vuoksi voi olla vaikea tietää, onko toteutettu algoritmi varmasti toimiva.

Kätevä tapa saada tietoa tehokkaan algoritmin toimivuudesta on verrata sen toimintaa suoraviivaiseen algoritmiin. Tämä voidaan automatisoida niin, että algoritmeja testataan suurella määrällä satunnaisia syötteitä. Esimerkiksi voimme testata äskeisen tehtävän algoritmeja seuraavaan tapaan:

import random

def best_profit_brute(prices):
    ...

def best_profit_fast(prices):
    ...

while True:
    n = random.randint(1, 20)
    prices = [random.randint(1, 10) for _ in range(n)]

    result_brute = best_profit_brute(prices)
    result_fast = best_profit_fast(prices)

    print(prices, result_brute, result_fast)

    if result_brute != result_fast:
        print("ERROR")
        break

Tässä funktio best_profit_brute toteuttaa raa’an voiman algoritmin ja funktio best_profit_fast toteuttaa tehokkaan algoritmin. Pääohjelma testaa algoritmeja luomalla satunnaisia listoja, joissa \(n\) on välillä \(1 \dots 20\) ja hinnat ovat välillä \(1 \dots 10\). Jokaisen testin jälkeen ohjelma tulostaa listan sisällön sekä funktioiden palauttamat arvot. Ohjelman tulostus voisi alkaa seuraavasti:

[2, 4, 5, 4, 2, 4, 8, 7, 5] 6 6
[8, 8, 8, 3, 6, 4, 9, 3, 2, 5, 4, 5, 2] 6 6
[9, 3, 1, 5, 8, 9, 3] 8 8
[3, 6, 7] 4 4
[6, 8, 7, 10, 8, 6, 1, 1, 2, 2, 8, 9, 10] 9 9
[4, 5, 3, 4, 5] 2 2
[3, 6, 2] 3 3
[4, 3, 8, 10, 7, 3, 4, 7, 5, 1, 7, 8, 7] 7 7
...

Tällaisen testauksen avulla saa hyvää varmuutta siitä, että tehokas algoritmi on toimiva. Jos löytyy syöte, jossa algoritmi antaa väärän tuloksen, ohjelma ilmoittaa tästä ja testaus päättyy. Tämän jälkeen ohjelman antaman syötteen avulla voi koettaa tutkia, miksi algoritmi ei toimi oikein.

Esimerkki: Bittijono

Tehtävä

Suoraviivainen tapa ratkaista tehtävä on käydä läpi kaikki tavat valita vasen ja oikea kohta ja laskea, monessako kohdassa vasen bitti on 0 ja oikea bitti on 1:

def count_ways(bits):
    n = len(bits)
    result = 0
    for i in range(n):
        for j in range(i + 1, n):
            if bits[i] == '0' and bits[j] == '1':
                result += 1
    return result

Tässä ongelmana on jälleen, että aikavaativuus on \(O(n^2)\) eli algoritmi on liian hidas.

Mietitään, miten selviäisimme yhdellä silmukalla. Kuten osakkeen hinnan laskemisessa, tässäkin tehtävässä hyvä lähestymistapa on käsitellä jokaisessa kohdassa kyseiseen kohtaan päättyvät ratkaisut. Tarkemmin voimme koettaa laskea kussakin bittijonon kohdassa i tehokkaasti tavat, joissa oikea bitti 1 on kohdassa i ja vasen bitti 0 on ennen kohtaa i.

Jos kohdassa i on bitti 1, tässä kohdassa voi olla oikea kohta. Tässä tapauksessa vasen kohta voi olla mikä tahansa kohta ennen kohtaa i, jossa on bitti 0. Niinpä saamme aikaan tehokkaan algoritmin, kun pidämme muistissa, montako bittiä 0 on tullut vastaan silmukan aikana. Voimme toteuttaa algoritmin näin:

def count_ways(bits):
    n = len(bits)
    result = 0
    zeros = 0
    for i in range(len(bits)):
        if bits[i] == '0':
            zeros += 1
        if bits[i] == '1':
            result += zeros
    return result

Silmukan sisällä suoritettava koodi riippuu siitä, onko bitti 0 vai 1. Jos bitti on 0, kasvatetaan muuttujan zeros arvoa. Tämän avulla joka kohdassa tiedetään, montako bittiä 0 on tullut vastaan tähän mennessä. Jos taas bitti on 1, lisätään muuttujaan result muuttujan zeros arvo. Tämä laskee tehokkaasti mukaan tulokseen kaikki tavat, joissa oikea bitti on kohdassa i.

Algoritmissa on yksi silmukka, joka käy syötteen läpi, ja silmukan sisällä olevan koodin aikavaativuus on \(O(1)\). Tämän ansiosta algoritmin aikavaativuus on \(O(n)\) ja se toimii tehokkaasti.

Esimerkki: Listan halkaisu

Tehtävä

Suoraviivainen algoritmi tehtävään on seuraava:

def count_splits(numbers):
    n = len(numbers)
    result = 0
    for i in range(n - 1):
        left_sum = sum(numbers[0:i+1])
        right_sum = sum(numbers[i+1:])
        if left_sum == right_sum:
            result += 1
    return result

Algoritmi käy läpi kaikki tavat halkaista lista ja laskee muuttujiin left_sum ja right_sum listan vasemman ja oikean osan summan halkaisun jälkeen. Jos summat ovat samat, muuttujan result arvo kasvaa yhdellä. Algoritmin aikavaativuus on \(O(n^2)\), koska muuttujien left_sum ja right_sum laskeminen vie aikaa \(O(n)\).

Koska silmukka käy listan läpi vasemmalta oikealle, voimme tehostaa algoritmia laskemalla summaa left_sum samaa tahtia silmukan kanssa:

def count_splits(numbers):
    n = len(numbers)
    result = 0
    left_sum = 0
    for i in range(n - 1):
        left_sum += numbers[i]
        right_sum = sum(numbers[i+1:])
        if left_sum == right_sum:
            result += 1
    return result

Tämä ei ole kuitenkaan riittävä tehostus, koska muuttujan right_sum laskeminen on edelleen hidasta eikä siihen voi tehdä vastaavaa muutosta, koska listaa käydään läpi vasemmalta oikealle. Vaikka muuttuja left_sum lasketaan tehokkaasti, algoritmi vie edelleen aikaa \(O(n^2)\).

Voimme kuitenkin tehostaa algoritmia lisää hyödyllisen havainnon avulla: jos tiedämme vasemman osan summan lisäksi koko listan summan, voimme laskea näiden tietojen avulla tehokkaasti oikean osan summan.

def count_splits(numbers):
    n = len(numbers)
    result = 0
    left_sum = 0
    total_sum = sum(numbers)
    for i in range(n - 1):
        left_sum += numbers[i]
        right_sum = total_sum - left_sum
        if left_sum == right_sum:
            result += 1
    return result

Koska koko listan summa ei muutu silmukan aikana, voimme laskea sen ennen silmukkaa muuttujaan total_sum. Tämä vie aikaa \(O(n)\) mutta se tehdään vain kerran ennen silmukkaa. Tämän jälkeen silmukassa right_sum saadaan laskettua tehokkaasti kaavalla total_sum - left_sum. Tuloksena on algoritmi, jonka aikavaativuus on \(O(n)\).

Esimerkki: Osalistat

Tehtävä

Tämä tehtävä on selvästi vaikeampi kuin aiemmat käsitellyt tehtävät, mutta tässäkin toimii aiemmin hyväksi havaittu tekniikka: käydään läpi lista ja lasketaan jokaisessa kohdassa, montako ratkaisua päättyy kyseiseen kohtaan.

Esimerkkitapauksessa tulisi saada laskettua seuraavat tulokset:

Esimerkiksi kohdassa 5 haluttu tulos on 3, koska kohtaan 5 päättyvät osalistat ovat \([2,3,3,2,2]\), \([3,3,2,2]\) ja \([3,2,2]\).

Voimme laskea kohtaan i päättyvien osalistojen määrän tehokkaasti kahden muuttujan avulla: a osoittaa edelliseen kohtaan, jossa on eri luku kuin kohdassa i, ja b osoittaa edelliseen kohtaan, jossa on eri luku kuin kohdissa i ja a. Nämä muuttujat ovat hyödyllisiä, koska osalistan tulee alkaa kohdan b jälkeen ja viimeistään kohdassa a. Niinpä kohtaan i päättyvien osalistojen määrä saadaan laskettua kaavalla a - b.

Esimerkiksi kun i on kohdassa 5, tilanne on seuraava:

Tässä tapauksessa a on kohdassa 3, jossa on luku 3, ja b on kohdassa 0, jossa on luku 1. Osalistojen määrä saadaan laskettua kaavalla 3 – 0 = 3.

Silmukan edetessä muuttujia a ja b täytyy päivittää sopivasti aina, kun kohdassa i on eri luku kuin kohdassa i - 1. Tässä on kaksi tapausta:

1. Jos kohdassa i on eri luku kuin kohdassa a, b siirtyy kohtaan a ja a siirtyy kohtaan i - 1.
2. Jos kohdassa i on sama luku kuin kohdassa a, vain a siirtyy kohtaan i - 1.

Katsotaan nyt, miten muuttujat päivittyvät äskeisessä esimerkissä. Kun i siirtyy kohdasta 5 kohtaan 6, kohdassa i on eri luku kuin kohdassa a. Niinpä kyseessä on tapaus 1, jolloin a siirtyy kohtaan 6 – 1 = 5 ja b siirtyy kohtaan 3:

Kun i siirtyy kohdasta 6 kohtaan 7, kohdassa i on sama luku kuin kohdassa a. Niinpä kyseessä on tapaus 2, jolloin vain a siirtyy kohtaan 7 – 1 = 6:

Tämän idean avulla saadaan tehokas algoritmi, joka voidaan toteuttaa seuraavasti:

def count_lists(numbers):
    n = len(numbers)
    a = b = -1
    result = 0
    for i in range(1, n):
        if numbers[i] != numbers[i - 1]:
            if numbers[i] != numbers[a]:
                b = a
            a = i - 1
        result += a - b
    return result

Tässä toteutuksessa a ja b ovat alussa -1 tarkoittaen, että ne eivät vielä osoita mihinkään listan kohtaan. Tämän ansiosta algoritmi laskee oikein osalistojen määrän myös listan alkuosassa.

4. Hajautus

Hajautus (hashing) on tekniikka, jota käytetään usein tehokkaiden tietorakenteiden toteuttamisessa. Pythonissa tietorakenteet joukko (set) ja sanakirja (dict) perustuvat hajautukseen.

Tutustumme tässä luvussa hajautukseen perustuviin tietorakenteisiin ja niiden käyttämiseen algoritmien suunnittelussa. Lisäksi tutustumme tietorakenteiden taustalla olevaan teoriaan.

Joukko

Pythonin tietorakenne set eli joukko on hajautukseen perustuva tietorakenne, joka pitää yllä alkioiden joukkoa. Tietorakenne tarjoaa seuraavat operaatiot:

• metodi add lisää alkion joukkoon
• operaattori in tarkastaa, onko alkio joukossa
• metodi remove poistaa alkion joukosta

Joukko on toteutettu niin, että kaikki yllä olevat operaatiot tapahtuvat tehokkaasti ajassa \(O(1)\).

Esimerkki

Seuraava koodi luo joukon numbers ja lisää sinne alkioita metodilla add:

numbers = set()

numbers.add(1)
numbers.add(2)
numbers.add(3)

print(numbers) # {1, 2, 3}

Joukko voidaan myös luoda suoraan listan perusteella:

numbers = set([1, 2, 3])

print(numbers) # {1, 2, 3}

Operaattori in tarkastaa, kuuluuko tietty alkio joukkoon:

print(3 in numbers) # True
print(4 in numbers) # False

Metodi remove puolestaan poistaa alkion joukosta:

print(numbers) # {1, 2, 3}
numbers.remove(2)
print(numbers) # {1, 3}

Lista vs. joukko

Lista ja joukko ovat tietyllä tavalla samantapaisia tietorakenteita, koska molemmissa voi lisätä, etsiä ja poistaa alkioita. Kuitenkin tietorakenteiden tehokkuudessa ja ominaisuuksissa on suuria eroja.

Tehokkuus

Listassa alkion lisääminen on tehokasta, mutta on hidasta etsiä alkiota listasta sekä poistaa alkio listasta.

Joukossa on tehokasta lisätä alkio joukkoon, etsiä alkiota joukosta sekä poistaa alkio joukosta.

Indeksointi

Listassa alkioita voidaan käsitellä indeksien perusteella:

numbers = [1, 2, 3]
print(numbers[1]) # 2

Joukon alkioihin sen sijaan ei voida viitata indekseillä:

numbers = set([1, 2, 3])
print(numbers[1]) # TypeError: 'set' object is not subscriptable

Toistuvat alkiot

Listassa sama alkio voi esiintyä useita kertoja:

numbers = []

numbers.append(5)
numbers.append(5)
numbers.append(5)

print(numbers) # [5, 5, 5]

Joukossa sama alkio voi esiintyä enintään kerran. Jos alkio lisätään monta kertaa joukkoon, tällä ei ole vaikutusta:

numbers = set()

numbers.add(5)
numbers.add(5)
numbers.add(5)

print(numbers) # {5}

Esimerkki: Montako eri lukua?

Tehtävä

Hidas ratkaisu (lista)

Voisimme ratkaista tehtävän listan avulla seuraavasti:

def count_distinct(numbers):
    seen = []
    for x in numbers:
        if x not in seen:
            seen.append(x)
    return len(seen)

Algoritmi käy läpi luvut ja lisää luvun listaan seen, jos lukua ei ole vielä listassa. Lopuksi listan seen koko on yhtä suuri kuin eri lukujen määrä.

Tämä algoritmi on toimiva mutta ei tehokas, koska jokaisella silmukan kierroksella vie aikaa \(O(n)\) tarkastaa operaattorilla in, onko luku listassa. Tämän vuoksi algoritmin aikavaativuus on \(O(n^2)\). Algoritmia on kuitenkin helppoa parantaa käyttämällä listan sijasta joukkoa.

Tehokas ratkaisu (joukko)

Voimme ratkaista tehtävän tehokkaasti joukon avulla seuraavasti:

def count_distinct(numbers):
    seen = set()
    for x in numbers:
        if x not in seen:
            seen.add(x)
    return len(seen)

Funktio on muuten samanlainen kuin aiemmassa listaratkaisussa, mutta seen on nyt joukko ja alkiot lisätään metodilla add. Tällä muutoksella on suuri vaikutus algoritmin tehokkuuteen. Muutoksen jälkeen operaattori in vie aikaa \(O(1)\) ja algoritmin aikavaativuus on vain \(O(n)\).

Koodia on mahdollista vielä tiivistää käyttämällä hyväksi sitä, että sama alkio ei mene useita kertoja joukkoon. Tämän ansiosta koodista voi poistaa tarkastuksen, onko alkio valmiiksi joukossa:

def count_distinct(numbers):
    seen = set()
    for x in numbers:
        seen.add(x)
    return len(seen)

Itse asiassa koodia voi tiivistää vielä lisää luomalla joukon suoraan listan pohjalta. Funktion toteutukseen riittää loppujen lopuksi yksi rivi koodia:

def count_distinct(numbers):
    return len(set(numbers))

Sanakirja

Pythonin tietorakenne dict eli sanakirja on hajautukseen perustuva tietorakenne, johon voidaan tallentaa avain-arvo-pareja. Ideana on, että avaimen perusteella voidaan hakea siihen liittyvä arvo.

Sanakirjaa voi ajatella listan yleistyksenä: listassa avaimet ovat indeksit \(0 \dots n-1\), kun taas sanakirjassa avaimet voivat olla mitä tahansa alkioita. Tietoa voi lisätä, hakea ja poistaa tehokkaasti ajassa \(O(1)\) avaimen perusteella.

Esimerkki

Seuraava koodi luo sanakirjan weights, jossa avaimet ovat merkkijonoja ja arvot ovat lukuja.

weights = {}

weights["apina"] = 100
weights["banaani"] = 1
weights["cembalo"] = 500

Yllä olevan sanakirjan voi luoda myös näin:

weights = {"apina": 100, "banaani": 1, "cembalo": 500}

Sanakirjan arvoja voi käsitellä samaan tapaan kuin listan arvoja:

print(weights["apina"]) # 100
weights["apina"] = 150
print(weights["apina"]) # 150

Operaattori in tarkastaa, onko sanakirjassa tiettyä avainta:

print("apina" in weights) # True
print("ananas" in weights) # False

Komento del poistaa avaimen ja siihen liittyvän arvon sanakirjasta:

print(weights) # {'apina': 100, 'banaani': 1, 'cembalo': 500}
del weights["banaani"]
print(weights) # {'apina': 100, 'cembalo': 500}

Sanakirjan käyttäminen

Seuraavassa on kolme tavallista sanakirjan käyttötarkoitusta algoritmien suunnittelussa:

Onko alkio esiintynyt

Sanakirjaa voi käyttää joukon kaltaisesti pitämään kirjaa esiintyneistä alkioista:

seen = {}
for x in items:
    seen[x] = True

Tämä koodi on toiminnaltaan suunnilleen sama kuin seuraava koodi:

seen = set()
for x in items:
    seen.add(x)

Voikin ajatella, että joukko vastaa sanakirjaa, jossa avaimet ovat joukon alkioita ja jokainen arvo on True.

Alkion esiintymiskerrat

Tavallinen sanakirjan käyttötarkoitus on laskea, montako kertaa mikäkin alkio on esiintynyt.

count = {}
for x in items:
    if x not in count:
        count[x] = 0
    count[x] += 1

Koodi laskee esiintymiskerrat sanakirjan count avulla. Jos alkiota x ei ole vielä sanakirjassa, koodi asettaa sen esiintymiskertojen määräksi 0. Tämän jälkeen koodi kasvattaa alkion x esiintymiskertoja yhdellä.

Alkion esiintymiskohta

Joissakin algoritmeissa on hyödyllistä pitää yllä tietoa siitä, missä kohdassa mikäkin alkio on esiintynyt.

pos = {}
for i, x in enumerate(items):
    pos[x] = i

Tässä sanakirjassa pos on kunkin alkion viimeisin esiintymiskohta listassa. Funktion enumerate avulla lista voidaan käydä läpi niin, että joka kierroksella i sisältää alkion indeksin ja x itse alkion.

Esimerkki: Moodi

Tehtävä

Voimme ratkaista tehtävän tehokkaasti hajautuksen avulla luomalla sanakirjan, johon lasketaan jokaisen alkion esiintymiskertojen määrä:

def find_mode(numbers):
    count = {}
    mode = numbers[0]

    for x in numbers:
        if x not in count:
            count[x] = 0
        count[x] += 1

        if count[x] > count[mode]:
            mode = x

    return mode

Tässä count on sanakirja, johon lasketaan lukujen esiintymiskerrat, ja muuttuja mode sisältää moodin. Alussa mode on listan ensimmäinen luku ja muuttujaa päivitetään aina, kun viimeksi käsitelty luku on esiintynyt useammin kuin muuttujassa oleva luku. Koska sanakirjan operaatiot toimivat ajassa \(O(1)\), algoritmin aikavaativuus on \(O(n)\).

Tässä on vielä toinen tapa toteuttaa algoritmi:

def find_mode(numbers):
    count = {}
    mode = (0, 0)

    for x in numbers:
        if x not in count:
            count[x] = 0
        count[x] += 1

        mode = max(mode, (count[x], x))

    return mode[1]

Nyt muuttuja mode on pari, jonka ensimmäinen alkio on moodin esiintymiskerrat ja toinen alkio on itse moodi. Esimerkiksi jos muuttujan arvona on (5, 2), tämä tarkoittaa, että alkio 2 on esiintynyt 5 kertaa.

Tämän toteutuksen etuna on, että moodia pystyy päivittämään max-funktion avulla. Tässä max-funktio vertailee ensisijaisesti parin ensimmäistä alkiota ja toissijaisesti parin toista alkiota. Koska parin ensimmäinen alkio on esiintymiskertojen määrä, parin arvo on sitä suurempi mitä useammin luku on esiintynyt.

Huomaa, että yllä olevat kaksi funktiota toimivat vähän eri tavalla tilanteessa, jossa on useita mahdollisia vaihtoehtoja moodiksi. Ensimmäinen funktio valitsee moodin, jonka viimeinen esiintymiskerta tulee vastaan ensimmäisenä. Toinen funktio puolestaan valitsee moodin, joka on arvoltaan suurin, koska pareissa vertaillaan toissijaisesti luvun suuruutta.

Esimerkki: Kierrokset

Tehtävä

Oleellinen havainto on, että uusi kierros täytyy aloittaa aina silloin, kun kerättävä luku on edellisen kerätyn luvun vasemmalla puolella. Esimerkiksi yllä olevassa listassa luku \(3\) aloittaa uuden kierroksen, koska se on luvun \(2\) vasemmalla puolella.

Hidas ratkaisu (lista)

Seuraava algoritmi ratkaisee tehtävän käyttäen vain listaa:

def count_rounds(numbers):
    n = len(numbers)

    rounds = 1
    for i in range(1, n):
        if numbers.index(i + 1) < numbers.index(i):
            rounds += 1

    return rounds

Ideana on laskea muuttujaan rounds tarvittava kierrosten määrä. Alussa kierrosten määrä on yksi. Sitten silmukka käy läpi luvut \(1 \dots n-1\) ja lisää kierrosten määrää yhdellä aina, kun luku \(i+1\) esiintyy listassa ennen lukua \(i\).

Tässä toteutuksessa on käytössä listan metodi index, joka antaa luvun sijainnin listassa. Tämän takia algoritmi on kuitenkin hidas, koska metodi index vie aikaa \(O(n)\) ja koko algoritmin aikavaativuus on \(O(n^2)\).

Tehokas ratkaisu (sanakirja)

Voimme toteuttaa saman idean tehokkaasti ottamalla käyttöön sanakirjan, joka sisältää kunkin luvun kohdan listassa:

def count_rounds(numbers):
    n = len(numbers)

    pos = {}
    for i, x in enumerate(numbers):
        pos[x] = i

    rounds = 1
    for i in range(1, n):
        if pos[i + 1] < pos[i]:
            rounds += 1

    return rounds

Tämän jälkeen ei tarvitse käyttää metodia index vaan luvun sijainnin listasta saa haettua tehokkaasti sanakirjasta. Algoritmissa on kaksi silmukkaa, jotka toimivat molemmat ajassa \(O(n)\), joten koko algoritmin aikavaativuus on \(O(n)\).

Esimerkki: Soittolista

Tehtävä

Hyvä lähestymistapa tähän tehtävään on laskea jokaiseen soittolistan kohtaan, kuinka pitkä on pisin kyseiseen kohtaan päättyvä soittolistan osa, jossa ei esiinny kahta samaa laulua. Näistä pituuksista suurin on tehtävän haluttu vastaus. Äskeisessä esimerkissä nämä pituudet ovat:

Kun olemme tietyssä soittolistan kohdassa ja vastaan tulee aiemmin listalla esiintynyt laulu, tämä rajoittaa soittolistan osan pituutta, koska kyseinen laulu ei saa esiintyä kahta kertaa. Niinpä soittolistan osan tulee alkaa laulun edellisen esiintymän jälkeen. Tämän avulla voimme päätellä, mistä kohdasta soittolistan osa voi alkaa.

Seuraava tehokas algoritmi perustuu yllä oleviin ideoihin:

def max_length(songs):
    n = len(songs)

    pos = {}
    start = 0
    length = 0

    for i, song in enumerate(songs):
        if song in pos:
            start = max(start, pos[song] + 1)
        length = max(length, i - start + 1)
        pos[song] = i

    return length

Sanakirja pos kertoo kustakin laulusta, missä kohtaa soittolistaa laulu on esiintynyt viimeksi. Muuttujassa start on kohta, josta soittolistan osa voi alkaa, ja muuttujassa length on pisin soittolistan osan pituus.

Algoritmi käy läpi soittolistan ja päivittää muuttujaa start aina, kun vastaan tulee laulu, joka on esiintynyt aiemmin soittolistalla. Tässä tilanteessa muuttujan start arvo kasvaa, jos laulun edellisen esiintymän kohta on aiempaa suurempi.

Tuloksena oleva algoritmi toimii ajassa \(O(n)\) hajautuksen ansiosta.

Esimerkki: Listan summat

Tehtävä

Hyödyllinen tekniikka tällaisessa tehtävässä on tarkastella listan alkuosien lukujen summia eli laskea jokaiseen kohtaan lukujen summa listan alusta kyseiseen kohtaan. Esimerkissä alkuosien summat ovat seuraavat:

Esimerkiksi kohdassa \(4\) alkuosan summa on \(11\), koska listan lukujen summa kohdasta \(0\) kohtaan \(4\) on \(2+3+5-3+4=11\).

Alkuosien summien hyötynä on, että minkä tahansa osalistan lukujen summa saadaan laskettua kahden alkuosan summan perusteella. Kun osalista alkaa kohdasta \(a\) ja päättyy kohtaan \(b\), sen lukujen summa saadaan laskemalla alkuosan summa kohtaan \(b\) ja vähentämällä siitä alkuosan summa kohtaan \(a-1\).

Esimerkiksi kun osalista alkaa kohdasta \(2\) ja päättyy kohtaan \(4\), sen lukujen summa on \(5-3+4=6\). Tämä on yhtä suuri kuin alkuosan summa kohtaan \(4\), josta on vähennetty alkuosan summa kohtaan \(1\), eli \(11-5=6\).

Oletetaan nyt, että olemme listan kohdassa \(i\) ja haluamme laskea, monessako kohtaan \(i\) päättyvässä osalistassa lukujen summa on \(x\). Kun alkuosan summa kohdassa \(i\) on \(p\), alkuosan summan tulee olla \(p-x\) aiemmassa kohdassa, jotta osalistan summaksi tulee \(p-(p-x)=x\). Niinpä haluttuja osalistoja on yhtä monta kun aiempia kohtia, joissa alkuosan summa on \(p-x\).

Seuraava algoritmi perustuu yllä olevaan ideaan:

def count_sublists(numbers, x):
    count = {0: 1}
    prefix_sum = 0
    result = 0

    for i in range(len(numbers)):
        prefix_sum += numbers[i]
        if prefix_sum - x in count:
            result += count[prefix_sum - x]

        if prefix_sum not in count:
            count[prefix_sum] = 0
        count[prefix_sum] += 1

    return result

Tässä sanakirjaan count lasketaan, montako kertaa mikäkin summa on esiintynyt listan alkuosien summissa. Sanakirjan avulla voidaan laskea tehokkaasti jokaiseen listaan kohtaan, monessako kyseiseen kohtaan päättyvässä osalistassa summa on \(x\). Sanakirjassa on valmiina tyhjää listaa tarkoittava summa \(0\), jotta algoritmi laskee oikein myös tapaukset, joissa osalista alkaa listan alusta.

Tuloksena oleva algoritmi toimii ajassa \(O(n)\) hajautuksen ansiosta.

Miten hajautus toimii?

Tässä luvussa esitellyt Pythonin tietorakenteet set ja dict perustuvat hajautukseen ja niiden taustalla on tietorakenne hajautustaulu. Pythonissa hajautustaulu on toteuttu avointa hajautusta käyttäen.

Pythonissa on sisäänrakennettu funktio hash, jolla voidaan laskea alkion hajautusarvo. Python kutsuu tätä funktiota, kun se määrittää alkion sijainnin hajautustaulussa. Funktion toimintaa voi testata näin:

> hash(42)
42
> hash(10**100)
910685213754167845
> hash("apina")
4992529190565255982

Kuten yllä olevasta testistä voi havaita, Pythonissa pienen kokonaisluvun hajautusarvo on suoraan kyseinen luku. Muuten hajautusarvot ovat yleensä satunnaisen näköisiä lukuja.

Pythonissa hajautusta käyttävät tietorakenteet toimivat yleensä aina tehokkaasti ja voidaan olettaa, että lisäykset, haut ja poistot vievät aikaa \(O(1)\). Silti on mahdollista, että Pythonin hajautus toimii hitaasti, jos syöte on valittu sopivalla tavalla.

Mitä voi hajauttaa?

Seuraava koodi ei toimi Pythonissa:

lists = set()
lists.add([1, 2, 3]) # TypeError: unhashable type: 'list'

Ongelmana on, että listalle ei voi laskea hajautusarvoa:

print(hash([1, 2, 3])) # TypeError: unhashable type: 'list'

Pythonissa on periaatteena, että hajautusarvon voi laskea vain oliolle, jonka sisältö on muuttumaton (immutable). Listan sisältö ei ole muuttumaton, koska listassa on esimerkiksi metodi append, joka lisää siihen uuden alkion. Tämän vuoksi listalle ei voi laskea hajautusarvoa.

Muuttumattomia olioita ovat esimerkiksi luvut, merkkijonot ja näitä sisältävät tuplet. Esimerkiksi seuraava koodi toimii, koska lukuja sisältävä tuple on muuttumaton ja sille voidaan laskea hajautusarvo:

lists = set()
lists.add((1, 2, 3))

Huomaa, että sanakirjassa vain avaimelle lasketaan hajautusarvo. Tämän takia myös seuraava koodi toimii, jossa avain on merkkijono ja arvo on lista:

lists = {}
lists["apina"] = [1, 2, 3]

Oma luokka hajautuksessa

Omaa luokkaa voi käyttää hajautuksessa määrittelemällä sille seuraavat metodit:

• __hash__: palauttaa olion hajautusarvon (funktio hash kutsuu sitä)
• __eq__: vertailee, onko olion sisältö sama kuin toisen olion sisältö (operaattori == kutsuu sitä)

Seuraavassa on esimerkki metodien määrittelystä. Tässä metodi __hash__ palauttaa olion sisältöä vastaavan tuplen hajautusarvon.

class Location:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __hash__(self):
        return hash((self.x, self.y))

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

Tämän jälkeen esimerkiksi seuraava koodi toimii tarkoitetulla tavalla:

locations = set()
locations.add(Location(1, 2))
locations.add(Location(3, -5))
locations.add(Location(1, 4))

Hajautus muissa kielissä

Hajautusta käyttävät tietorakenteet ovat yleisiä eri ohjelmointikielissä. Monissa kielissä Pythonin sanakirjaa vastaa tietorakenne nimeltä map, josta voidaan käyttää suomeksi nimeä hakemisto.

C++:ssa tietorakenteet std::unordered_set ja std::unordered_map toteuttavat hajautusta käyttävän joukon ja hakemiston.

std::unordered_set<int> numbers;

numbers.add(1);
numbers.add(2);
numbers.add(3);

std::unordered_map<std::string, int> weights;

weights["apina"] = 100;
weights["banaani"] = 1;
weights["cembalo"] = 500;

Javassa vastaavat tietorakenteet ovat HashSet ja HashMap:

HashSet<Integer> numbers = new HashSet<Integer>();

numbers.add(1);
numbers.add(2);
numbers.add(3);

HashMap<String, Integer> weights = new HashMap<String, Integer>();

weights.put("apina", 100);
weights.put("banaani", 1);
weights.put("cembalo", 500);

JavaScriptissä tietorakenne Set toteuttaa joukon:

let numbers = new Set();

numbers.add(1);
numbers.add(2);
numbers.add(3);

JavaScriptin perinteinen tapa luoda hakemisto on määritellä olio:

let weights = {};

weights["apina"] = 100;
weights["banaani"] = 1;
weights["cembalo"] = 500;

Uudempi tapa on käyttää erillistä tietorakennetta Map:

let weights = new Map();

weights.set("apina", 100);
weights.set("banaani", 1);
weights.set("cembalo", 500);

5. Järjestäminen

Järjestäminen (sorting) on klassinen algoritmiikan ongelma, jossa tehtävänä on järjestää annetut alkiot suuruusjärjestykseen. Järjestämiseen on kehitetty tehokkaita algoritmeja, jotka toimivat ajassa \(O(n \log n)\).

Tässä luvussa näemme, miten järjestämistä voi käyttää Pythonissa ja mitä hyötyä siitä voi olla tehokkaiden algoritmien toteuttamisessa. Tutustumme myös järjestämisen teoriaan ja muutamaan yleiseen järjestämisalgoritmiin.

Järjestäminen Pythonissa

Pythonissa listan sisältö voidaan järjestää metodilla sort:

numbers = [4, 2, 1, 2]
numbers.sort()
print(numbers) # [1, 2, 2, 4]

Pythonissa on myös funktio sorted, joka palauttaa listan järjestettynä:

numbers = [4, 2, 1, 2]
print(sorted(numbers)) # [1, 2, 2, 4]

Näissä tavoissa erona on, että metodi sort muuttaa olemassa olevaa listaa, kun taas funktio sorted muodostaa uuden listan.

Metodi sort ja funktio sorted toimivat tehokkaasti ajassa \(O(n \log n)\), minkä ansiosta niitä voidaan käyttää tehokkaiden algoritmien toteuttamisessa.

Esimerkki: Pienin ero

Tehtävä

Järjestetyssä listassa pienin ero on aina kahden vierekkäisen luvun välillä. Niinpä voimme ratkaista tehtävän tehokkaasti järjestämällä listan ja käymällä läpi kaikki vierekkäin olevat luvut. Esimerkiksi lista \([4,1,7,3,9]\) on järjestettynä \([1,3,4,7,9]\), jolloin pienimmän eron tuottavat luvut \(3\) ja \(4\) ovat vierekkäin.

Seuraava funktio min_diff toteuttaa algoritmin:

def min_diff(numbers):
    numbers = sorted(numbers)

    result = numbers[1] - numbers[0]
    for i in range(2, len(numbers)):
        result = min(result, numbers[i] - numbers[i - 1])

    return result

Algoritmi järjestää ensin listan kutsumalla funktiota sorted ja selvittää sitten muuttujaan result pienimmän eron kahden vierekkäisen luvun välillä.

Listan järjestäminen vie aikaa \(O(n \log n)\) ja vierekkäisten lukujen vertaileminen vie aikaa \(O(n)\), joten algoritmin aikavaativuus on \(O(n \log n)\).

Sivuvaikutusten välttäminen

Huomaa, että voisimme käyttää funktion alussa myös listan metodia sort:

def min_diff(numbers):
    numbers.sort()
    ...

Tässä olisi kuitenkin ongelmana, että funktio aiheuttaisi sivuvaikutuksen, koska parametrina annetun listan järjestäminen heijastuisi myös funktion min_diff kutsukohtaan. Tämä ei ole toivottava ilmiö, koska funktion ei pitäisi muuttaa listan sisältöä. Seuraavat koodit havainnollistavat asiaa:

Käytössä sort

numbers = [4, 1, 7, 3,9]
print(min_diff(numbers)) # 1
print(numbers) # [1, 3, 4, 7, 9]

Käytössä sorted

numbers = [4, 1, 7, 3,9]
print(min_diff(numbers)) # 1
print(numbers) # [4, 1, 7, 3,9]

Kun käytössä on metodi sort, funktion min_diff kutsuminen järjestää sivuvaikutuksena listan numbers. Kun käytössä on funktio sorted, lista numbers ei muutu, koska funktio sorted luo uuden järjestetyn listan. Niinpä parempi ratkaisu on toteuttaa funktio alkuperäisellä tavalla käyttäen funktiota sorted.

Hajautus vs. järjestäminen

Monessa tehtävässä on kaksi mahdollisuutta tehokkaan ratkaisun luomiseen: hajautus tai järjestäminen. Tarkastellaan esimerkkinä tehtävää, jonka ratkaisimme aiemmin hajautuksen avulla:

Tehtävä

Ratkaisimme tehtävän aiemmin hajautuksen avulla näin:

Algoritmi 1

def count_distinct(numbers):
    seen = set()

    for x in numbers:
        seen.add(x)

    return len(seen)

Voimme ratkaista tehtävän myös toisella tavalla järjestämisen avulla. Koska järjestetyssä listassa yhtä suuret luvut ovat peräkkäin, voimme käydä järjestetyn listan läpi ja kasvattaa laskuria aina luvun vaihtuessa.

Tässä on järjestämistä käyttävä algoritmi:

Algoritmi 2

def count_distinct(numbers):
    numbers = sorted(numbers)

    result = 1
    for i in range(1, len(numbers)):
        if numbers[i] != numbers[i - 1]:
            result += 1

    return result

Hajautusta käyttävä algoritmi vie aikaa \(O(n)\) ja järjestämistä käyttävä algoritmi vie aikaa \(O(n \log n)\), mutta miten nopeita algoritmit ovat käytännössä?

Tehdään testi, joka vertailee algoritmien tehokkuutta. Koska molemmat algoritmit ovat tehokkaita, toteutetaan testi niin, että listan koko on aina suuri (\(n=10^7\)). Koska listalla olevien lukujen suuruus saattaa vaikuttaa algoritmin tehokkuuteen, lisätään listalle satunnaisia lukuja väliltä \(1 \dots k\), missä \(k\) vaihtelee. Tämän avulla voidaan tutkia, miten lukujen suuruus vaikuttaa tehokkuuteen.

Testikoneella tulokset ovat seuraavat:

Tässä tapauksessa vaikuttaa, että hajautusta käyttävä algoritmi on tehokkaampi. Se on myös koodiltaan yksinkertaisempi, koska silmukassa riittää lisätä listan luvut set-rakenteeseen eikä vertailla vierekkäisiä lukuja keskenään.

Lisää järjestämisestä

Käänteinen järjestäminen

Parametri reverse muuttaa järjestämisen suunnan käänteiseksi:

numbers = [2, 4, 3, 5, 6, 1, 8, 7]
numbers.sort(reverse=True)
print(numbers) # [8, 7, 6, 5, 4, 3, 2, 1]

Moniosaiset alkiot

Jos järjestettävät alkiot ovat tupleja tai listoja, järjestys on ensisijaisesti ensimmäisen alkion mukaan, toissijaisesti toisen alkion mukaan, jne.

Esimerkiksi listassa olevat parit järjestyvät näin:

pairs = [(3, 5), (1, 3), (1, 2), (2, 4)]
pairs.sort()
print(pairs) # [(1, 2), (1, 3), (2, 4), (3, 5)]

Alkioiden vertailutapa

Parametrilla key voidaan määritellä funktio, joka muuttaa alkioita ennen kuin niitä vertaillaan toisiinsa. Parametria voidaan käyttää esimerkiksi näin:

numbers = [4, -1, 6, 2, -7, 8, 3, -5]
numbers.sort(key=abs)
print(numbers) # [-1, 2, 3, 4, -5, 6, -7, 8]

Tässä funktiona on abs eli itseisarvo, minkä seurauksena luvut järjestetään suuruuden mukaan välittämättä niiden etumerkistä.

Oma luokka

Pythonissa luokan olioita voidaan järjestää, kun luokkaan on toteutettu riittävästi metodeita olioiden vertailua varten. Esimerkiksi riittää, että on toteutettu metodit __eq__ ja __lt__, jolloin olioita voidaan vertailla operaattoreiden == ja < avulla. Seuraava koodi havainnollistaa asiaa:

class Location:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return (self.x, self.y) == (other.x, other.y)

    def __lt__(self, other):
        return (self.x, self.y) < (other.x, other.y)

    def __repr__(self):
        return str((self.x, self.y))

locations = []
locations.append(Location(1, 4))
locations.append(Location(4, 5))
locations.append(Location(2, 2))
locations.append(Location(1, 2))

locations.sort()

print(locations) # [(1, 2), (1, 4), (2, 2), (4, 5)]

Esimerkki: Ravintola

Tehtävä

Tällaisessa tehtävässä hyvä lähestymistapa on tarkastella tapahtumia aikajärjestyksessä. Tapahtumia on kahdenlaisia: asiakas saapuu ravintolaan tai asiakas lähtee ravintolasta. Jokaisen tapahtuman yhteydessä asiakkaiden määrä kasvaa tai vähenee yhdellä.

Esimerkin tapauksessa tapahtumat ovat:

Voimme ratkaista tehtävän tehokkaasti muodostamalla ensin asiakkaita vastaavat tapahtumat ja järjestämällä ne aikajärjestykseen. Tämän jälkeen voimme käydä läpi tapahtumat ja pitää yllä asiakkaiden määrää laskurissa.

Seuraavassa funktiossa listat arrivals ja departures sisältävät asiakkaiden saapumisajat ja lähtöajat. Esimerkin tapauksessa arrivals on [6, 3, 6, 1, 2] ja departures on [8, 7, 9, 5, 8].

def max_customers(arrivals, departures):
    events = []
    for time in arrivals:
        events.append((time, 1))
    for time in departures:
        events.append((time, 2))

    events.sort()

    counter = 0
    result = 0
    for event in events:
        if event[1] == 1:
            counter += 1
        if event[1] == 2:
            counter -= 1
        result = max(result, counter)

    return result

Funktio luo listan events, johon lisätään jokaista asiakasta kohden kaksi tapahtumaa pareina. Asiakkaan saapumisaika lisätään muodossa (time, 1) ja asiakkaan lähtöaika muodossa (time, 2). Sitten funktio järjestää listan, minkä seurauksena tapahtumat järjestyvät niiden aikojen mukaan.

Tapahtumien järjestämisen jälkeen lista events käydään läpi ja muuttuja counter pitää yllä asiakkaiden määrää. Muuttujaan result tallennetaan muuttujan counter suurin arvo tapahtumien käsittelyn aikana.

Tuloksena oleva algoritmi muodostuu kolmesta osasta. Tapahtumien luominen vie aikaa \(O(n)\), koska jokaisesta asiakkaasta muodostetaan kaksi tapahtumaa. Tapahtumien järjestäminen vie aikaa \(O(n \log n)\), ja tapahtumien läpikäynti vie aikaa \(O(n)\). Niinpä koko algoritmin aikavaativuus on \(O(n \log n)\).

Miten järjestäminen toimii?

Järjestämisalgoritmille annetaan lista alkioita ja sen tehtävänä on saada alkiot suuruusjärjestykseen. Yleensä lähtökohtana on, että algoritmi voi vertailla alkioita toisiinsa sekä vaihtaa alkioiden paikkoja listalla.

Yksinkertaiset järjestämisalgoritmit perustuvat vierekkäisten alkioiden vaihtamiseen keskenään ja niiden aikavaativuus on \(O(n^2)\). Yksi tällainen algoritmi on lisäysjärjestäminen, joka käy listan läpi vasemmalta oikealle ja siirtää kunkin alkion oikeaan kohtaan listan alkuosassa.

Järjestämiseen on olemassa myös tehokkaita algoritmeja, joiden aikavaativuus on \(O(n \log n)\). Yksi tällainen algoritmi on lomitusjärjestäminen, joka järjestää ensin listan vasemman ja oikean puoliskon rekursiivisesti erikseen ja yhdistää sitten järjestetyt puoliskot kokonaiseksi järjestetyksi listaksi.

Pythonin käyttämä järjestämisalgoritmi on Timsort, jossa on sekä lisäysjärjestämisen että lomitusjärjestämisen piirteitä. Algoritmin aikavaativuus on \(O(n \log n)\), ja se on suunniteltu niin, että se on erityisen tehokas monissa käytännössä vastaan tulevissa tilanteissa.

Yleisessä tapauksessa ei ole mahdollista luoda järjestämisalgoritmia, jonka aikavaativuus olisi tehokkaampi kuin \(O(n \log n)\). Tämä voidaan todistaa määrittämällä alaraja sille, montako kahden alkion vertailua algoritmissa tulee olla pahimmassa tapauksessa.

Järjestämisen toiminnan tutkiminen

Seuraava koodi havainnollistaa, mitä Python tekee järjestäessään listan sisällön:

import functools

def cmp(a, b):
    print("compare", a, b)
    return a - b

numbers = [4, 1, 3, 2]
numbers.sort(key=functools.cmp_to_key(cmp))
print(numbers)

Kun metodia sort kutsutaan yllä olevalla tavalla, se vertailee listalla olevien alkioiden järjestystä kutsumalla funktiota cmp. Funktio cmp saa parametreina alkiot a ja b ja sen tulee palauttaa

• negatiivinen arvo, jos a on pienempi kuin b,
• positiivinen arvo, jos a on suurempi kuin b, ja
• nolla, jos a ja b ovat yhtä suuria.

Tässä cmp on toteutettu niin, että se palauttaa lausekkeen a - b arvon, minkä ansiosta se järjestää alkiot pienimmästä suurimpaan.

Metodi sort muuttaa listan alkioiden järjestystä funktion cmp perusteella. Funktio cmp tulostaa kaikki tekemänsä vertailut, mikä antaa tietoa metodin sort tekemistä vertailuista. Koodin tulostus on seuraava:

compare 1 4
compare 3 1
compare 3 4
compare 3 1
compare 2 3
compare 2 1
[1, 2, 3, 4]

Tämä tarkoittaa, että metodi sort vertailee ensin lukuja 1 ja 4, sitten lukuja 3 ja 1, jne. Kuuden vertailun jälkeen metodi on saanut listan järjestykseen.

Järjestäminen muissa kielissä

Eri ohjelmointikielissä on valmiita menetelmiä järjestämiseen. Kielten välillä on eroja siinä, mihin algoritmeihin järjestäminen perustuu, mutta yleensä valmiit menetelmät ovat tehokkaita ja ne on toteutettu hyvin.

C++:ssa on saatavilla funktio std::sort, jolle annetaan parametrina iteraattori järjestettävän välin alkuun ja loppuun. Funktiota voidaan käyttää seuraavasti:

std::vector<int> numbers;
...
std::sort(numbers.begin(), numbers.end());

Javassa voidaan käyttää luokan Collections metodia sort:

ArrayList<Integer> numbers = new ArrayList<>();
...
Collections.sort(numbers);

JavaScriptissa taulukon metodi sort järjestää sen sisällön. Metodin käyttäminen voi kuitenkin aiheuttaa yllätyksiä:

numbers = [2, 11, 1, 3];
numbers.sort();
console.log(numbers); // [1, 11, 2, 3]

Tässä järjestettävänä on kokonaislukuja sisältävä lista, mutta luku 11 menee järjestykseen ennen lukua 2. Syynä tähän on, että metodi sort käsittelee alkioita oletuksena merkkijonoina, jolloin 11 on pienempi kuin 2. Metodille voi kuitenkin antaa seuraavasti vertailufunktion lukujen järjestämistä varten:

numbers = [2, 11, 1, 3];
numbers.sort((a, b) => a - b);
console.log(numbers); // [1, 2, 3, 11]

6. Omat tietorakenteet

Tietorakenteen toiminta voidaan esittää joukkona metodeita, joilla on tietyt parametrit ja joiden kutsuminen antaa tietyn tuloksen. Esimerkiksi Pythonin listassa on metodit append, count ja index, joiden avulla pystyy lisäämään alkion listaan, laskemaan alkion esiintymiskerrat sekä etsimään alkion indeksin.

Luokkien avulla voimme toteuttaa itse tietorakenteita, jotka sisältävät haluttuja metodeja. Usein tällaisen luokan sisällä on jokin Pythonin tietorakenne, kuten lista tai sanakirja. Luokan etuna on, että se tarjoaa tietorakenteelle siistin rajapinnan, jonka takana on tietorakenteen sisäinen toteutus.

Esimerkki: Pino

Tehtävä

Luokka Stack on helppoa toteuttaa Pythonin listan avulla, koska alkion lisääminen listan loppuun ja poistaminen listan lopusta toimivat ajassa \(O(1)\). Voimme toteuttaa luokan seuraavasti:

class Stack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append(x)

    def top(self):
        return self.stack[-1]

    def pop(self):
        self.stack.pop()

Ideana on, että luokan sisällä määritellään lista stack, johon tallennetaan pinon alkiot. Metodit push ja pop toteutetaan listan metodien append ja pop avulla ja metodi top toteutetaan hakemalla listan viimeinen alkio.

Seuraava koodi testaa luokan toimintaa:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.top()) # 3
print(s.top()) # 3
s.pop()
print(s.top()) # 2

Tässä tapauksessa luokka Stack rajoittaa listan toimintaa, koska luokan metodeilla on mahdollista käsitellä vain listan viimeistä alkiota. Luokan käyttäjän ei tarvitse tietää, miten luokka on toteutettu sisäisesti, vaan hän voi luottaa siihen, että saatavilla on metodit push, top ja pop.

Huomaa, että voimme kuitenkin käsitellä luokan sisäistä tietoa, jos tiedämme, miten luokka on toteutettu. Seuraava koodi havainnollistaa asiaa:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.stack) # [1, 2, 3]

Luokka tallentaa sisäisesti pinon sisällön listaan stack, jonka sisältöön pääsee käsiksi, vaikka luokan metodeilla voi käsitellä vain pinon ylintä alkiota.

Älä tee luokkaa näin

Seuraava tapa luokan toteuttamiseen ei ole toimiva:

class Stack:
    stack = []

    def push(self, x):
        self.stack.append(x)

    def top(self):
        return self.stack[-1]

    def pop(self):
        self.stack.pop()

Erona aiempaan luokkaan tässä luokassa ei ole alustusmetodia __init__ vaan lista stack luodaan luokan päätasolla. Päältä päin luokka vaikuttaa toimivalta:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.top()) # 3

Ongelmana tässä toteutuksessa on kuitenkin, että lista stack on yhteinen kaikille luokasta luoduille olioille. Seuraava koodi havainnollistaa ongelmaa:

a = Stack()
b = Stack()
a.push(1)
b.push(2)
print(a.top()) # 2

Koodi lisää pinoon a luvun 1 ja pinoon b luvun 2. Tämän jälkeen koodi hakee pinon a ylimmän alkion. Tuloksen pitäisi olla 1, mutta se onkin 2, koska pinoilla on yhteinen lista stack. Tämän seurauksena alkion lisääminen toiseen pinoon lisää sen kumpaankin pinoon eikä luokka toimi halutulla tavalla.

Lisää ominaisuuksia luokkaan

Aiempi luokka Stack toimii sinänsä, mutta siinä on vielä joitakin puutteita. Ensinnäkään pinon sisällön tulostaminen ei anna hyödyllistä tietoa:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s) # <__main__.Stack object at 0x7fd6c4e23ee0>

Voimme korjata tämän lisäämällä luokkaan metodin __repr__, jonka tehtävänä on palauttaa tekstimuotoinen esitys luokan sisällöstä. Voimme toteuttaa metodin niin, että se palauttaa suoraan listan stack sisällön tekstinä:

    def __repr__(self):
        return str(self.stack)

Tämän muutoksen jälkeen pinon sisältö tulostuu näin:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s) # [1, 2, 3]

Toinen puute on, että pinon kokoa ei pysty selvittämään funktiolla len, vaan tämä aiheuttaa virheilmoituksen. Voimme korjata tämän lisäämällä luokkaan seuraavan metodin __len__:

    def __len__(self):
        return len(self.stack)

Metodia __len__ kutsutaan silloin, kun luokasta tehty olio annetaan funktion len parametriksi. Tässä tapauksessa metodin riittää palauttaa listan stack koko. Nyt seuraava koodi toimii järkevällä tavalla:

s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(len(s)) # 3

Metodeissa pop ja top on vielä puutteena, että ne eivät ota huomioon tilannetta, jossa pino on tyhjä. Tässä tilanteessa ei ole mahdollista poistaa tai hakea pinon ylintä alkiota. Voimme lisätä metodeihin virheenkäsittelyn seuraavasti:

    def pop(self):
        if len(self.stack) == 0:
            raise IndexError("pop from empty stack")
        return self.stack.pop()

    def top(self):
        if len(self.stack) == 0:
            raise IndexError("top from empty stack")
        return self.stack[-1]

Nyt jos metodeita kutsutaan pinon ollessa tyhjä, metodit tuottavat IndexError-virheen, jossa on tekstimuotoinen kuvaus virheen syystä. Seuraava koodi havainnollistaa asiaa:

s = Stack()
s.push(1)
s.pop()
s.pop() # IndexError: pop from empty stack

Esimerkki: Tehokas lisäys

Tehtävä

Tämä luokka vasta muuten aiempaa luokkaa Stack, mutta siinä on uusi metodi push_many, jonka avulla voi lisätä saman alkion useita kertoja pinoon. Luokan toteutuksessa on haasteena, että myös metodin push_many tulee toimia ajassa \(O(1)\) riippumatta siitä, miten monta kertaa alkio lisätään.

Seuraava tapa toteuttaa metodi push_many ei ole riittävä:

    def push_many(self, x, k):
        for i in range(k):
            self.push(x)

Tässä ongelmana on, että metodissa on silmukka, joka vie aikaa \(O(k)\), eli metodin suoritusaika riippuu siitä, montako kertaa alkio lisätään. Kuitenkin aikavaativuuden tulisi olla \(O(1)\) eli metodissa ei saa olla silmukkaa.

Hyödyllinen näkökulma luokan suunnittelussa on, että luokan ainoa vaatimus on toteuttaa halutut operaatiot ajassa \(O(1)\). Muilta osin voimme päättää vapaasti, millainen on luokan sisäinen toteutus. Erityisesti luokan ei ole pakko tallentaa jokaista alkiota erikseen pinoon, vaan sen riittää antaa vaikutelma tällaisesta pinosta.

Tehokas tapa toteuttaa luokka on tallentaa pinoon sisäisesti pareja muotoa \((k,x)\): alkio \(x\) esiintyy \(k\) kertaa. Esimerkiksi koodi

s = SuperStack()
s.push_many(3, 8)
s.push(4)
s.push_many(2, 5)

luo pinon \([(3,8),(1,4),(2,5)]\), joka esittää tiivistetyssä muodossa pinon \([8,8,8,4,5,5]\) sisällön. Tämän ansiosta jokainen metodin push tai push_many kutsu lisää vain yhden alkion pinoon. Vastaavasti metodit top ja pop täytyy toteuttaa niin, että ne käsittelevät oikealla tavalla pinossa olevia pareja. Luokka voidaan toteuttaa seuraavasti:

class SuperStack:
    def __init__(self):
        self.stack = []

    def push(self, x):
        self.stack.append((1, x))

    def push_many(self, k, x):
        self.stack.append((k, x))

    def top(self):
        return self.stack[-1][1]

    def pop(self):
        last = self.stack[-1]
        if last[0] == 1:
            self.stack.pop()
        else
            self.stack[-1] = (last[0] - 1, last[1])

Metodi top palauttaa pinon ylimmän parin toisen jäsenen, koska jokaisen parin toinen jäsen vastaa pinossa olevaa alkiota. Metodi pop puolestaan tarkastelee pinon ylimmän parin ensimmäistä jäsentä eli toistokertojen määrää. Jos alkio toistuu kerran, metodi poistaa parin pinosta. Jos taas alkio toistuu useamman kerran, metodi vähentää toistokertojen määrää yhdellä.

Tämän toteutuksen ansiosta jokainen luokan metodi toimii ajassa \(O(1)\), koska jokaisessa metodissa on kiinteä määrä komentoja eikä silmukoita.

Esimerkki: Moodi

Tehtävä

Tämä on muunnelma aiemmasta tehtävästä, jossa laskettavana oli annetun listan lukujen moodi. Erona on, että luokan Mode avulla voi vuorotellen lisätä lukuja listalle sekä kysyä, mikä on tähän mennessä lisättyjen lukujen moodi. Esimerkiksi luokkaa voidaan käyttää näin:

m = Mode()
m.add(1)
m.add(1)
m.add(2)
print(m.mode()) # 1
m.add(2)
m.add(2)
print(m.mode()) # 2

Koska ainoa luokalta kysyttävä asia on listan lukujen moodi, meidän ei tarvitse tallentaa muistiin listaa vaan vain tarvittavat tiedot moodin laskemiseen. Voimme toteuttaa luokan käyttäen sanakirjaa, johon on tallennettu jokaisen luvun esiintymiskertojen määrä. Lisäksi luokassa on muistissa tämänhetkinen moodi.

class Mode:
    def __init__(self):
        self.count = {}
        self.status = (0, 0)

    def add(self, x):
        if x not in self.count:
            self.count[x] = 0
        self.count[x] += 1
        self.status = max(self.status, (self.count[x], x))

    def mode(self):
        return self.status[1]

Sanakirja count sisältää kunkin luvun esiintymiskerran, ja parissa status on tieto moodista muodossa \((k,x)\): moodi on luku \(x\), joka esiintyy listassa \(k\) kertaa. Kun listalle lisätään luku \(x\), moodia päivitetään, jos luku \(x\) on lisäämisen jälkeen listan moodi. Tämä onnistuu kätevästi max-funktion avulla, joka vertaa ensisijaisesti parin ensimmäistä jäsentä ja toissijaisesti toista jäsentä.

Luokan kummassakin metodissa on vain yksittäisiä komentoja, joten ne toimivat vaatimusten mukaisesti ajassa \(O(1)\).

7. Puut ja rekursio

Puu (tree) on tietorakenne, joka muodostuu eri tasoilla olevista solmuista (node). Puiden avulla voidaan esittää hierarkioita, joissa eri tasoilla olevat solmut ovat yhteydessä toisiinsa.

Tarkastellaan esimerkkinä seuraavaa puuta:

Tässä puussa on seitsemän solmua, jotka ovat kolmella tasolla.

Puun ylin solmu on nimeltään juuri (root). Solmun lapsi (child) on yhtä alemmalla tasolla oleva solmu, johon pääsee kulkemaan solmusta. Solmun vanhempi (parent) on solmu, jonka lapsi solmu on. Jos solmulla ei ole lapsia, se on lehti (leaf).

Esimerkissä puun juuri on solmu 1. Solmun 1 lapset ovat solmut 4, 5 ja 2. Solmun 4 vanhempi on solmu 1. Puun lehtiä ovat solmut 3, 7, 5 ja 6.

Jokaisella solmulla juurta lukuun ottamatta on tarkalleen yksi vanhempi. Tämän vuoksi on olemassa yksikäsitteinen reitti juuresta mihin tahansa solmuun kulkemalla yhteyksiä alaspäin. Juurella ei ole vanhempaa.

Solmun alipuu (subtree) sisältää solmut, joihin pääsee kulkemalla solmusta alaspäin yhteyksiä pitkin. Esimerkissä solmun 1 alipuu sisältää puun kaikki solmut ja solmun 4 alipuu sisältää solmut 4, 3 ja 7.

Solmun syvyys (depth) tarkoittaa, miten matalalla solmu on puussa. Juuren syvyys on 0 ja muilla solmuilla syvyys on yhtä suurempi kuin niiden vanhemman syvyys. Esimerkissä solmun 1 syvyys on 0, solmun 4 syvyys on 1 ja solmun 3 syvyys on 2.

Puun korkeus (height) on suurin puussa esiintyvä solmun syvyys. Esimerkissä puun korkeus on 2, koska solmujen 3, 7 ja 6 syvyys on 2.

Puun käsittely

Voimme esittää puun solmun Pythonissa seuraavan luokan Node avulla:

class Node:
    def __init__(self, value, children=[]):
        self.value = value
        self.children = children

    def __repr__(self):
        return str(self.value)

Solmun luonnissa annetaan kaksi tietoa: solmussa oleva arvo sekä lista solmun lapsista. Jos listaa ei anneta, se on oletuksena tyhjä. Esimerkiksi seuraava koodi luo kolme solmua niin, että solmut 2 ja 3 ovat solmun 1 lapsia.

node2 = Node(2)
node3 = Node(3)
node1 = Node(1, [node2, node3])

Solmun merkkijonoesityksenä on solmussa oleva arvo:

node = Node(1)
print(node) # 1

Tämän luokan avulla puu voidaan määritellä rakentamalla sen juurisolmu. Esimerkiksi seuraava koodi luo luvun alussa olleen esimerkkipuun:

tree = Node(1, [Node(4, [Node(3), Node(7)]),
                Node(5),
                Node(2, [Node(6)])])

Puun läpikäynti

Luonteva tapa käsitellä puuta on käyttää rekursiota. Esimerkiksi seuraava funktio traverse käy läpi kaikki solmut, jotka ovat solmun node alipuussa:

def traverse(node):
    print(node)
    for child in node.children:
        traverse(child)

Kun funktiolle annetaan viittaus puun juureen, funktio käy läpi kaikki puun solmut:

traverse(tree)

Esimerkkipuussa funktion tulostus on seuraava:

1
4
3
7
5
2
6

Funktio traverse tulostaa ensin sille annetun solmun arvon (node.value). Tämän jälkeen funktio käy läpi kaikki solmun lapset (node.children) ja kutsuu jokaisen lapsen kohdalla itseään rekursiivisesti.

Voimme vielä selventää funktion toimintaa muuttamalla sitä seuraavasti:

def traverse(node):
    print("enter", node.value)
    for child in node.children:
        traverse(child)
    print("leave", node.value)

Nyt funktio tulostaa ”enter \(x\)”, kun solmun \(x\) käsittely alkaa, ja ”leave \(x\)”, kun solmun \(x\) käsittely päättyy. Esimerkkipuussa funktio tulostaa:

enter 1
enter 4
enter 3
leave 3
enter 7
leave 7
leave 4
enter 5
leave 5
enter 2
enter 6
leave 6
leave 2
leave 1

Tiedon laskeminen puusta

Puita käsitellään usein funktioilla, jotka laskevat rekursiivisesti jonkin puuhun liittyvän tiedon. Tarkastellaan esimerkkinä funktiota count_nodes, joka laskee, montako solmua on solmun node alipuussa:

def count_nodes(node):
    result = 1
    for child in node.children:
        result += count_nodes(child)
    return result

Funktiota voidaan käyttää näin:

tree = Node(1, [Node(4, [Node(3), Node(7)]),
                Node(5),
                Node(2, [Node(6)])])

print(count_nodes(tree)) # 7

Funktio laskee solmujen määrän muuttujaan result. Muuttujan alkuarvo on 1, jolloin siihen on laskettu mukaan solmu node. Tämän jälkeen funktio käy läpi solmun lapset ja laskee mukaan rekursiivisesti solmujen määrät lasten alipuissa. Lopuksi funktio palauttaa solmujen määrän.

Katsotaan tarkemmin, miten funktio laskee solmujen määrän esimerkissä:

Kun funktiolle annetaan viittaus solmuun 1, muuttuja result on alussa 1 ja funktio lisää siihen silmukassa solmun 1 lasten solmujen määrät. Solmun 1 lapset ovat solmut 4, 5 ja 2. Solmun 4 alipuussa on 3 solmua, solmun 5 alipuussa on 1 solmu ja solmun 2 alipuussa on 2 solmua. Niinpä muuttujaan result lisätään määrät 3, 1 ja 2 ja solmujen määräksi saadaan 1 + 3 + 1 + 2 = 7.

Voimme vielä selventää funktion toimintaa lisäämällä siihen tulostusta:

def count_nodes(node):
    result = 1
    for child in node.children:
        result += count_nodes(child)
    print("subtree of node", node, "has", result, "nodes")
    return result

Tämän muutoksen jälkeen funktio tulostaa jokaisesta solmusta tiedon, montako solmua sen alipuussa on:

subtree of node 3 has 1 nodes
subtree of node 7 has 1 nodes
subtree of node 4 has 3 nodes
subtree of node 5 has 1 nodes
subtree of node 6 has 1 nodes
subtree of node 2 has 2 nodes
subtree of node 1 has 7 nodes

Monia puihin liittyviä asioita voidaan laskea samalla idealla: määritellään sopivat muuttujat, käydään läpi silmukassa solmun lapset rekursiivisesti ja päivitetään muuttujia sopivalla tavalla. Esimerkiksi seuraava funktio count_height laskee puun korkeuden eli suurimman puussa olevan solmun syvyyden:

def count_height(node):
    result = 0
    for child in node.children:
        result = max(result, count_height(child) + 1)
    return result

Tässä tapauksessa silmukka käy läpi solmun lapset ja valitsee funktion max avulla suurimman alipuun korkeuden, johon lisätään 1. Esimerkkipuussa solmun 1 lasten alipuiden korkeudet ovat 1, 0 ja 1. Näistä valitaan suurin korkeus 1, johon lisätään 1, josta saadaan solmun 1 alipuun korkeudeksi 2.

Syvyyksien käsittely

Välillä hyödyllinen tekniikka on lisätä rekursiiviseen funktioon parametri, joka pitää yllä käsiteltävän solmun syvyyttä. Esimerkiksi seuraava funktio tulostaa puun jokaisen solmun syvyyden.

def traverse(node, depth):
    print("node", node, "depth", depth)
    for child in node.children:
        traverse(child, depth + 1)

Funktiota kutsuttaessa juuren syvyydeksi annetaan 0, ja funktio kasvattaa syvyyttä yhdellä aina liikkuessaan alempaan solmuun. Funktiota voidaan käyttää näin:

tree = Node(1, [Node(4, [Node(3), Node(7)]),
                Node(5),
                Node(2, [Node(6)])])

traverse(tree, 0)

Tässä tapauksessa tulostus on:

node 1 depth 0
node 4 depth 1
node 3 depth 2
node 7 depth 2
node 5 depth 1
node 2 depth 1
node 6 depth 2

Tehdään seuraavaksi monimutkaisempi funktio get_depths, jonka tulisi palauttaa listana kaikkien puun solmujen syvyydet pienimmästä suurimpaan. Esimerkkipuussa funktion tulisi palauttaa lista [0, 1, 1, 1, 2, 2, 2]. Hyvä tapa tehdä tällainen funktio on tehdä sen avuksi toinen funktio, jolla on enemmän parametreja:

def get_depths(node):
    depths = []
    get_depths_helper(node, 0, depths)
    return sorted(depths)

def get_depths_helper(node, depth, depths):
    depths.append(depth)
    for child in node.children:
        get_depths_helper(child, depth + 1, depths)

Funktio toimii nyt näin:

tree = Node(1, [Node(4, [Node(3), Node(7)]),
                Node(5),
                Node(2, [Node(6)])])

print(get_depths(tree)) # [0, 1, 1, 1, 2, 2, 2]

Tässä funktio get_depths luo ensin listan depths solmujen syvyyksille. Tämän jälkeen funktio kutsuu funktiota get_depths_helper, joka lisää syvyydet listalle. Lopuksi funktio get_depths palauttaa listan järjestettynä.

Funktiolla get_depths_helper on kaksi lisäparametria: parametri depth pitää yllä tietoa solmun syvyydestä ja parametri depths on viittaus listaan, johon syvyydet tallennetaan. Huomaa, että koska Pythonissa lista välitetään viittauksena, kaikki syvyydet lisätään samalle listalle, joka on määritelty funktiossa get_depths. Tämän ansiosta tiedot saadaan kerättyä samalle listalle eri funktiokutsuista.

Tässä on vielä toinen tapa toteuttaa funktio get_depths, jossa funktiolle get_depths_helper ei anneta parametrina listaa vaan funktio palauttaa listan.

def get_depths(node):
    return sorted(get_depths_helper(node, 0))

def get_depths_helper(node, depth):
    depths = [depth]
    for child in node.children:
        depths += get_depths_helper(child, depth + 1)
    return depths

Tässä tapauksessa funktio get_depths_helper muodostaa listan, johon lisätään ensin käsiteltävän solmun syvyys ja sitten alipuiden listat, jotka saadaan rekursiivisesti. Funktio get_depths saa lopulta listan, jossa on kaikkien solmujen syvyydet, ja funktio palauttaa tämän listan järjestettynä.

Luokka paremmaksi

Tarkastellaan vielä luokan Node määrittelyä:

class Node:
    def __init__(self, value, children=[]):
        self.value = value
        self.children = children

    def __repr__(self):
        return str(self.value)

Luokka toimii tällaisenaan yleensä hyvin, mutta Pythonissa on yllättävä piirre, joka voi aiheuttaa ongelmia joissakin tilanteissa. Seuraava koodi esittelee asiaa:

node1 = Node(1)
node2 = Node(2)

node1.children.append(node2)

print(node1.children) # [2]
print(node2.children) # [2]

Tässä luotiin kaksi solmua, joilla ei ole lapsia, minkä jälkeen solmun 1 lapseksi lisättiin solmu 2. Yllättäen kuitenkin solmu 2 ilmestyi myös itsensä lapseksi.

Tämä ilmiö johtuu siitä, että oletusparametri [] luodaan vain kerran ja se on yhteinen kaikille metodikutsuille. Tämän vuoksi molemmat solmut viittaavat samaan tyhjään listaan, johon lisätty solmu näkyy kummallekin solmulle.

Voimme korjata asian muuttamalla alustusmetodia näin:

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children if children else []

    def __repr__(self):
        return str(self.value)

Nyt parametrin children oletusarvo on None. Jos parametria ei ole annettu, alustusmetodi luo tyhjän listan. Tämän muutoksen jälkeen jokainen olio saa oman tyhjän listan ja koodi toimii järkevästi:

node1 = Node(1)
node2 = Node(2)

node1.children.append(node2)

print(node1.children) # [2]
print(node2.children) # []

Vielä toinen puute luokassa on, että solmun tulostaminen näyttää vain solmussa olevan arvon eikä solmun lapsia:

tree = Node(1, [Node(2, [Node(3), Node(4)]), Node(5)])
print(tree) # 1

Pythonissa on periaatteena, että metodin __repr__ tulisi antaa sellainen merkkijonoesitys oliosta, joka luo olion. Tämä ei selkeästi toteudu tällä hetkellä.

Voimme korjata asian muuttamalla luokkaa näin:

class Node:
    def __init__(self, value, children=None):
        self.value = value
        self.children = children if children else []

    def __repr__(self):
        if self.children == []:
            return f"Node({self.value})"
        else:
            return f"Node({self.value}, {self.children})"

Tämän jälkeen solmun tulostaminen antaa merkkijonoesityksen, joka sisältää myös solmun lapset ja jonka perusteella olio voitaisiin luoda:

tree = Node(1, [Node(2, [Node(3), Node(4)]), Node(5)])
print(tree) # Node(1, [Node(2, [Node(3), Node(4)]), Node(5)])

Esimerkki: Työntekijät

Puiden avulla voidaan mallintaa monia hierarkisia rakenteita. Esimerkiksi organisaation henkilöstörakenne voidaan esittää puuna, jossa jokainen työntekijä on yksi puun solmuista ja solmun lapset ovat työntekijän alaiset.

Seuraavaan luokkaan voidaan tallentaa työntekijän nimi ja lista alaisista:

class Employee:
    def __init__(self, name, subordinates=[]):
        self.name = name
        self.subordinates = subordinates

    def __repr__(self):
        return self.name

Luokkaa voidaan käyttää näin:

def list_employees(employee, level=0):
    print(" "*(level*4), employee)
    for subordinate in employee.subordinates:
        list_employees(subordinate, level + 1)

staff = Employee("Emilia",
                 [
                    Employee("Antti"),
                    Employee("Leena", [Employee("Jussi")]),
                    Employee("Matti", [Employee("Sasu")])
                 ])

list_employees(staff)

Koodin tulostus on:

Emilia
    Antti
    Leena
        Jussi
    Matti
        Sasu

Esimerkki: Kuningattaret

Ongelman ratkaisuiden järjestelmällinen läpikäynti voidaan myös nähdä puun läpikäyntinä. Tämä menetelmä tunnetaan nimellä peruuttava haku (backtracking). Tarkastellaan esimerkkinä seuraavaa tehtävää:

Tehtävä

Voimme lähestyä ongelmaa käymällä läpi puuta, jonka juurena on tyhjä ruudukko. Jokaisessa solmussa lapsia ovat ruudukot, joihin on lisätty kuningatar seuraavalle riville. Seuraava kuva näyttää osan tapaukseen \(n=4\) liittyvästä puusta:

Tällä tavalla voidaan käydä läpi kaikki mahdolliset tavat lisätä kuningattaret ruudukkoon ja laskea mukaan ratkaisut, joissa kaksi kuningatarta ei uhkaa toisiaan. Huomaa, että puuta ei ole olemassa valmiina muistissa vaan sitä rakennetaan samaan aikaan läpikäynnin kanssa.

Seuraava koodi toteuttaa läpikäynnin:

def count_queens(n):
    return count(n, 0, [])

def count(n, row, queens):
    if row == n:
        return 1
    result = 0
    for col in range(n):
        attacks = [attack(queen, (row, col)) for queen in queens]
        if not any(attacks):
            result += count(n, row + 1, queens + [(row, col)])
    return result

def attack(queen1, queen2):
    if queen1[0] == queen2[0] or queen1[1] == queen2[1]:
        return True
    if abs(queen1[0] - queen2[0]) == abs(queen1[1] - queen2[1]):
        return True
    return False

print(count_queens(4)) # 2
print(count_queens(8)) # 92

Funktiolle count annetaan kolme parametria: ruudukon koko, seuraavaksi lisättävän kuningattaren rivi sekä lista lisätyistä kuningattarista. Rivit ja sarakkeet on numeroitu \(0 \dots n-1\) ja kuningattaret esitetään muodossa \((y,x)\), jossa \(y\) ja \(x\) ovat kuningattaren rivi ja sarake. Funktio käy läpi kaikki sarakkeet ja jatkaa hakua rekursiivisesti tilanteissa, joissa kuningatar voidaan lisätä sarakkeeseen ilman, että se uhkaa aiemmin lisättyä kuningatarta.

Funktio attack tarkastaa, uhkaavatko kaksi kuningatarta toisiaan. Ensimmäinen ehto tarkastaa tapaukset, joissa kuningattaret uhkaavat toisiaan vaaka- tai pystysuuntaisesti. Toinen ehto puolestaan tarkastaa tapaukset, joissa kuningattaret uhkaavat toisiaan vinosuuntaisesti. Tämä voidaan tunnistaa siitä, että vaaka- ja pystysuuntaisten etäisyyksien itseisarvot ovat samat.

Koodissa on käytössä kätevä funktio any, joka palauttaa arvon True silloin, kun annetulla listalla on ainakin kerran arvo True. Niinpä not any(attacks) tarkoittaa, että jokainen listan attacks arvo on False eli lisättävä kuningatar ei uhkaa mitään aiemmin lisättyä kuningatarta.

8. Verkkoalgoritmit

Verkko (graph) on tietorakenne, joka muodostuu solmuista (node) ja kaarista (edge). Jokainen verkon kaari yhdistää kaksi solmua toisiinsa.

Esimerkiksi seuraavassa verkossa on viisi solmua ja seitsemän kaarta:

Solmun naapuri (neighbor) on toinen solmu, johon siitä pääsee kaarella. Esimerkiksi solmun 1 naapurit ovat solmut 2, 3 ja 4. Solmun aste (degree) on naapurien määrä. Esimerkiksi solmun 1 aste on 3, koska sillä on 3 naapuria.

Kahden solmun välinen polku (path) on kaaria pitkin kulkeva reitti. Tässä on joitakin mahdollisia polkuja solmusta 1 solmuun 5:

• 1 → 2 → 5
• 1 → 4 → 5
• 1 → 3 → 4 → 5
• 1 → 3 → 4 → 2 → 5

Esimerkkejä verkkojen käyttötarkoituksista:

• Tieverkko: Solmut ovat kaupunkeja ja kaaret ovat teitä. Kahden solmun välinen polku vastaa kahden kaupungin välistä reittiä.
• Kontaktiverkko: Solmut ovat ihmisiä ja kaaret ovat kontakteja. Kahden solmun välinen polku kuvaa, mitä kautta ihmiset tuntevat toisensa.
• Tietoverkko: Solmut ovat tietokoneita ja kaaret ovat yhteyksiä. Kahden solmun välinen polku kuvaa, mitä kautta voidaan välittää tietoa.

Verkot ohjelmoinnissa

Tavallinen tapa käsitellä verkkoa ohjelmoinnissa on pitää muistissa kunkin solmun vieruslistaa (adjacency list). Solmun \(x\) vieruslista sisältää kaikki solmut, joihin pääsee kaarella solmusta \(x\).

Pythonissa voimme tallentaa verkon sanakirjana, jossa avaimet ovat solmuja ja arvot vieruslistoja. Esimerkkiverkko voidaan tallentaa seuraavasti:

graph = {
    1: [2, 3, 4],
    2: [1, 4, 5],
    3: [1, 4],
    4: [1, 2, 3, 5],
    5: [2, 4]
}

Usein on kätevää määritellä verkkoa varten luokka, jossa on metodi kaarien lisäämiseen. Luokka voidaan toteuttaa seuraavasti:

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {node: [] for node in nodes}

    def add_edge(self, a, b):
        self.graph[a].append(b)
        self.graph[b].append(a)

Tässä konstruktorille annetaan lista nodes, jossa on verkon solmut. Tämän perusteella luodaan sanakirja graph, joka sisältää vieruslistat. Aluksi jokainen vieruslista on tyhjä, ja metodi add_edge lisää kaaren solmujen a ja b välille.

Nyt voimme luoda esimerkkiverkon näin:

g = Graph([1, 2, 3, 4, 5])

g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(1, 4)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 4)
g.add_edge(4, 5)

Syvyyshaku

Syvyyshaku (depth-first search) eli DFS on menetelmä, jonka avulla voidaan käydä läpi kaikki verkon solmut, joihin pääsee lähtösolmusta kaaria pitkin. Syvyyshaku voidaan toteuttaa rekursiivisesti verkon vieruslistojen avulla.

Seuraava koodi toteuttaa syvyyshaun:

class DFS:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {node: [] for node in nodes}

    def add_edge(self, a, b):
        self.graph[a].append(b)
        self.graph[b].append(a)

    def visit(self, node):
        if node in self.visited:
            return
        self.visited.add(node)

        for next_node in self.graph[node]:
            self.visit(next_node)

    def search(self, start_node):
        self.visited = set()
        self.visit(start_node)
        return self.visited

Metodi search suorittaa syvyyshaun solmusta start_node alkaen ja palauttaa haun löytämät solmut. Metodi luo ensin joukon visited, johon merkitään, missä solmuissa haku on käynyt. Tämän jälkeen metodi kutsuu rekursiivista metodia visit, joka toteuttaa haun.

Metodi visit saa parametriksi vierailtavan solmun node. Jos haku on käynyt solmussa, metodin suoritus päättyy, ja muuten solmu lisätään joukkoon visited. Tämän jälkeen metodi käy läpi solmun node vieruslistan ja kutsuu itseään rekursiivisesti jokaiselle solmun node naapurille.

Seuraava koodi esittelee syvyyshaun toimintaa:

d = DFS([1, 2, 3, 4, 5])

d.add_edge(1, 2)
d.add_edge(1, 3)
d.add_edge(1, 4)
d.add_edge(2, 4)
d.add_edge(2, 5)
d.add_edge(3, 4)
d.add_edge(4, 5)

print(d.search(1))

Koodin tulostus on seuraava:

{1, 2, 3, 4, 5}

Tämä tarkoittaa, että solmusta 1 pääsee solmuihin 1, 2, 3, 4 ja 5 eli solmusta 1 pääsee kulkemaan kaikkiin verkon solmuihin.

Komponentit ja yhtenäisyys

Verkon komponentti (component) sisältää solmut, jotka ovat yhteydessä toisiinsa kaaria pitkin. Esimerkiksi seuraavassa verkossa on kolme komponenttia: \(\{1,2,3\}\), \(\{4,5,6,7\}\) ja \(\{8\}\).

Verkko on yhtenäinen (connected), jos siinä on tasan yksi komponentti eli minkä tahansa kahden solmun välillä on reitti kaaria pitkin. Esimerkiksi seuraava verkko on yhtenäinen, koska sen ainoa komponentti on \(\{1,2,3,4,5\}\).

Esimerkiksi tieverkossa komponentti sisältää kaupungit, joiden välillä pystyy kulkemaan teitä pitkin. Tieverkko on yhtenäinen, jos minkä tahansa kahden kaupungin välillä on olemassa reitti teitä pitkin.

Syvyyshaun avulla voidaan etsiä verkon komponentit käymällä läpi verkon solmut ja aloittamalla uusi haku aina, kun vastaan tulee solmu, joka ei ole vielä missään komponentissa. Seuraava luokka Components toteuttaa etsinnän:

class Components:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {node: [] for node in nodes}

    def add_edge(self, a, b):
        self.graph[a].append(b)
        self.graph[b].append(a)

    def visit(self, node):
        if node in self.components:
            return
        self.components[node] = self.counter

        for next_node in self.graph[node]:
            self.visit(next_node)

    def find_components(self):
        self.counter = 0
        self.components = {}

        for node in self.nodes:
            if node not in self.components:
                self.counter += 1
                self.visit(node)

        return self.components