Tavoitteena on arvontarutiini, joka arpoo aina ensin vähintään yhden per arvontaväli, ennen kuin siirtyy "seuraavalle kierrokselle". Eli jos heitetään vaikka 6-sivuista noppaa ja saadaan luku 3, niin seuraavassa arvonnassa ei ole mukana lukua 3. Kun kaikki kuusi arvoa käyty arpajaisissa lävitse, niin aletaan arpomaan taas kaikkien lukujen kesken.
Kuinkahan tuo olisi järkevin ja kustannustehokkain toteuttaa? Pitääkö tehdä lista? Entä jos lukuja on miljoona? Tulee aika pitkä lista.
Kuinkahan tuo olisi järkevin ja kustannustehokkain toteuttaa? Pitääkö tehdä lista? Entä jos lukuja on miljoona? Tulee aika pitkä lista.
Vastaukset 11
Vanhimmat
Pitää tehdä lista. Muuten et voi tietää mitkä arvonnan tulokset on jo käytetty.
Arvan tilanteen tallentamiseen riittää yksi bitti per arpa. Miljoona arpaa on siis vasta 125000 byteä (8-bittistä) muistia.
Ainakin Pascal :ssa (Lazarus, Free Pascal) tuon on yksinkertaista.
Määrittelet vain taulukon vaikka näin:
var
bitpackedarr :BitPacked array[1..1000000] of boolean;
Niin käytössä on tuo 125000 tavun kokoinen taulukko miljoonalle.
Taulukon koon saa selville esim.
writeln ( IntToStr(SizeOf(bitPackedArr)));
Vaikka sivulla
http://wiki.freepascal.org/Boolean/fi
kerrotaan että boolean tyyppi vie tavun verran niin tuo BitPacked avainsana
pakkaa taulukon joten se vie miljoonan kokoisessa taulukossa vain tuon 125000 tavua.
Binääripuu, johon merkitään tulleet luvut (esim, jos miljoona, niin < 500000 menee vasemmalle ja >= oikealle jne.) Kun paikka löytyy, niin merkataan se luku sinne käytetyksi. Jos jostain haarasta on kaikki luvut käytetty, niin siihen laitetaan fullstoppi, että tämä on tyhjä (eikä sen haaran lukuja tarvitse enää pitää muistissa).
Luvun arpominen tehdään siten, että lähdetään juuresta ja valitaan satunnaisesti jompi kumpi lapsi, paitsi jos toinen on tyhjä. Eikös se tuolla tavalla ainakin ensimmäinen tule täysin tasajakautunut, mutta tuleeko seuraavat jäljellä olevien tasajakaumasta?
En ihan varmaksi osaa sanoa toimisiko tuollainen. Pahimmassa tapauksessahan siinä tulisi "joka toinen" lehtisolmu täyteen ennen kuin yhtään ylemmän tason oksaa saadaan katkaistua, mutta se on erittäin epätodennäköistä että niin käy. Pitäisi kokeilla.
Toisin sanottunahan tuon voisi muuten ottaa niin, että arvotaan luvun binääriesitys ja puussa kulku tehdään sen mukaan tuleeko 0 vai 1.
Pythonilla saa helposti esim. nopan luvut. En jaksa kokeilla miten tuo taipuu isoihin listoihin.
from random import shuffle
luvut=list(range(1,7))
shuffle(luvut)
while len(luvut) > 0:
print(luvut.pop())
>>>
======================== RESTART: /home/hemma/luvut.py ========================
2
3
4
6
5
1
>>>
No kokeilin kuitenkin miljoonalla ilman tulostusta. Meni ehkä pari sekuntia listan luomiseen, arpomiseen ja tyhjäksi popittamiseen.
Ja jos siitä tekee oman funktionsa, niin käyttää sitten globaalia muuttujaa listassa.
from random import shuffle
luvut = []
def arpoja(mista, mihin):
global luvut
if len(luvut) == 0:
luvut=list(range(mista,mihin 1))
shuffle(luvut)
return luvut.pop()
arvontakertoja=10
while(arvontakertoja):
print(arpoja(1,6))
arvontakertoja-=1
arvontakertoja=10
while(arvontakertoja):
print(arpoja(1,6))
arvontakertoja-=1
>>>
======================== RESTART: /home/hemma/luvut.py ========================
2
5
3
1
6
4
3
5
2
1
>>>
Sekoilin copypastessa. Rivejä tuli liikaa. Tässä oikea versio.
from random import shuffle
luvut = []
def arpoja(mista, mihin):
global luvut
if len(luvut) == 0:
luvut=list(range(mista,mihin 1))
shuffle(luvut)
return luvut.pop()
arvontakertoja=10
while(arvontakertoja):
print(arpoja(1,6))
arvontakertoja-=1
Tuleeko käyttötarkoituksessa kaikki M (=yläraja) lukua arvottua vai vain pieni osa niistä? Jos kaikki, niin sitten tuo listaratkaisu on varmaan paras ja nopein. Kokeilin myös sellaista missä listaa ei sekoiteta aluksi, vaan aina luku arvottaessa arvotaan satunnainen indeksi ja otetaan se palautettavaksi ja sitten vaihdetaan se luku listan loppuun ja popataan, mutta tämä näytti olevan hitaampi. Tosin siinä tapauksessa, että niitä arvontoja ei tehdä hirveästi luupissa, niin tämä voisi olla parempi (sillä säästytään listan sekoitukselta aluksi).
Kokeilin myös tehdä tuota binääripuu-versiota, jota ylemmässä viestissä pohdin. Tälläinen siitä tuli: https://codepen.io/minkkilaukku/full/YMvZej Se saattaisi olla hyvä, jos yläraja on erittäin iso ja tosiaan niitä arvontoja ei tehdä paljon, niin säästytään koko jättilistalta, vaan puuhun lisätään solmuja sitä mukaa kun arvontoja suoritetaan. (Joskaan eihän tällöin kovinkaan todennäköisesti tule yhtäsuuria lukuja arvonnoissa muutenkaan, mutta jos halutaan olla täysin varma.) Siinä on kuitenkin aika paljon overheadiä ja ei se satunnainen karsiutuminen taida olla niin suurta, että suurille arvontamäärille se on hitaampi (ja varmaan vie myös rutkasti enemmän muistia, kun siinä on pidettävä linkit myös lapsesta vanhempaan ja muutenkin).
Tuossa erittäin suuren M ja vähän arvontoja -tapauksessa voisi oikeastaan olla hyvä sellainen versio, että pidetään muistissa tulleet, luvut (esim joukko datarakenne, jossa nopea testata inkluusiota) ja jos satunnaisessa arvonnassa tulee jo nähty, niin arvotaan uudelleen.
Tuosta jakaumasta: Jos yläraja M on kakkosen potenssi, niin silloin taitaa tulla tasajakauma, mutta jos ei, niin oikealla puolella olevat luvut tulee "liian usein liian aikaisin". Lisäsin tämän todentamiseksi vähän simulaatiota ja niiden jakaumien kuvantamisen jopa tuonne: https://codepen.io/minkkilaukku/full/YMvZej
Asian voisi ehkä korjata pitämällä joka solmussa muistissa kuinka paljon lukuja on sen oikealla puolella ja kuinka paljon vasemmalla (sellaista strategiaa aluksi koitinkin, mutta siirryin sitten vaan tuohon, että onko solmu tyhjennetty vai ei).
"...kuinka paljon lukuja on sen oikealla puolella ja kuinka paljon vasemmalla"
Siis riittää yksi luku jokaiseen solmuun, että paljonko siinä haarassa on. Vanhempisolmu sitten vertailee lapsistaan ja valitsee niiden perusteella (silloinhan tuo "isDone" tarkoittaisi että 0 jäljellä, joten sekin voidaan korvata tuolla painotetulla tn. arvonnalla, tietenkin yhä, jos lasta ei ole olemassa, niin se täytyy luoda mikäli se haara on ylipäätään sallittu (ei sallittu, jos ollaan liian oikealla (M ei kakkosen potenssi) tai liian alhaalla (tasoja log_2(M):n verran)).