Edelliseen putkapostiin tuli lyhyessä ajassa suuri joukko täydellisiä vastauksia. Tästä palkintona uusi tehtävä ilmestyy etuajassa:
https://www.ohjelmointiputka.net/postit/tehtava.
Putkapostien maailmaan saapuu tämän tehtävän myötä uusi henkilö: maisteri Höpsölä.
Minun silmääni ja aivooni näyttää siltä, että tehtävänannossa on muutama virhe.
Kohdassa Vastausohje puhutaan jaettavasta luvusta vaikka tehtävänannon perusteella käsitin, että kyse pitäisi olla jakavasta luvusta.
Lisäksi tehtävän kuvauksen viimeinan lause "Kuinka monta lukua pitää vähintään yhdistää, jotta lopputulos on jaollinen seuraavilla luvuilla?" mietitty. Onko siis tarkoitus, että lopputulos on jaollinen niillä kaikilla? Vastausohjeesta taas käsitin, että jokaiselle jakajalle pitää ilmoittaa erillinen luku.
Kiitos hyvistä huomioista. Vastauksessa pitää tosiaan ilmoittaa jakava luku eikä jaettavaa lukua, ja tehtävässä on kahdeksan eri tapausta. Muutin väärän sanan oikeaksi sekä selvensin vastausohjetta laajemmalla esimerkillä.
Lähetinpä ratkaisuohjelmani Antille mailitse, vaikka se tuskin sisältää yhtään mitään yllättävää. C-kielinen lyhyt ohjelma vei aikaa muutamia sekunteja ilman erityisiä optimointiyrityksiä.
Oiskohan ollut helpoin putkaposti :)
Tällainen tulos tuli, vieläkö on jotain olennaista optimoitavaa? :)
real 0m2.988s user 0m4.672s sys 0m0.012s
Tällä kertaa muuten assembly tuotti paremman tuloksen kuin C.
Eka on helpoin.
Vai helppo tehtävä... Edes 2 ensimmäistä ei mahtunut 64 bittiin :p
Samantapaisia ongelmia on tullut ratkottua useita, joten tämä ei vaatinut juurikaan miettimistä ja koodiakin vain muutaman rivin.
Pieni spoileri/vinkki: uggc://ra.jvxvcrqvn.bet/jvxv/Zbqhyne_nevguzrgvp.
Toi sun linkkis ei toimi...
Se on ROT13-enkoodattu kuten kaikki muutkin viimeaikaset spoilerit. ROT13 wikipediassa, enkooderi.
Metabolix kirjoitti:
Tällainen tulos tuli, vieläkö on jotain olennaista optimoitavaa? :)
real 0m2.988s user 0m4.672s sys 0m0.012s
Ei luultavasti, tosin omani suoriutuu ajassa 2613 ms @ AthlonXP 2000+ @ -O0. ;)
L2-K2 kirjoitti:
Ei luultavasti, tosin omani suoriutuu ajassa 2613 ms @ AthlonXP 2000+ @ -O0. ;)
Kiinnostaisi nähdä sellainen koodi. En näe mitään tapaa parannella omaani, ja koneeni pitäisi kyllä tuolle pärjätä. Aika on siis koko paketin kokonaisaika.
Metabolix kirjoitti:
L2-K2 kirjoitti:
Ei luultavasti, tosin omani suoriutuu ajassa 2613 ms @ AthlonXP 2000+ @ -O0. ;)
Kiinnostaisi nähdä sellainen koodi. En näe mitään tapaa parannella omaani, ja koneeni pitäisi kyllä tuolle pärjätä. Aika on siis koko paketin kokonaisaika.
Hups. kyseessä oli siis pelkkä isoin... eli sulla on _huomattavasti_* nopeampi koodi. :( (Kokonaisaika 11495 ms, joista 10167 ms kahteen viimeiseen. -O0)
*rautasi?
Intel Pentium Dual-Core 1,73 GHz (T2370). Tuloksessa näkyy erikoisuus, jota kukaan ei vielä ole käynyt ihmettelemässä: kokonaisaika on pienempi kuin prosessoriaika. Tämä selittyy tietenkin muutamalla fork-kutsulla. Ilman forkkia ajoaika vastaa tuota prosessoriaikaa, vajaa viisi sekuntia.
funktio kirjoitti:
Samantapaisia ongelmia on tullut ratkottua useita, joten tämä ei vaatinut juurikaan miettimistä ja koodiakin vain muutaman rivin.
Pieni spoileri/vinkki: uggc://ra.jvxvcrqvn.bet/jvxv/Zbqhyne_nevguzrgvp.
Euo tuosta kyllä ollut mitään apua.
Gvrfva xlyyä rggä zbq 0 xregbb wbf ba wnbyyvara wbyynva yhihyyn zhggn grugäiäffä ba xlfrrffä xäfvggäzäggözäa fhherg yhihg. Wbf fra yhiha ynvggnn fgevatvxfv avva fvvgä ghyrr wb fhhaavyyrra ghunafvn zrexxrwä xha ahzrebg lyvggää 200:a. Vgfr xbxrvyyh ghbyyn uggc://jjj.rfnah.anzr/qrycuv/Nytbevguzf/Znguf/
Ei taas oikeen aukee kun ei ole matemaattisten kaavojen vääntäminen tolla tasolla hallussa.
Kolmas erilainen algoritmikokeilu osoittautui riittävän tehokkaaksi, vaikka tuokin jauhoi yli 10 minuuttia (Python, Athlon 64 3000+). Koodirivien määrä on 6.
Luokittelisin tämän tehtävän vähän keskitasoa helpommaksi putkapostien joukossa.
Juu ei minullakaan oikeen aukea, ku en ole lukiomatematiikkaa viel lukenu...
Sinänsä mukavaa, että on vaihteeksi todella helppo putkaposti - eipähän mene koko iltaa sen parissa.
Se mitä jäin miettimään, että millä kielellä tällainen kannattaisi tehdä koodaukseen kuluvan ajan kannalta ajateltuna. Valmis pseudokoodi nimittäin valmistui pääkopassa 1 minuutissa, mutta sen naputtelu koneen ymmärtämään muotoon vei järkyttävät 14 minuuttia (josta tosin 2 minuuttia meni bugien korjaamiseen kun laitoin vahingossa 77777777 isoimmaksi luvuksi ja yksi vastaus jäi puuttumaan yms)
Itse tein koodin VB.Netillä ja koko tehtävän ratkaisemiseen (yksi ylimääräinen luku eli 7 mukaanlukien) menee 6 sekuntia CPU-aikaa (12 s todellista aikaa) Core Duo T2600:lla.
En nyt optimoinut koodia mitenkään, optimoisin mieluummin kirjoittamiseen kuin suorittamiseen menevää aikaa. :D
Joo lopullinen vastaus ei tosiaankaan vienyt kun pari riviä ja laskeekin suht nopeasti (51.97 sekuntia). Jäi vaan kaivamaan miten tuurilla tuo idea tuli mieleen ja että se sattu toimimaan.
Tulee muuten mieleen, että onkohan tätä tehtävää innoittanut se seikka, että joissain hedelmäpeleissäkin onnekas 777 saa numerologisesti mielenkiintoisen vastauksen.
37,84s melkein samalla koodilla säikeistettynä. Tuplaydin prosessori pääsi kiihdyttelemään ja eron huomaa ihan selkeesti.
Sinänsä mielenkiintoista, innostuin nyt itsekin optimoimaan.. No, oikeastaan tein saman vaan C++:lla kun en oikeastaan keksi mitä tuossa voisi laskennallisesti optimoida.
Mitäköhän mä nyt sit teen väärin, kun tulos on noin paljon huompi kuin Metabolixin 4.6 sekuntia.. Vai oliko C++ tosiaan noin merkittävästi hitaampi kuin assembly vai onko mun Core2 Duo E4500 (2,2GHz) vaan hitaampi kuin Metabolixin prossu tms.
real 0m6.476s user 0m6.472s sys 0m0.002s
En siis tehnyt säikeistystä, joten tulkitsisin, että tuo käytti vain puolta tehoa prossusta ja siten aikaisempaan Windowsilla tehtyyn verrattuna CPU-aika olisi noin puolet (joskin prossukin taitaa olla 40% nopeampi)
..Edit: Nyt ei kyllä riitä ymmärrys.. Poistan loopin sisältä yhden tarkistuksen (25% koodista) niin suoritusaika kasvaa (tosin vain alle 1%)
Vastaavasti loopin lopussa
while (true);
on 2% hitaampi kuin
while (Laskuri < 10000000000);
vaikka laskuri ei koskaan saavuta tuota 10000000000.. Ehkä tässä on joku optimoinnillinen juttu että tuo toinen sattuu tuottamaan prossun kannalta kivemmin järjestyvän koodin, vai onko jollain tiedossa yksinkertaista selitystä moiseen?
On se C++ merkittävästi hitaampi, itselläni tuli sillä muistaakseni 7-8 sekuntia. Nuo parin prosentin muutokset kannattaa jättää huomiotta, ajoaika riippuu monesta muustakin tekijästä ja vaihtelee siis helposti muutamia prosentteja ihan ajokohtaisesti.
Core 2 Duon pitäisi olla parempi kuin Pentium Dual-Coren, tai ominaisuudet ainakin ovat hienommat (Pentiumista puuttuu nimittäin mm. uusin virtualisointihässäkkä, joka Core 2:ssa taas on). Kellotaajuuskin on noin paljon kovempi, niin eiköhän tässä ero löydy koodin optimoinnista. Seuraavassa arveluja syystä.
Lxfv fryvglf ba fvvaä, xhvaxn xäfvggryrg yhiha yvfääzvfra creääa. Wbf fvyzhxnffn ba vssrwä, wbvyyn gnexvfgrgnna, xreebgnnaxb nvrzcv yhxh xlzzraryyä, fnqnyyn inv ghunaaryyn war, buwryznfgn ghyrr vyzrvfrfgv uvgnnzcv xhva wbf ubzzn ubvqrgnna fvfäxxävfvyyä fvyzhxbvyyn (sbe enwn = xlzzrara; enwn < znxfvzv; enwn = xlzzrara * enwn, wn gäzäa fvfäyyä nvan wngxrgnna yhxhwra yvfääzvfgä hhgrra enwnna nfgv.
Nffrzoylyyn clfgll xvewbvggnznna buwryzna 32-ovggvfryyrxva cebfrffbevyyr avva, rggä xnvxxv zhhgghwng cvqrgääa wngxhinfgv erxvfgrervffä. P++ yhhygninfgv xälggää 64-ovggvfrra wnxbynfxhha revyyvfgä shaxgvbgn, wbxn gbvzvv xnvxvffn gncnhxfvffn, zhggn gäffä grugäiäffä wnxnwn (frvfxng) clfll 32-ovggvfraä, wbgra wnxbynfxhha evvggää lxfv gninyyvara qvi-bcrenngvb, wbxn wnxnn rqk:rnk-cneva (64-ovggvä) wn gnyyragnn wnxbwääaaöxfra rqk:ääa.
Joo, periaatteessa olisi kiintoisaa kokeilla tehdä tuo assemblerilla, mutta en ole oikein vihkiytynyt PC-ympäristön assemblerin käyttöön. Siis lähinnä tuntuisi että lopputuloksen tulostaminen ulos vaatisi opettelua. Varmaan löytyy ihan hyviä työkaluja joissa on valmiit kirjastot moiseen.
Tai sitten voisi kokeilla tehdä inline assembleria C++ -koodiin, tms.
Metabolix kirjoitti:
Nuo parin prosentin muutokset kannattaa jättää huomiotta, ajoaika riippuu monesta muustakin tekijästä ja vaihtelee siis helposti muutamia prosentteja ihan ajokohtaisesti.
Itsellä ei kyllä tuo user-aika vaihtele edes 1 promillea ajokerroittain.
Oma assembly-versioni on siis pelkkä laskufunktio, joka saa parametrina jakajan ja palauttaa oikean vastauksen. Tulostamisen hoidan toki perinteisellä C:llä, vaikka C:n standardikirjaston käyttäminen assemblyssa onnistuu kyllä myös helposti.
Grez kirjoitti:
Itsellä ei kyllä tuo user-aika vaihtele edes 1 promillea ajokerroittain.
Mielenkiintoista, nimittäin oman kokemukseni mukaan muutaman sadasosan heittely on aivan normaalia koneella kuin koneella. Suurin vaikutus tuntuu olevan ylimääräisellä taustakuormalla, tulee ilmeisesti prosessinvaihtoja sen verran enemmän, että niistä aiheutuu pientä virhettä. Voi siis tietenkin olla, että aika pysyy täsmälleen samana, jos resurssit ovat hyvin vapaina.
Ehkäpä tuolla koneella sitten on niin vähän taustakuormaa, ettei se pääse vaikuttamaan.
Itse kirjottelin oman ohjelmani javalla noin 5 minuutissa. Kokonaissuoritusaika yhdellä corella noin 4,8 s. Kahdella threadillä suoritusaika on puolestaan noin 2,7 s. Hyvin samanlaiset ajat kuin Metabolixilla :). Taidan tosin saada vähän etua koneesta (Core 2 Duo E6850).
Metabolix kirjoitti:
Tällainen tulos tuli, vieläkö on jotain olennaista optimoitavaa? :)
real 0m2.988s user 0m4.672s sys 0m0.012sTällä kertaa muuten assembly tuotti paremman tuloksen kuin C.
"Hieman" moderninpaa rautaa alle, ja optimoitu C-toteutuskin alkaa kulkea (skaalautuu hyvin kellotaajuuden kanssa):
EDIT: siis samalla raudalla, eli C2D:llä...
Core 2 Duo Conroe @ 3GHz
real 0m4.382s user 0m4.368s sys 0m0.000s
Athlon XP @ 1,67GHz
real 0m8.180s user 0m8.129s sys 0m0.036s
EDIT2: EDIT3:
Ehh...
Pikainen koodin muutos => c++ ja pienet muutokset koodissa yhdistettynä kääntäjän optimointeihin:
"-O3 -march=native -funroll-all-loops -ffast-math"
EDIT3:
Koodin palauttaminen C:ksi EI huonontanut suoritusaikoja, eli ero tuli koodin optimoinneista ja ON todellinen.
antaa aivan käsittämättömiä aikoja Conroella @ 2.4GHz, Athlonilla ajat eivät (käytännössä) muutu. (vastausten pysyessä oikeina)
Conroe:
real 0m1.837s user 0m1.836s sys 0m0.000s
Aihe on jo aika vanha, joten et voi enää vastata siihen.