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
<50
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
- 261831
Miksi ihmeessä nainen seurustelit kanssani joskus
Olin ruma silloin ja nykyisin vielä rumempi En voi kuin miettiä että miksi Olitko vain rikki edellisestä suhteesta ja ha221749Heikki Silvennoinen petti vaimoaan vuosien ajan
Viiden lapsen isä Heikki kehuu kirjassaan kuinka paljon on pettänyt vaimoaan vuosien varrella.1081662Persut nimittivät kummeli-hahmon valtiosihteeriksi!
Persujen riveistä löytyi taas uusi törkyturpa valtiosihteeriksi! Jutun perusteella järjenjuoksu on kuin sketsihahmolla.691541Minun oma kaivattuni
Ei ole mikään ilkeä kiusaajatyyppi, vaan sivistynyt ja fiksu sekä ystävällinen ihminen, ja arvostan häntä suuresti. Raka721528Pelastakaa Lapset: Netti ei ole turvallinen paikka lapsille - Erätauko-tilaisuus to 25.4.2024
Netti ei ole turvallinen paikka lapsille, mutta mitä asialle voi vanhempana tehdä? Torstaina 25.4.2024 keskustellaan ne231426Onko ministeri Juuso epäkelpo ministerin tehtäviensä hoitamiseen?
Eikö hänellä ole kompetenttia hoitaa sosiaali- ja terveysministetin toimialalle kuuluvia ministerin tehtäviä?581405Sakarjan kirjan 6. luku
Jolla korva on, se kuulkoon. Sain profetian 22.4.2023. Sen sisältö oli seuraava: Suomeen tulee nälänhätä niin, että se191222Tervehdys!
Sä voit poistaa nää kaikki, mut mä kysyn silti A:lta sen kokemuksia sun käytöksestä eron jälkeen. Btw, miks haluut sabot651150Elia tulee vielä
Johannes Kastaja oli Elia, mutta Jeesus sanoi, että Elia tulee vielä. Malakian kirjan profetia Eliasta toteutuu kokonaan361145