From: Wybo Dekker <wybo@...>
Date: 2005-07-19T00:31:03+09:00
Subject: Re: [SOLUTION] Sampling (#39) + comparison

My solution:

n, m, found = ARGV.shift.to_i, ARGV.shift.to_i, []
(n+n*n/m).times do found.push(rand(m)) end 
found.uniq!
found.slice!(n..-1)
found.sort!
found.map! { |i| i.to_s }
puts found.join("\n")

I also compared the various solutions, skipping those that took more than 
a minute:

adam.rb         elap 19.652 user 19.101 syst 0.227 CPU 98.35%
bill.rb         elap 43.157 user 41.780 syst 0.688 CPU 98.40%
ezra.rb         elap 33.861 user 32.193 syst 1.025 CPU 98.10%
joost1.rb       elap 32.797 user 31.447 syst 0.741 CPU 98.14%
joost2.rb       elap 21.465 user 20.336 syst 0.783 CPU 98.38%
wybo1.rb        elap 27.174 user 26.162 syst 0.543 CPU 98.27%
wybo2.rb        elap 23.279 user 22.241 syst 0.678 CPU 98.45%

The first (adam.rb) is not truly random.
wybo1.rb is my final solution shown above. 
wybo2.rb is what I could make inspired by joost1.rb and joost2.rb:

STDOUT.sync = false
GC.disable

num,ceil = ARGV.map { |s| s.to_i }
keep = {}

# only slightly slower but a lot shorter than rolling out:
num.times do 
  keep[rand(ceil)] = true
end

while keep.length < num
    keep[rand(ceil)] = true
end

found = keep.keys
# keeping things in place is faster:
found.sort!
found.map! { |i| i.to_s }
puts found.join("\n")
 
-- 
Wybo