Jorin jutut / ohjelmointi

Tietokoneohjelmien nopeus ja kompleksisuuden käsite

Tämä kirjoitus käsittelee tietokoneohjelmien nopeutta keskittyen erityisesti käsitteeseen nimeltä kompleksisuus. Lukijalta odotetaan hiukan kokemusta ohjelmoinnista millä tahansa ohjelmointikielellä.

Hyvä tietokoneohjelma - yleistä asiaa

Hyvällä tietokoneohjelmalla on neljä vaatimusta:

  1. Ohjelma toimii oikein, eli tekee mitä pitää ja käsittelee myös virhetilanteet, kuten mahdottoman syötteen tai muistin loppumisen.
  2. Ohjelma on tehokas, eli ei käytä suoritinaikaa, keskusmuistia tai muita resursseja enempää kuin on tarpeen.
  3. Ohjelma on helppokäyttöinen.
  4. Lähdekoodi on selkeää, ohjelmaa on helppo muokata ja laajentaa.

Näistä kohdista tehokkuus on vähiten tärkeä. Nopeasti saatavat virheelliset tulokset ovat huonompi asia kuin ei tuloksia lainkaan, eikä nopeista ja oikeista vastauksistakaan ole hyötyä, ellei käyttäjä osaa käyttää ohjelmaa. Jos ohjelman rakenne on kunnossa, on nopeuttakin yleensä helppo parantaa, koska silloin nopeuden kannalta kriittiset osat on helppo korvata paremmilla muuttamatta koko ohjelmaa. Toisaalta nopeus vaikuttaa käytettävyyteen: ohjelman tulisi toimia jouhevasti, koska tauot keskeyttävät käyttäjän keskittymisen tehtävään.

Tehokkuus voi käsittää monenlaisia asioita. Yleensä mitataan juuri suoritusaikaa ja muistin kulutusta. Tietokantojen yhteydessä tärkein tehokkuusasia on levyhakujen määrä. Resurssi, jonka käyttö pyritään minimoimaan, voi olla myös vaikkapa lähiverkossa siirrettävän datan määrä. Tässä kirjoituksessa keskitytään vain suoritusaikaan, mutta periaatteessa sama perusidea pätee myös muihin resursseihin.

Suoritusaikaan vaikuttavia tekijöitä

Tietenkin nopeampi suoritin tekee asioita nopeammin, 100 MHz on parempi kuin 75 MHz. Myös suorittimen tyyppi vaikuttaa, yleensä Pentium on nopeampi kuin 80486. Hyvin paljon on merkitystä sillä, onko kyseessä tulkattava vai käännettävä kieli, Java voi olla monin kerroin hitaampaa kuin Pascal. Kääntäjäkin asiaan vaikuttaa, jokin osaa tehdä nopeampaa koodia kuin muut saman kielen kääntäjät.

Kaikki mainitut asiat vaikuttavat korkeintaan jonkin vakiokertoimen verran. Ohjelman nopeus tietokoneessa, jossa on 100 MHz:n suoritin on enintään kolmanneksen suurempi kuin 75 MHz:n suorittimella varustetussa mallissa. Nopeusero jää pienemmäksi, jos nopeuteen vaikuttaa suorittimen lisäksi myös muu tekijä, kuten kiintolevyaseman nopeus. (Periaatteessa kääntäjä voisi nopeuttaa enemmän kuin vakiokertoimella, mutta tällaisia ei tiettävästi ole. Myös kieli voi eräissä erikoistapauksissa vaikuttaa enemmän, esimerkiksi Prologia ja Pascalia verrattaessa.)

Algoritmi

Tekstissä esiintyy sana algoritmi. Sillä tarkoitetaan jonkin tarkasti määritellyn tehtävän suorittavan ohjelman tai ohjelman osan toimintaperiaatetta. Hyvin usein algoritmit käsittelevät suurta joukkoa keskenään samankaltaisia tietoalkioita. Kyseessä voi olla vaikkapa taulukon järjestävä algoritmi ja tietoalkiot kokonaislukuja.

Kompleksisuus

Algoritmien nopeutta ei verrata sekunteina, vaan kompleksisuutena. Kompleksisuus tarkoittaa miten nopeasti suoritusaika kasvaa, kun tietoalkioiden määrää lisätään.

Otetaan esimerkiksi taulukko kahden kuvitellun algoritmin suoritusajasta erilaisilla tietoalkioiden lukumäärillä.

