En rubyfråga om hur hitta unika slumptal

Om du har en begränsad mängd tal att välja från kan det vara en idé att ha lägga alla möjliga tal i en lista, och sedan plocka ett slumpmässigt valt tal därifrån. Det valda talet tas sedan bort från listan. Listan kan skapas sekventiellt, alltså ordningen 0, 1, 2, ..., eftersom du väljer index slumpmässigt. Detta är mer effektivt än att slumpa ordningen.

Såvida det inte är stor overhead för att lagra heltal så borde talen [0, 65535] ta upp under en megabyte:

$ irb
irb(main):001:0> 65535.size * 65536.0 / 1024**2
=> 0.5

Om talen inte är tillräckligt begränsade kan en lösning vara att lagra skapade tal i en lista/tabell. För att slippa linjär söktid är en (hash)map troligtvis bäst. När du ska generera ett tal fortsätter du tills du fått fram ett som inte finns i tabellen. I worst case är dock detta väldigt ineffektivt.

Edit: Förtydligande: Första lösningen är bäst med en array-baserad lista, där index-baserad åtkomst sker med konstant tid. Effektiv borttagning ur en array-baserad lista kan göras genom att byta plats på sista elementet och det element som ska tas bort, och sedan ta bort det nya "sista elementet" (alltså det som ska bort). Alltså (pseudokod):

i = rand(0, MAX)
list.swap(i, list.size() - 1)
list.remove_index(list.size() - 1)

Detta sker troligtvis på konstant tid (beroende på hur Rubys implementation ser ut).

Slumptal är inte unika. Om du vill ha ett unikt tal (ett ID), börja på 0 och öka successivt.

Det stämmer att slumptal i sig inte är unika, men man kan ändå vilka ha icke-sekventiella, unika tal.

Möjligtvis. Skulle vara intressant att veta varför TS vill ha just "unika slumptal".

Vad sägs om att ha en klasspecifik heltalscounter som ökar för varje ny klassinstans och så plussar man på ett slumptal i intervallet [0,1] dessutom. Det borde uppfylla kraven

Jo, det är så man brukar definiera "unikt". Men varför vill du ha slumpade tal?