Lajittelututkimuksesta laitoksen alkuvuosina ja myös muustakin
Emeritusprofessori Eero Peltola
Aluksi
Automaattisen tietojenkäsittelyn historia on vieläkin lyhyt, jos alku lasketaan ensimmäisten tietokoneiden rakentamisesta nykypäivään. Alan merkitys ja sen vaikutukset ovat lyhyestä historiasta huolimatta kuitenkin erittäin merkittävät ja atk:hon törmää jo melkein joka paikassa ja yhtä mittaa.
Automaattinen tietojenkäsittely ilmestyi yliopistoihin ja korkeakouluihin 1950- ja 1960-lukujen vaihteessa, varsinaisesti 1960-luvun alussa, jolloin niihin hankittiin ensimmäisiä tietokoneita. Tällöin niissä käynnistyi myös atk:n opetus, joka oli lähinnä ohjelmoinnin opetusta. Vuosina 1965 ja 1967 perustettiin Suomeen silloin tietojenkäsittelyopiksi kutsutun oppiaineen ensimmäiset professuurit ja laitokset, joihin nämä professorin virat ja muut oppiaineen uudet virat sijoitettiin. Laitosten tehtävänä oli suorittaa alansa korkeinta tutkimusta ja antaa siihen liittyvää opetusta.
Liityin Helsingin yliopiston tietojenkäsittelyopin opettaja- ja tutkijayhteisöön syyslukukauden 1969 alussa. Ydinfysiikkaa käsittelevä väitöskirjani käsikirjoitus oli silloin niin pitkällä, että siirtyminen opettamaan ja tutkimaan uutta oppiainetta, jonka aihepiirien parissa olin jo kuitenkin työskennellyt useita vuosia, oli myös käytännössä mahdollista. Fysiikan ja ydinfysiikan sekä muuten myös tähtitieteen ongelmien tutkimisessa ja ratkaisemisessa olin jo pitkään käyttänyt tietokoneita. Noiden tutkimusten voisi nykypäivän terminologiaa käyttäen katsoa kuuluneen myös laskennallisen tieteen (computational science) piiriin.
Professori Donald E. Knuth julkaisi 1960-luvun loppupuolella ensimmäiset osat suunnittelemastaan 7-osaisesta kirjasarjasta The Art of Computer Programming, jonka sisällön hän oli kaavaillut seuraavanlaiseksi:
- Volume1. Fundamental Algorithms
- Chapter 1. Basic Concepts
- Chapter 2. Information Systems
- Volume 2. Seminumerical Algorithms
- Chapter 3. Random Numbers
- Chapter 4. Aritmethic
- Volume 3. Sorting and Searching
- Chapter 5. Sorting Techniques
- Chapter 6. Searching Techniques
- Volume 4. Combinatorial Algorithms
- Chapter 7. Combinatorial Searching
- Chapter 8. Recursion
- Volume 5. Syntactical Algorithms
- Chapter 9. Lexical Scanning
- Chapter 10. Parsing Techniques
- Volume 6. Theory of Languages
- Chapter 11. Mathematical Linguistics
- Volume 7. Compilers
- Chapter 12. Programming Language Translation
Tästä kirjasarjasta ilmestyi kuitenkin vain kolme ensimmäistä osaa. Kirjasarja kuvaa kokonaisuutena hyvin sitä, mitä Knuth piti silloin tietojenkäsittelyopin keskeisenä sisältönä. Voidaan todeta, että sisältö on vieläkin yllättävän ajankohtainen, vaikka useiden aihepiirien kohdalla on luonnollisesti edetty pitkälle ja matemaattinen tarkastelu ei ole yhtä keskeisessä roolissa. Lisäksi nykyään sovelluspainotteiset sisällöt ovat merkittävämmin esillä kuin 1960-luvulla. Jo silloin tietojenkäsittelyn käytännön sovellusten perusteella puhuttiin teknistieteellisestä ja kaupallishallinnollisesta tietojenkäsittelystä.
Knuth'in teossarjan ensimmäistä osaa käytettiin laitoksella tietorakenteita ja niihin liittyviä algoritmeja käsitelleen kurssin lähdemateriaalina. Tätä kurssia itsekin luennoin. Toinen osa puolestaan liittyi laitoksella alkuvaiheessa tehtyyn numeriikan tutkimukseen, jossa tutkittiin pyöristysvirheiden vaikutuksia laskentaan ja kehitettiin menetelmiä riittävän laskentatarkkuuden ylläpitämiseksi.
Aivan 1970-luvun alussa olin vuoden Marylandin yliopistossa. Siellä tutustuin konenäön, luonnollisten kielten ja tekoälyn tutkimuksiin. Varsinaisena tutkimuskohteenani olivat kuitenkin tiedon jäljitysmenetelmät (information retrieval), joita professori Jack Minker tekoälyn ohella tutki siihen aikaan. Suomessa tämän aihepiiriin tutkimuksen katsottiin kuuluvan kirjastotieteen ja informatiikan piiriin, joten en sitä palattuani Suomeen enää jatkanut, vaan ryhdyin tutkimaan muita aihepiirejä. Kehitin Lauri Fontellin, Harri Laineen ja Olavi Maanaviljan kanssa tietohakemistoon perustuvaa parametroitua tiedostojen käsittelyjärjestelmää. Idea oli hyvä, mutta ohjelmointikielet ja tietokoneet eivät olleet tarpeeksi kehittyneitä, jotta ratkaisu olisi soveltunut käytännön tietojenkäsittelytehtäviin. Tutkimus oli varhaista tietokannan hallintajärjestelmätutkimusta, jossa tietokannan lisäksi kehitimme yleistä tiedostojen käsittelyohjelman runkoa, joka käsittelyn ohjausparametrien ja ohjelmarungon liitoskohtiin kiinnitettävien tapauskohtaisten "proseduurien" avulla voitiin muokata kulloisenkin sovelluksen tarpeiden mukaiseksi.
Lauri Fontell siirtyi Atk-Instituutin rehtoriksi ja me muut eli Harri Laine, Olavi Maanavilja ja minä ryhdyimme tutkimaan tietokantamalleja, koska se oli luonteva jatko aiemmille tutkimuksillemme. Taisimme olla suomalaisen tietokantatutkimuksen, etenkin tietokantamallitutkimuksen uranuurtajia. Näiden "kaupallishallinnollisten" tutkimusten ohella tein myös lajittelututkimusta.
Lajittelututkimuksesta
Tulin jo fysiikkaa ja muita luonnontieteitä opiskellessani siihen tulokseen, että uuteen aihepiiriin kannattaa perehtyä ensin lukemalla ja kuuntelemalla toisten luentoja ja esitelmiä sekä keskustelemalla aihepiiriä tuntevien kanssa. Omaa tietämystään on pakko vielä parantaa, jos alkaa antaa aihepiiristä opetusta. Vielä yksityiskohtaisempaa osaamista vaaditaan, jos ohjelmoi aihepiiriin liittyviä sovelluksia. Viimeisenä askeleena on tehdä aihepiiriin liittyvää tutkimusta, jonka tavoitteena on saada aikaan uusia tieteellisiä tutkimustuloksia. Tulosten arvo tulee mitatuksi, kun ne saa julkaistuksi arvostetuissa kansainvälisissä tieteellisissä aikakauslehdissä. Julkaiseminen laitoksen omassa raporttisarjassa tai konferenssijulkaisussa ei aina vielä välttämättä takaa tulosten tieteellistä merkittävyyttä, mutta on monesti hyödyllinen välivaihe ja erinomainen foorumi esimerkiksi väitöskirjojen julkaisemiseen.
Knuth'in kirjasarjan kolmas osa käsittelee etsintä- ja lajittelumenetelmiä. Etsintä- ja lajittelualgoritmeja tarvitaan melkeinpä sovelluksessa kuin sovelluksessa. Tähän aihepiirin perehtymisessä käytin edellä kuvaamaani mallia. Luin kyseistä kirjaa ja aihepiiristä kirjoitettuja artikkeleita. Pidin etsintä- ja lajittelumenetelmiä käsittelevää luentosarjaa sekä toteutin menetelmiä tietokoneohjelmina. Tällöin kävi ilmiselväksi, että lajittelumenetelmät olivat jo pitkään tutkittu aihepiiri ja menetelmät myös perusteellisesti analysoituja. Ei siis olisi helppoa saada aikaan uusia tuloksia. Tästä tulee vakuuttuneeksi, kun lukee Knuth'in kirjaa. Toisaalta aihepiiri on tällöin myös hyvä haaste nuorelle tutkijalle.
Tarkastellaanpa esimerkkiä, jossa vektorissa A(1:N) on N eri kokonaislukua, jotka on lajiteltava nousevaan järjestykseen. Usein käytetty tapa on lajitella luvut järjestykseen vertailemalla kerrallaan kahta eri alkiota ja vaihtamalla alkioiden arvot keskenään, jos indeksiltään pienemmän alkion arvo on suurempi. Riippuen siitä, miten ja missä järjestyksessä vertailtavat alkioparit valitaan, saadaan erilaisia lajittelumenetelmiä. Näiden lajittelualgoritmien kompleksisuutta voidaan tutkia analysoimalla, miten algoritmit käyttäytyvät, kun lajiteltavat luvut ovat algoritmin kannalta parhaassa, keskimääräisessä ja pahimmassa järjestyksessä. Tämän lisäksi voidaan analysoida lajittelumenetelmän vaatimaa lisämuistitilaa. Tällöin erottuvat toisistaan algoritmit, jotka lajittelevat alkiot paikallaan eli alkuperäisessä vektorissa ja algoritmit, jotka tarvitsevat N:ään verrannollisen määrän lisätilaa. Edelliseen ryhmään kuuluu esimerkiksi upotuslajittelu ja jälkimmäiseen ryhmään lomituslajittelu. Quicksort'issa lisämuistitilan tarve on keskimäärin verrannollinen log N:ään. Vertailuun perustuvien lajittelumenetelmien tehokkuuden mittana pidetään menetelmien vaatimaa vertailuiden määrää, joka parhaimmillaan on verrannollinen N:ään ja huonoimmillaan N:n toiseen potenssiin. Käytännön lajittelutehtävissä ratkaisevaa on kuitenkin lajitteluun kuluva kokonaisaika, johon vaikuttavat myös lajittelussa tarvittava alkioiden vaihtojen lukumäärä ja vertailtavien parien järjestyksen määrittävä "indeksikirjanpito" eli siis kontrollirakenteiden vaatima aika.
Lomituslajittelu tuntui tuolloin mielenkiintoiselta. Se oli tehokas, olivatpa alkiot missä järjestyksessä tahansa. Niinpä aloin pohdiskella, miten lomituslajittelussa voitaisiin varmistaa se, että lajittelu olisi tasapainoista eli että lomitettavat jonot olisivat aina mahdollisimman yhtä pitkiä. Aikani mietittyäni keksinkin ratkaisun. Jos lomitetaan kahta jonoa kerrallaan yhdeksi jonoksi, niin nämä jonot voivat sisältyä yhteen vektoriin siten, että toiseen jonoon kuuluvat alkiot 1, 3, 5, ... ja toiseen alkiot 2, 4, 6, ... Tätä periaatetta yleistämällä voidaan vektoriin sijoittaa neljä jonoa ja niin edelleen. Voidaan helposti todeta, että tällaisella sijoittelulla lomitettavien jonojen pituudet poikkeavat toisistaan korkeintaan yhden alkion verran.
Olin jo aiemmissa tutkimuksissa havainnut, että tutkimusryhmä tehostaa merkittävästi tulosten aikaansaamista ja että "taistelupari" eli kahden tutkijan ryhmä on tehokkain, jos tutkimus ei ole kovin laaja. Niinpä ei muuta kuin paria etsimään. Se ei onneksi ollut kovin vaikeaa. Olin jo seurannut läheltä Erkiön Hannun toimia. Hän oli ansiokkaasti kehittänyt algoritmeja liukuvan tarkkuuden laskentaa varten ja tunsi hyvin laskentakeskuksessa olevan Burroughs B 6700 -tietokoneen ja siinä käytetyn (Extended) Algol -kielen. Hän osallistuikin asiantuntevasti lajittelualgoritmin hiomiseen ja ohjelmointiin, kehitti algoritmit, joilla luotiin pahimpien tapausten aineistot, ja suoritti eri lajittelualgoritmien lajitteluaikojen mittaukset. Tutkimustemme tuloksia julkaistiin laitoksen julkaisusarjassa, sitten konferenssissa ja lopuksi onnistuimme saamaan artikkelin myös Information Processing Letters -julkaisusarjaan. Vielä kuin "kaupanpäällisiksi" tämä lehti julkaisi ilmoituksen Communications of the ACM -lehdessä ja siinä mainostettiin juuri sen numeron sisältöä, jossa artikkelimme oli.
Tasapainoista lomituslajittelua kehitellessämme saimme uusia ideoita, joiden ja omien ideoidensa kehittämistä Hannu jatkoi minun siirryttyäni Jyväskylän yliopistoon. Hannu julkaisikin tutkimuksiaan ensin lisensiaattityönään "On the heapsort and its dependence on input data" ja sitten väitöskirjananaan "Studies on the efficiency of certain internal sorting algorithms" vuonna 1980.
Lopuksi
On ollut mielenkiintoista havaita, että viime vuosina aiemmat aihepiirit ovat kokeneet uuden renessanssin. Tiedonjäljityksen tutkimusaiheita käsitellään nyt sekä tiedon louhinnan että semanttisten seittien (semantic web) yhteydessä. Semanttisia verkkoja tutkittiin tietokantamallien yhteydessä jo 1970-luvun lopulla. Itsekin olen matkoilla ollessani jälleen miettinyt lajitteluongelmia "aikaa tappaakseni" ja keksinyt pari uutta ideaa. Pitäisi kai taas ottaa Hannuun yhteyttä.