From: Ezra Zygmuntowicz <ezra@...>
Date: 2005-07-18T04:20:14+09:00
Subject: Re: [SOLUTION] Sampling (#39)

Here was my original naive solution which got me down to 28 seconds  
but as people have noted was not really random:

#!/usr/local/bin/ruby
members, limit, index = ARGV[0].to_i, ARGV[1].to_i, 0
member_range = limit / members
0.upto(members-1) do
   res = rand member_range
   puts res + index
   index += member_range
end

That was pretty fast but wasn't a real solution. Here is my final  
solution:

#!/usr/local/bin/ruby

GC.disable

members, limit, samples = ARGV[0].to_i, ARGV[1].to_i, {}

loop do
   break unless samples.length < members
   samples[rand(limit)] = 1
end

result = samples.keys.sort

puts result

     It looks like I went pretty much the same route that Joost went.  
But I didn't optimize it as much as he did. The results are:

ezras-powerbook-g4-17:~/Desktop ez$ time ./sample.rb  5_000_000  
1_000_000_000 >big_sample.txt

real    0m47.496s
user    0m44.523s
sys     0m2.013s
ezras-powerbook-g4-17:~/Desktop ez$ wc big_sample.txt
5000000 5000000 49443742 big_sample.txt
ezras-powerbook-g4-17:~/Desktop ez$ head big_sample.txt
162
312
314
400
564
731
868
1086
1235
1344
ezras-powerbook-g4-17:~/Desktop ez$ tail big.txt
999998406
999998718
999998808
999998843
999998848
999999159
999999307
999999776
999999847
999999864

This was a fun quiz. I really enjoyed it. Thanks James :-)


-Ezra Zygmuntowicz
WebMaster
Yakima Herald-Republic Newspaper
ezra@yakima-herald.com
509-577-7732