Re: Pieni kesäpähkinä survoilijoille!

[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!

Etusivu  |  Keskustelu
Copyright © Survo Systems 2001-2013. All rights reserved.
Updated 2013-06-15.