Alkioita Suoritusaika
Algoritmi AAlgoritmi B
100110
1000100150
10000100002000
100000100000025000

Algoritmin A suoritusaika satakertaistuu, kun alkioiden lukumäärä kymmenkertaistuu. Sanotaan, että kompleksisuus on (n²), eli suoritusaika on likimain suoraan verrannollinen alkioiden määrän neliöön. Algoritmin B kompleksisuus on (n×log n), eli taulukon mukaisesti suoritusaika kasvaa enemmän kuin suoraan verrannollisesti alkioiden lukumäärään nähden, mutta kuitenkin paljon hitaammin kuin algoritmilla A.

Esimerkissä A oli nopeampi pienellä alkiomäärällä (1000), mutta hitaampi alkioiden lukumäärän kasvaessa kymmeneen tuhanteen. Vaikka kyse oli keksityistä luvuista, on tilanne aivan mahdollinen. Usein kompleksisuudeltaan pienempi algoritmi on monimutkaisempi, ja siksi hitaampi pienellä aineistolla.

Esimerkissä raja, jossa B oli nopeampi kuin A, oli jossain tuhannen ja kymmenen tuhannen alkion välillä. Vaikka esimerkki oli keksitty, on periaate todellinen: alkioiden määrän kasvaessa kompleksisuudeltaan pienempi algoritmi voittaa varmasti joskus.

Saman asian voi esittää myös graafisessa muodossa:
[Kuvio tilanteesta.]

Theta, Omega ja O

Monien algoritmien kompleksisuus voidaan määrittää tarkasti. Tällöin käytetään Theta-merkintää, eli esimerkiksi Theta(n²) tarkoittaa, että algoritmin suoritusaika lähestyy täsmälleen alkioiden määrän neliöön nähden verrannollista funktiota alkioiden määrän kasvaessa. Ellei tarkkaa rajaa tiedetä, mutta jokin yläraja saadaan selville, käytetään O-merkintää. O(n²) tarkoittaa, että algoritmin suoritusaika on korkeintaan alkioiden määrän neliöön nähden verrannollinen. O(n²) -kompleksinen algoritmi on aina myös O(n^3)-, O(n^4) ja O(n^58) -kompleksinen, kyse on siis ylärajasta. Vastaavasti on määritelty Omega-merkintä, joka kuvaa alarajaa. Omega(n²) -kompleksinen algoritmi on ainakin alkioiden määrän neliöön nähden verrannollinen suoritusajaltaan.

Oikeasti Theta merkitään [Kreikankielen Theta-kirjain] ja Omega merkitään [Kreikankielen Omega], mutta WWW-sivulla ei voi käyttää kreikan aakkosia siten, että sivu toimisi kaikilla selaimilla.

Keskimääräinen vai pahin suoritusaika

Kompleksisuus voidaan määritellä pahimman suoritusajan mukaan, keskimääräisen tapauksen mukaan tai parhaan tapauksen mukaan. Paras tapaus ei yleensä ole kiinnostava. Pahin ja keskimääräinen tapaus ovat usein samoja. Esimerkiksi alkion haku n-alkioisesta järjestämättömästä taulukosta vaatii pahimmillaan n vertailua ja keskimäärin n/2 vertailua, olettaen että haettava alkio löytyy. Molemmissa tapauksissa siis suoritusaika on suoraan verrannollinen alkioiden määrään.

Useimmiten käytetty mittayksikkö on pahimman tapauksen kompleksisuus. Pahin tapaus voi olla hyvinkin yleinen, esimerkiksi edellisen kappaleen alkion haku tilanteessa, jossa alkiota ei löydy. Keskimääräinen tapaus edellyttäisi oikeastaan jo käsitteenä, että erilaisten tapausten esiintymistiheys tunnettaisiin. Tasajakauma, jokainen syöte yhtä todennäköinen, on helppo mutta varsin usein virheellinen oletus, esimerkiksi järjestämisalgoritmeja käytetään usein tilanteessa, jossa järjestettävä taulukko on jo "melkein järjestyksessä".

Minkä suhteen lasketaan?

