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.
Sosiaalidemokraattinen satunnaislukugeneraattori
Anonyymi
11
89
Vastaukset
- Anonyymi
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.- Anonyymi
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.- Anonyymi
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
>>>- Anonyymi
No kokeilin kuitenkin miljoonalla ilman tulostusta. Meni ehkä pari sekuntia listan luomiseen, arpomiseen ja tyhjäksi popittamiseen.
- Anonyymi
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
>>> - Anonyymi
Anonyymi kirjoitti:
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).minkkilaukku kirjoitti:
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)).
Ketjusta on poistettu 0 sääntöjenvastaista viestiä.
Luetuimmat keskustelut
Näin asia on
Tiedän ettei hän koskaan aio lähestyä minua eikä niin ole koskaan aikonutkaan, eikä lähesty ja enkä minä enää tee sitä k364992Taas varoitusta lumesta ja jäästä
Ai kauhea! Vakava säävaroitus Lumi-/jäävaroitus Varsinais-Suomi, Satakunta, Uusimaa, Kanta-Häme, Päijät-Häme, Pirkanmaa,322693Örebro kuolleet lisääntyy.
Nyt n, 10. Mitähän vielä. Haavoittuneet?. Kuka on ampuja, salaisuus.1911632Mistä erotat onko joku kiinnostunut vai muuten mukava?
Voi sekaantua yleiseen ystävällisyyteen vai voiko?1611419Poliisi tahtoo pääsyn 4 miljoonan suomalaisen sormenjälkiin.
https://www.is.fi/digitoday/art-2000011009633.html Tämä sormenjälkiin poliisin pääsy on erittäin tärkeä rikollisten kiin1381361Varo sisältöpaljastuksia! Tämän naisen bachelor-Joonas valitsi - Oliko valittu Monica vai Vivianna?
Joonaksella on kaksi naista jäljellä. Mutta valitsiko bachelor kahdesta naisesta Monican vai Viviannan? Oliko mielestäsi241140- 1831133
Trump - otan Gasan haltuun nyt
USA miehittää Gazan alueen ja rakentaa siitä uuden upean alueen aurikoiseen Israeliin. Väkivaltainen alkuperäisväestö h264943Kemettikö lommauttaa
Kemettikö lommauttaa, kuulinpahan vain. Toivottavasti nyt kuitenkin murheenryynit ,tupakoivat laiskimukset poistetaan.24913- 196824