Sana algoritmi tarkoittaa laajasti ottaen jonkin tietyn toiminnan yksiselitteistä kuvausta. Esimerkiksi mikä tahansa ohjelma on tietynlainen algoritmi, koska se kuvaa tietynlaista käyttäytymistä (toimintaa) suhteessa käyttäjän toimiin. Yleisemmin ottaen voidaan sanoa, että algoritmi kuvaa jonkin syötteen, esimerkiksi tekstin, lukujen tai käyttäjän toimien, suhdetta tulosteeseen, esimerkiksi tekstiin, tiedostojärjestelmän muutoksiin tai tietokoneen ruudulle tuleviin asioihin. Algoritmi sisältää myös yksiselitteisen ohjeen siitä, miten tuloste muodostetaan syötteen perusteella.
Tämän perusteella pitäisi olla ilmeistä, että ohjelmointikielet ovat tekniikoita algoritmien määrittämiseksi ja että algoritmeja ovat myös kaikki sellaiset ohjelman osat, jotka pystyy suorittamaan erikseen, esimerkiksi ohjelman funktiot. Voisikin sanoa, että jokainen algoritmi koostuu monista pienistä osa-algoritmeista. Joskus nämä osa-algoritmit ovat käyttäjän kirjoittamia ja niitä kutsutaan aliohjelmiksi (eli ne ovat siis funktioita, joita käytetään apuna toisten funktioiden määrittelyssä). Joskus taas nämä osa-algoritmit ovat niin yksinkertaisia, että ohjelmointikieli itse tarjoaa ne ohjelmoijalle. Tällaisia toimintoja/algoritmeja kutsutaan primitiiveiksi ja esimerkiksi Schemessä niitä ovat mm. car, + ja null?.
Algoritmin ulkoisiin hyveisiin kuuluu, että siitä on hyötyä mahdollisimman monelle mahdollisimman paljon. Nämä kaksi päämäärää ovat keskenään vastakkaisia.[1] Niiden välillä onkin pyrittävä tasapainoon. Aloittelevat ohjelmoijat tekevät yleensä liian erikoistuneita algoritmeja ja keskinkertaiset ohjelmoijat liian yleispäteviä. Ihmisillä on itse asiassa luonnostaan näiden kahden tasapainottamisesta melko hyvä intuitio, jonka sovittaminen ohjelmointiin vain tuottaa vaikeuksia.
[1] Esimerkki algoritmista, josta on erittäin
paljon hyötyä mutta erittäin pienelle joukolle, on algoritmi, joka osaa
tunnistaa täydellisesti puhetta, kunhan kyseessä on puhe, joka on
täsmälleen samanlaista kuin algoritmin kehittäjän puhe oli marraskuussa
2004. Esimerkki algoritmista, joka on erittäin laajakäyttöinen mutta
vähähyötyinen sellaisenaan (vailla erikoistamista) on jonkin
ohjelmointiformalismin, esim. lambdakalkyylin tai Schemen, toteutus.
Algoritmin sisäisiin hyveisiin kuuluu, että se koostuu mahdollisimman monesta mahdollisimman selkeästä ja erikseen käytettävissä olevasta osasta. Nämä pyrkimykset eivät ole keskenään ristiriidassa, eivätkä myöskään sen pyrkimyksen kanssa, että ohjelma olisi lyhyt ja ytimekäs (jolloin sen kirjoittamisessa on mahdollisimman vähän vaivaa). Mutta algoritmin jakaminen mielekkäisiin osiin vaatii hahmotuskykyä ja jonkin verran suunnittelua tai ainakin intuitiota. Lisäksi algoritmin sisäisiin hyveisiin kuuluu myös se, että siinä ei ole sisäistä toistoa eli ettei se sisällä keskenään hyvin samantapaisia osia monta kertaa.[2] Toiston poistaminen edellyttää yhtenäisten osien eriyttämistä uudeksi, yleispätevämmäksi algoritmiksi, mikä vaatii hahmotuskykyä ja insinööritaitoa. Näin ollen algoritmin sisäisten hyveiden noudattaminen siirtää työtä koodin kirjoittamisen puolelta ajattelun puolelle ja tekee kaikkiaan ohjelmoinnista mielekkäämpää ja kiinnostavampaa toimintaa.
[2]
Nämä samantapaiset osat tuntuvat kummasti olevan sellaisia, että kun
yhteen niistä tulee muutoksia, jokaista muutakin joutuu muuttamaan.
Algoritmin ulkoista toimintaa ei määritä täydellisesti se, mitä se tekee. Paremman kuvan siitä, mitä algoritmi oikeasti tekee eli mikä algoritmi on varsinaisesti kyseessä, saa siitä, mitä syötettä se ottaa ja minkä tulosteen se siitä antaa. Kun on kyseessä funktio, tämä merkitsee sen argumenttien ja palautusarvon määrittelyä.
Esimerkiksi sen sijaan, että puhutaan funktiosta, joka tavuttaa
, on
tarkempaa puhua funktiosta, joka ottaa merkkijonon ja palauttaa
merkkijonon, jossa argumenttimerkkijonon tavurajat on merkitty viivoin.
Samoin sen sijaan, että puhuttaisiin funktiosta, joka etsii seuraavan
tavurajan
, on tarkempaa puhua funktiosta, joka ottaa merkkijonon ja
palauttaa numerona, kuinka monen merkin päässä sen alusta on ensimmäinen
tavuraja.
Tämä on tärkeää, koska olen huomannut, että monet ohjelmoijat eivät etukäteen ajattele, mitä heidän funktionsa palauttaa. On mahdotonta kirjoittaa perustapauksia ja rekursioita, ellei tiedä, mitä funktion on tarkoitus palauttaa.
Ohjelmat tulevat helpommiksi lukea ja algoritmit helpommiksi käyttää uudelleen, kun niiden nimi selkeästi kertoo, mitä algoritmi tuottaa mistä eli mikä on sen tulosteen suhde sen syötteisiin. Lisäksi, jos algoritmille (funktiolle) on vaikea keksiä nimeä, se ei välttämättä vastaa mitään mielekästä toimintaa tai käsitettä ja niinpä sen itsenäisyys (sitä käyttävistä funktioista) on kyseenalaista.
Esimerkiksi funktio, joka ottaa kaksi listaa ja palauttaa listan, joka sisältää molempien listojen alun siltä osalta kuin se on kummillekin listoille sama, voisi olla nimeltään common-prefix:
(define (common-prefix l1 l2)
(if (not (equal? (car l1) (car l2))) '()
(cons (car l1) (common-prefix (cdr l1) (cdr l2)))))
Jos taas tämä funktio palauttaisikin numerona samankaltaisen alun
pituuden, sen nimi voisi olla common-prefix-length. Toisena
esimerkkinä aiempi esimerkkifunktio, joka etsii tavurajan, voisi olla nimeltään next-syllable-boundary-index.
Jos tulosteen nimeäminen edellyttää verbijohdosta (erityisesti partisiippia), on yleensä selkeämpää käyttää vain suoraa predikaattilausetta nimenä. Esimerkiksi aiemmin kuvatun tavutusfunktion johdonmukainen nimi on with-syllable-boundaries-marked, mutta sen voisi nimetä yksinkertaisesti mark-syllable-boundaries tai mark-syllables. Ylipäänsä prepositiorakenteita on usein syytä karsia, ellei niiden läsnäolo ole selkeyden kannalta välttämätöntä: esimerkiksi common-prefix-funktion nimi voisi periaatteessa olla common-prefix-of tai common-prefix-of-lists, mutta tämä olisi lähinnä ärsyttävää. Funktio, joka ottaa n listaa ja palauttaa listan, jossa niiden kaikkien elementit ovat peräkkäin, on nimeltään append.
Totuusarvon palauttavat funktiot nimetään sen kysymyksen mukaan, johon
ne vastaavat, ja niiden nimeen lisätään kysymysmerkki (Schemessä).
Tällöin jätetään mahdollinen kopula (is
tai onko
) pois. Esimerkiksi
funktio, joka ottaa numeron ja palauttaa toden tai epätoden sen mukaan,
onko se alkuluku, tulisi nimetä prime?. Funktio, joka ottaa kaksi
listaa ja testaa, alkaako toinen niistä toisella, voisi olla nimeltään
begins-with? tai prefix?:
(define (prefix? l1 l2)
(cond ((null? l1) #t)
((not (equal? (car l1) (car l2))) #f)
(else (prefix? (cdr l1) (cdr l2)))))
Joskus tiettyä tietotyyppiä käsittelevät funktiot nimetään siten, että ne alkavat tietotyypin nimellä, koska sama nimi saattaisi olla yhtä järkevä monen eri tietotyypin operaationa. (Ehkä vielä parempi tosin on kirjoittaa algoritmi, joka pystyy käsittelemään kaikkia näitä tietotyyppejä, mutta tämä ei ole usein mahdollista.) Esimerkiksi: syntax-replace-words, list-ref, vector-length. Mainittakoon, että listat nauttivat schemessä jonkinlaista etuasemaa, ja monet niihin liittyvät funktiot on nimetty ilman etuliitettä.
Nimeäminen on hirveän tärkeää, koska järkevä nimi on osoitus siitä, että algoritmi tekee konseptuaalisesti eheän asian, on ymmärrettävä ja uudelleenkäytettävä.
Tämä on poikkeus edelliseen neuvoon. Funktiot, joilla on sivuvaikutuksia (eli esim. argumenttitaulukon jonkin / joidenkin kohtien arvojen muuttaminen) nimetään sivuvaikutuksensa perusteella ja niiden nimeen lisätään huutomerkki (Schemessä). Yleensä näiden funktioiden palautusarvo on yhdentekevä tai määrittelemätön, ja niiden nimeäminen palautusarvon perusteella olisi älytöntä.
Esimerkiksi, funktio joka korvaa argumenttisyntaksipuustaan sanat toisilla suoraan, sen sijaan, että palauttaisi uuden puun, voisi olla nimeltään syntax-replace-words!.
Sivuvaikutuksellisista funktioista vielä sen verran, että niiden kanssa
pitää olla tarkkana. Jos ne sivuvaikutuksensa lisäksi palauttavat
jonkin hyödyllisen arvon, niillä saa helposti aikaan hyvin sekavaa
koodia. Lisäksi niitä on hankalampaa uudelleenkäyttää kuin puhtaita
funktioita. Hyviä palautusarvoja sivuvaikutuksellisille funktioille
ovat #t tai muutettu argumentti.
Kun lähestyt monimutkaisen algoritmin kirjoittamista, hahmottele päässäsi tai jollain muistiinpanovälineellä tarvitsemasi tietorakenteet ja algoritmi syötteen ja tulosteen perusteella; hahmottele, millaisia osatoimintoja algoritmiin sisältyy ja mitä se tarvitsee avukseen. Määritä jokainen näistä osatoiminnoista ja avuista omana algoritminaan ja määrittele se syötteen ja tulosteen perusteella. Jatka, kunnes olet niin yksinkertaisissa asioissa, ettet enää keksi, miten yksinkertaistaisit niitä.
Aloita algoritmin kirjoittaminen näistä kaikkein yksinkertaisimmista
osista. Tee niistä kauniita ja hyvin toimivia. Jos olet tekemässä
oikeaa tuotantoon tulevaa ohjelmaa tai mitä tahansa tarpeeksi
monimutkaista
kokonaisuutta, kirjoita niille myös automatisoidut
testit.[3] Kokeile myös
kutsua niitä itse.
[3] Automatisoidut testit ovat korvaamattomia, kun ohjelma
muuttuu. Testit ovat niin tärkeitä, että joidenkuiden mielestä ne
pitäisi kirjoittaa ennen varsinaista osaa, jota ne testaavat. Onko
tämä mielekästä, riippuu ohjelman kehittämistavasta.
Kun olet saanut aikaiseksi edellytykset (aliohjelmat) johonkin korkeamman tason algoritmiin, kirjoita se ja testaa. Jos olet tehnyt algoritmien syöte- ja tulosteanalyysin oikein, algoritmisi kirjoittaminen etenee vääjäämättä etkä joudu palaamaan takaisinpäin. Jos olet tehnyt nimeämisanalyysin oikein, jokainen kirjoittamasi osa-algoritmi on järkevä kokonaisuus sellaisenaan ja saavutus, vaikkei sitä loppujen lopuksi käytettäisikään. (Tällaisia algoritmeja yleensä tulee muutamia, mutta niitä ei ole tarpeen poistaa varsinkaan, jos niillä on toimivat testit ja selkeä nimi.)
Algoritmit ovat abstraktioita, yleistyksiä. Ne tuottavat johdonmukaisen
tuloksen tietylle syötteiden joukolle; ei ole mitään järkeä tehdä
algoritmia, joka toimii vain yhdelle syötteelle, kuten pelkästään
merkkijonolle kiizakoo
. Muistatko algoritmin hyveet? Usein nämä
hyveet on mahdollista ottaa kunnolla huomioon vasta, kun osa ohjelmasta
on kirjoitettu.
Esimerkiksi usein käy niin, että erilaisten toimintojen samankaltaisuuden huomaa vasta jälkeen päin. Jos kaksi algoritmin osa-algoritmia muistuttavat toisiaan toiminnaltaan, on todennäköisesti olemassa jokin yleispätevämpi mutta yhtä hyödyllinen algoritmi, joka kokoaa näiden kahden toiminnan. Erosta kahden algoritmin välillä tulee tämän yleispätevän algoritmin yksi (tai useampi) argumentti; esimerkiksi funktio, joka kuvaa tietyssä kohdassa tehtyä laskentaa, totuusarvo, joka kertoo, tehdäänkö tietty asia vai ei, tai muuta sellaista.
Esimerkiksi kaksi funktiota, joista toinen kertoo, kuinka monta konsonanttia merkkilistan alussa on ja toinen, kuinka monta vokaalia, voidaan molemmat määritellä yhden funktion perusteella:
(define (consonant-prefix-length seq)
(cond ((null? seq) 0)
((not (consonant? (car seq))) 0)
(else (+ 1 (consonant-prefix-length (cdr seq))))))
(define (vowel-prefix-length seq)
(cond ((null? seq) 0)
((not (vowel? (car seq))) 0)
(else (+ 1 (vowel-prefix-length (cdr seq))))))
Tämä muuttuu muotoon:
(define (fulfilling-prefix-length pred seq)
(cond ((null? seq) 0)
((not (pred (car seq))) 0)
(else (+ 1 (fulfilling-prefix-length (cdr seq))))))
(define (consonant-prefix-length seq)
(fulfilling-prefix-length consonant? seq))
(define (vowel-prefix-length seq)
(fulfilling-prefix-length vowel? seq))
Itse asiassa useimmat hirmu yleispätevät
apufunktiot, kuten map,
filter jne., ovat juuri tällä tavalla kehittyneitä.
Yksi esimerkki vielä (tätä ei tarvitse ymmärtää, mutta ymmärtäminen
saattaa kohottaa tietoisuuden tasoa). Usein testattaessa jotain asiaa
halutaan testata yhdestä arvosta monta asiaa: esimerkiksi, onko tietty
merkki (yksi arvo) kirjain tai numero. and-, or- ja
not-konnektiiveista on mahdollista määrittää versiot, jotka
dispatchaavat
jonkin arvon argumenttifunktio(i)lleen:[4]
(define (both test1 test2) (lambda (val) (and (test1 val) (test2 val)))) (define (either test1 test2) (lambda (val) (or (test1 val) (test2 val)))) (define (non test) (lambda (val) (not (test val)))) ; voi käyttää esim. näin: (if ((non null?) ls) ...) ; voi määrittää esim. seuraavat: (define alphanumeric? (either char-alphabetic? char-numeric?)) (define consonant? (both char-alphabetic? (non vowel?))) ; toinen mahdollinen käyttö: (define (less-than? upperbound) (lambda (x) (< x upperbound))) (define (greater-than? lowerbound) (lambda (x) (< lowerbound x))) (if ((both even? (greater-than? 100)) val) ...) (if ((both (greater-than? 0) (less-than? 10)) val) ...) ; tämä on itse asiassa niin yleistä, että kannattaa ehkä: (define (between? x min max) (and (<= min x) (< x max)))
[4] Vielä
jumalaisempi aihe: jotkut lukijat saattavat huomata, että ainakin
both ja either, mahdollisesti myös non, ovat ilmentymiä
tietystä yleispätevämmästä algoritmista, jonka nimi voisi olla esim.
dispatch-and-combine-results. Tätä yleistystä ei ole tehty koska
(1) funktiot ovat aivan riittävän yksinkertaisia jo sellaisinaan ja (2)
koska and ja or omaavat erityiskykyjä, jotka ne menettävät, jos
niitä kohdellaan tavanomaisina funktioina. En aio selittää tätä.
Tämä on luonnollinen seuraus edellisestä. Hyvä algoritmi on abstrakti mutta hyödyllinen, ja yksityiskohtien määrittäminen alimmalla tasolla voi olla haitallista (tai sitten ei). Algoritmin yksityiskohdat pitäisi fiksata vasta mahdollisimman korkealla tasolla algoritmissa, tai jopa siirtää ne kokonaan ohjelman ulkopuolelle, käyttäjän määritettäviksi (komentolinja-argumentein, konfiguraatiotiedostoin tai jollain muulla tavalla, esimerkiksi vastaamalla kysymyksiin).
Esimerkkinä hienosti yleistetystä tavutusalgoritmista voisi olla sellainen, jolle annetaan lista tavutussääntöjä jossain tietyssä muodossa (funktioina?) ja joka lisää tavuviivat näiden kaikkien sääntöjen perusteella. Toinen esimerkki ovat tavutuspoikkeukset: niitä ei kannattane kirjoittaa suoraan ohjelmakoodiin, vaan päättää esim. jokin esitysmuoto poikkeuksille, ja sitten käydä poikkeusten lista läpi katsoakseen, päteekö niistä jokin.