Edellä on käytetty hieman epämääräistä käsitettä "alkioiden lukumäärä". Usein tarkempaa määrittelyä ei tarvitakaan, vaan kyse on selvästi jonkin taulukon koosta tai vastaavasta. Monimutkaisempi tilanne syntyy mietittäessä algoritmia, joka laskee lyhimmän tiettyjen kaupunkien kautta kulkevan reitin. Kompleksisuus voidaan tällöin ilmoittaa joko kaupunkien määrän, niiden välisten teiden määrän tai kenties näiden summan funktiona. Tarvittaessa on siis kerrottava, minkä suhteen kompleksisuudesta ollaan puhumassa.

Joissakin tilanteissa alkioiden määrä voi tarkoittaa esimerkiksi luvun pituutta, eli esimerkiksi yhteenlasku on Theta(n) -kompleksinen numeroiden lukumäärän suhteen.

Esimerkki kompleksisuuden laskemisesta

Otetaan esimerkiksi yksinkertainen järjestämisalgoritmi, tässä esitetty C++ -kielellä:

void Jarjesta(int * luvut, int n)
{
    for (int i=0; i<n; i++)
        for (int j=i+1; j<n; j++)
            if (luvut[i] > luvut[j])
            {
                int tilap=luvut[i];
                luvut[i]=luvut[j];
                luvut[j]=tilap;
            }
}

Algoritmissa on kaksi sisäkkäistä silmukkaa. Ulommassa silmukassa i käy läpi N kierrosta, ja sisemmässä j käy läpi keskimäärin (suunnilleen) N/2 kierrosta. Yhteensä siis if-lause suoritetaan N×(N/2)=N²/2 kertaa. Siis suoritusaika on suoraan verrannollinen järjestettävän taulukon koon neliöön, eli kompleksisuus on Theta(n²).

Kompleksisuuden laskusääntöjä

Kompleksisuuden määritelmästä seuraa mielenkiintoisia laskusääntöjä. Ensinnäkin ei ole mielekästä kirjoittaa Theta(2×n²), saman asian sanoo Theta(n²). Tarkoitushan ei ole kuvata algoritmien nopeutta sinänsä, vaan sitä, miten nopeasti suoritusaika kasvaa. Siispä kaksi algoritmia voivat olla kompleksisuudeltaan aivan samoja, vaikka toinen algoritmeista on kaksi kertaa niin nopea kuin toinen.

Peräkkäin suoritetuista tehtävistä isompi voittaa. Jos järjestetään taulukko Theta(n²) -algoritmilla ja sitten Theta(n) -algoritmilla tehdään jokin muunnos taulukolle, on kompleksisuus Theta(n²+n), joka on sama kuin Theta(n²). Tämä on loogista, sillä jälkimmäisen osan vaatima aika muuttuu merkityksettömäksi, kun alkioiden lukumäärää kasvatetaan.

Sisäkkäisissä tehtävissä kompleksisuus saadaan usein kertolaskulla. Kaksi n kertaa suoritettavaa sisäkkäistä silmukkaa muodostavat siis yhdessä n² -kompleksisen silmukan.

Milloin kompleksisuus ei kuvaa todellista suoritusaikaa

Tyypillinen algoritmi tekee joitain esivalmisteluja, suorittaa silmukassa joitain operaatioita ja lopuksi vielä esimerkiksi vapauttaa väliaikaisesti varaamansa muistitilan. Alku- ja loppuvalmistelut vievät nekin aikaa. Lisäksi algoritmi on yleensä oma funktionsa, ja funktiokutsukin vie jonkin aikaa. Mitä vähemmän alkioita silmukassa käsitellään, sitä suurempi on alku- ja lopputoimien suhteellinen osuus suoritusajasta. Siis kompleksisuudella ei ole käytännön merkitystä pienillä aineistoilla. Se, paljonko on "pieni", on aina selvitettävä tilannekohtaisesti.

Nykyaikaisissa tietokoneissa on monitasoinen muistihierarkia. Viimeksi käsitellyt tiedot ovat nopeasti saatavilla välimuistissa. Tästä seuraa joitakin rajoja, joiden ylittyessä suoritusaika kasvaa. Esimerkiksi Pentium-tason kotimikrossa kahdeksan kilotavun kokoinen data mahtuu 1. tason välimuistiin, joten sen käsittely on todella nopeaa. 2. tason välimuistiin mahtuu usein 256 kilotavua, joten tässä vaiheessa tietoalkioiden lisääntyessä tulee seuraava raja. Viimeisenä rajana on esimerkiksi 10 megatavua, jonka jälkeen keskusmuisti loppuu ja dataa joudutaan käsittelemään kiintolevyltä. Rajakohdat ovat eri koneissa erilaiset, mutta olemassa ne ovat kaikissa nykyaikaisissa koneissa.

