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:

Listan koko `n`	Algoritmi 1	Algoritmi 2	Algoritmi 3
1000	0.17 s	0.00 s	0.00 s
10000	15.93 s	0.00 s	0.00 s
100000	–	0.01 s	0.00 s
1000000	–	0.27 s	0.02 s

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:

Aikavaativuus	Algoritmin nimitys
\(O(1)\)	Vakioaikainen
\(O(\log n)\)	Logaritminen
\(O(n)\)	Lineaarinen
\(O(n \log n)\)	–
\(O(n^2)\)	Neliöllinen
\(O(n^3)\)	Kuutiollinen

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)\).