Tässä tulee uusi putkaposti:
https://www.ohjelmointiputka.net/postit/tehtava.
Pythonilla optimoimaton ratkaisu vei kolmisenkymmentä riviä ja laski kaikki tapaukset yhteensä 2,5 sekunnissa.
Javalla kokeilin hieman erilaista, pikaisesti ajatellen lähes yhtä tehokasta lähestymistapaa, ja pisimmät sarjat ratkesivat tälläkin kolmessa sekunnissa. Nyt en kuitenkaan saanut laskettua lyhyempiä sarjoja samalla kertaa, joten kaikkien ratkaisujen laskeminen vei lähes puoli minuuttia.
Minun Python-ohjelmani laskee tapaukset 6–27 0,5 sekunnissa ja tapaukset 6–100 18 sekunnissa (3 GHz:n suorittimella).
Lievästi optimoidun C-toteutuksen ajoaika on suunnilleen 0,008s, vaihtelee välillä 0ms-16ms. Sama Haskellilla ilman optimointeja vie 0,12s jos käyttää 64-bittisiä kokonaislukuja ja 0,67s jos rajattoman tarkkuuden lukuja. Tapaukset 6-100 vievät n. 4,3s ja tapaukset 6-1000 n. 71s, prosessori 2,2GHz.
1000 295802311446280404383895650972369422351780321315
295271707986874364022548828339599919717634337289
871450358855126574285116429733062126188041599452
519883705765321881142038053615619643413839401175
053894858046253389063266732589740743107884138074
482956678166850317396062074718134737802224014034
591421066762065969179907093717061966075685986123
603193994243457321215507790417708692223686847932
853426084001869961528026749332540587826194311232
355391978567482937301960660319334888593671908211
502356325401269010442971904639101424737314244350
818245914719401784436476653783346064916598019720
944835245058317
Toteutin saman C:llä, ja sillä nopeus on mainittua muutaman millisekunnin luokkaa. Alkuperäinen Python-koodini käsitteli lukuja tekstinä, mutta jostain syystä oikeiden lukujen käyttökään ei nopeuttanut koodia. Olisi mielenkiintoista tietää, millainen pikku optimointi minulta on jäänyt huomaamatta, kun Antin ratkaisu on noin paljon nopeampi. Tapauksen 1000 laskemiseen meni Pythonilla 130 sekuntia, prosessori on 32-bittinen ja kellotaajuus 1,73 GHz.
Voisiko Antin prosessori käsitellä lukuja nopeammin, koska 3 GHz on kuitenkin nopeanpi kuin 1,73 GHz. En jostain syystä jaksa uskoa, että sinulta olisi jäänyt huomaamatta jotakin.
Metabolix kirjoitti:
Olisi mielenkiintoista tietää, millainen pikku optimointi minulta on jäänyt huomaamatta, kun Antin ratkaisu on noin paljon nopeampi.
Vai onkohan ratkaisutapa erilainen? Lähetin sinulle sähköpostia.
Ratkaisutapa on näköjään hyvinkin erilainen ja selvästi mutkikkaampi. Uudempi versio omasta ratkaisustani on hyvin selkeä alle 20-rivisenäkin.
Oma ratkaisu: 22 (merkitsevää) Python-riviä, yhteensä 3 min 37 s. Hidas mutta selkeä algoritmi.
Koodasin uuden algoritmin Haskellilla. Se voi ratkaista isoja tapauksia ilman kaikkien pienempien tuloksia. Tuhannen nopan heittosarja vie sekunnin, ja koska tulos on sama kuin tuo jonka pastesin aiemmin, se on melko varmasti oikein. Kymmenen tuhannen sarja vie 3,5s, sadan tuhannen minuutin, miljoonan 20min. Viimeisen tarkka arvo on 1779850986...9205325019, jossa pisteiden kohdalla on 778132 numeroa.
Wikipediassa on monta hyvää artikkelia tähän liittyen. Jos jotain kiinnostaa, näistä on hyvä aloittaa:
http://en.wikipedia.org/wiki/Markov_chain
http://en.wikipedia.org/wiki/Stochastic_matrix
Miten te käsittelette noin valtavia lukuja? Valmiilla kirjastolla vai jollain omalla ratkaisulla?
Haskellissa ja Pythonissa on valmiina tuki. Yleensä se on toteutettu GMP:llä, ja sitä voi käyttää myös monilla muilla kielillä. Omat ratkaisut tuskin olisivat läheskään yhtä hyviä.
Itse pääsin 1,3 GHz kellotaajuudella tällaiseen tulokseen
$ time python noppa.py 10000 10000 294504624606303899806625...5490470235656924931097 real 0m32.527s user 0m29.954s sys 0m0.048s
missä pisteiden välissä on noin 7700 numeroa. Tuhannen heiton käsittelemiseen menee 1,7s. Ainakin linkeistä päätellen algoritmi lienee samantapainen kuin funktiolla.
Aihe on jo aika vanha, joten et voi enää vastata siihen.