Pääasiaa edellä esitetty ei muuta: jossain vaiheessa kompleksisuudeltaan pienempi algoritmi voittaa varmasti.

Tyypillisiä kompleksisuuden arvoja

Theta(1) tarkoittaa vakiokompleksisuutta. Alkion haku taulukosta saadaan lisäämällä taulukon alun osoitteeseen haettavan alkion paikka kerrottuna yhden alkion viemällä tilalla ja hakemalla alkio näin lasketusta muistipaikasta. Taulukon koko ei siis vaikuta aikaan, eli kompleksisuus on Theta(1).

Logaritmiseksi sanotaan Theta(log n) -kompleksisuutta. Tällainen on esimerkiksi alkion haku järjestetystä taulukosta puolitushaulla. Katsotaan keskimmäinen alkio ja lopetetaan jos se on haettava. Jos se on suurempi kuin haettu, on alkio ennen keskimmäistä alkiota ja muutoin keskimmäisen alkion jälkeen. Kun alkioiden määrä kaksinkertaistuu, joudutaan tekemään yksi puolitus lisää.

Theta(n) on lineaarinen kompleksisuus. Tällaisia ovat kaikki normaalit taulukon läpi käyvät algoritmit, esimerkiksi taulukon alkioiden summan laskenta. Linkitetty lista on solujen muodostama rakenne, jossa solu sisältää alkion ja osoittimen seuraavaan soluun. Alkion haku on tällöin Theta(n)-kompleksinen, eli listan koon kasvaessa muuttuu haku hitaammaksi.

Theta(n×log n) on yleinen nopeampien järjestysalgoritmien keskimääräinen kompleksisuus. Tämä syntyy tilanteessa, jossa taulukko puolitetaan, kumpikin puolikas käsitellään rekursiivisesti ja alimmalla tasolla joudutaan tekemään jokin vertailu alkiota kohti.

Theta(n²) on hitaampien järjestämisalgoritmien kompleksisuus. Näissä algoritmeissä taulukko joudutaan käymään läpi kahdessa sisäkkäisessä silmukassa.

Tietokoneet nopeutuvat

Tietokoneet kehittyvät hurjaa vauhtia, nopeus kaksinkertaistuu parin vuoden välein. Tarkoittaako tämä, ettei kompleksisuudesta tarvitse enää välittää? Kaksinkertainen nopeushan tarkoittaa, että voimme ratkaista kaksi kertaa isompia tehtäviä... eikun ei tarkoita. Jos kompleksisuus on suuri, häviää ohjelma konetehon ja tehtävien koon kasvaessa yhä enemmän. Siispä tulevaisuutta ajatellen pitää nimenomaan miettiä nykyistä enemmän millainen jonkin algoritmin kompleksisuus on.

Saman asian voi kertoa myös selvällä esimerkillä:
Olkoon meillä algoritmi A, jonka kompleksisuus on Theta(n²), algoritmi B, jonka kompleksisuus on Theta(n) ja algoritmi C, jonka kompleksisuus on Theta(10^n). Jos tietokoneen laskentakapasiteetti satakertaistuu, niin voimme käsitellä samassa ajassa algoritmilla A kymmenen kertaa niin isoja aineistoja kuin ennen, algoritmilla B sata kertaa niin isoja aineistoja kuin ennen ja algoritmilla C aineistoja, joihin on lisätty kaksi alkiota.

Tiivistelmä

Linkkejä

Tietokonepalsta: Kuinka Fibonaccin lukuja lasketaan, artikkeli Solmussa. Hyvä juttu, tätä kirjoitusta matemaattisempi käsittelytapa. Luin jutun vasta kirjoitettuani tämän tekstin, tuskin olisin itse kompleksisuudesta kirjoittanutkaan, jos olisin tiennyt tämän olemassaolosta.

C++ -kielen standardikirjaston kompleksisuusmääritelmät. Esimerkki siitä, missä kompleksisuusmerkintöjä käytetään.


Muokattu viimeksi 2000-06-22
Uusin versio on saatavilla osoitteessa http://www.uta.fi/%7ejm58660/jutut/ohjelmointi/kompleksisuus.html

Kiitokset Antti Valmarille, joka luki tekstin ja esitti hyödyllisiä korjauksia niin paljon, että häntä voi pitää tekstin toisena kirjoittajana.