[vastaus aiempaan viestiin]
| Kirjoittaja: | Kimmo Vehkalahti |
|---|---|
| Sähköposti: | - |
| Päiväys: | 24.6.2004 17:58 |
Palaan syötille asettamani kesäpähkinän pariin, ja muistutan samalla
jalkapallon EM-kisojen edettyä pudotuspelivaiheeseen, että täälläkin
areenoilla on tuota mediat täyttävää aihetta sivuttu (ks. arkistosta
viesti www.survo.fi/arkisto/000315.html - "Survotaan jalkapalloa"). :-)
Survo-keskustelun neljäs vuosi olikin alkanut vilkkaasti, ja Kalevi
Kanteleen aloitteesta tuottanut lisää oivallista materiaalia kolmisen
viikkoa sitten julistamaani kesäpähkinää ajatellen.
Liekö syynä lupaamani "palkinnon" vaatimattomuus vai tehtävän vaativuus;
määräpäivään mennessä en ole saanut yhtään varsinaista ratkaisuehdotusta
(olen kyllä kautta rantain kuullut että yritetty on). Näin ollen kooste
vastauksista ei ole tämän pidempi.
Taidan tahallani pitkittää jännitystä paljastamalla vain osan totuutta.
Kyseessähän on tehtävä, joka tuo mieleen jonkinlaisen puu-algoritmin
(ainakin tietorakenteiden teoriaan perehtyneille). Käytän esimerkkinä
aivan uusimpia viestinumeroita, koska niiden avulla tehtävä hahmottuu
varsin tiiviissä tilassa (kiitos "sanapähkinään" osallistujien!).
Tarkastellaan siis seuraavia viestejä, joista ensimmäinen on Kalevin
sanapähkinän aloitusviesti:
000671 / 000671-000000.msg
000672 / 000672-000671.msg
000673 / 000673-000671.msg
000674 / 000674-000672.msg
000675 / 000675-000673.msg
000676 / 000676-000675.msg
000677 / 000677-000000.msg
000678 / 000678-000671.msg
000679 / 000679-000678.msg
000680 / 000680-000679.msg
000681 / 000681-000000.msg
000682 / 000682-000681.msg
000683 / 000683-000671.msg
000684 / 000684-000671.msg
Aiemmassa viestissäni selostamani systeemin mukaisesti nämä voidaan
järjestää muotoon, jossa aloitusviestit ovat ikään kuin puun runko
ja kommentit siihen kiinnittyviä oksia. Kun säilytetään viestien
alkuperäinen (numero)järjestys, saadaan ensin:
000671-000000
000672-000671
000673-000671
000674-000672
000675-000673
000676-000675
000677-000000
000678-000671
000679-000678
000680-000679
000681-000000
000682-000681
000683-000671
000684-000671
Järjestämällä oksat oikeiden "runkoviestien" kohdalle saadaan edelleen:
000671-000000
000672-000671
000674-000672
000673-000671
000675-000673
000676-000675
000678-000671
000679-000678
000680-000679
000683-000671
000684-000671
000677-000000
000681-000000
000682-000681
(Tästä näkeekin jo helposti, että sanapähkinään on kymmenen vastausta.)
Puumalli houkuttelee laatimaan rekursioon perustuvan algoritmin, joka
lähtee runkotasolta ja käy aina niin pitkällä oksistossa kuin on tarve
palaten lopulta runkotasolle mukanaan haluttu tieto kommenttiviestien
lukumäärästä.
Rekursiivisille algoritmeille on tyypillistä, että ne ovat hyvin lyhyitä
ja "kauniita"; toistuuhan sama kuvio yhä uudelleen mentäessä syvemmälle
puun oksistoon. Teho syntyy siitä, että ohjelma kutsuu itseään uudelleen
niin monta kertaa että koko puu kaikkine oksineen on käyty läpi. Riippuen
mm. oksiston syvyydestä tällaiset algoritmit voivat olla joko tajuttoman
tehokkaita tai tuhottoman tehottomia.
Omassa toteutuksessani en ole varsinaisesti käyttänyt rekursiota, vaan
[...] enpäs sanokaan tarkemmin vielä. Olin joka tapauksessa laatinut jo
tehtävää viritellessäni pienen sukron, joka suoriutuu työstä käyttämällä
kahta Survon komentoa: REPLACE ja LINEDEL. Jälkimmäisen voisi helposti
korvata tavanomaisin sukrokielen keinoin, mutta REPLACE on keskeisessä
asemassa, ja sitä käytetään monta monituista kertaa.
Sukroni nimi on MONTAKO, ja se käsittää siististi ladottuna 16 riviä
(epäsiististi 9). Käyttötilanne em. esimerkillä (vrt. aiempi viestini):
/MONTAKO
000671 / 000671-000000.msg
000672 / 000672-000671.msg
000673 / 000673-000671.msg
000674 / 000674-000672.msg
000675 / 000675-000673.msg
000676 / 000676-000675.msg
000677 / 000677-000000.msg
000678 / 000678-000671.msg
000679 / 000679-000678.msg
000680 / 000680-000679.msg
000681 / 000681-000000.msg
000682 / 000682-000681.msg
000683 / 000683-000671.msg
000684 / 000684-000671.msg
"Kävelyvauhdilla" {tempo 2} lista muuntuu n. 18 sekunnissa muotoon
000671 / 000671-000000 10
000677 / 000677-000000 0
000681 / 000681-000000 1
"Täydellä rähinällä" {tempo 0} aikaa ei kulu yhtä sekuntia enempää.
Tehtävässäni antama n. 50 ensimmäisen viestin lista muuntuu vastaavasti
muotoon
000001 / 000001-000000 0
000002 / 000002-000000 6
000004 / 000004-000000 1
000011 / 000011-000000 5
000012 / 000012-000000 2
000020 / 000020-000000 2
000021 / 000021-000000 2
000024 / 000024-000000 2
000027 / 000027-000000 1
000029 / 000029-000000 3
000036 / 000036-000000 4
000037 / 000037-000000 2
000040 / 000040-000000 3
000047 / 000047-000000 1
000050 / 000050-000000 0
n. neljässä sekunnissa. (Summittaiset aikamittaukset 1.7GHz koneella.)
Olen istuttanut algoritmini osaksi ARKISTO-nimistä sukroa (joka koostuu
n. 550 rivistä, ml. muutama kommenttirivi), jonka uusimmat tuotokset
(664 HTML-tiedostoa) ovat nyt esillä osoitteessa www.survo.fi/arkisto .
Kuten sanottu, jätän pähkinästä vielä ytimen pureskeltavaksi juhannuksen
ajaksi ja esittelen tekemäni sukron vasta ensi viikolla. Minulla on siitä
peräti n. 100-rivinen versio, joka dokumentoi homman yksityiskohtaisesti.
Lämmintä juhannusta! ;-)
- Kimmo
| Vastaukset: |
|---|
Survo-keskustelupalstan (2001-2013) viestit arkistoitiin aika ajoin sukrolla, joka automaattisesti rakensi viesteistä (yli 1600 kpl) HTML-muotoisen sivukokonaisuuden. Vuoden 2013 alusta Survo-keskustelua on jatkettu entistäkin aktiivisemmin osoitteessa forum.survo.fi. Tervetuloa mukaan!