From: Jim Menard <jimm@...>
Date: 2005-07-18T21:26:27+09:00
Subject: [SOLUTION] Sampling (#39)

A fun quiz. Thanks, James.

I've posted my solution at http://www.io.com/~jimm/rubyquiz/quiz39/, but 
here's the whole page.

Here is my solution to Ruby Quiz 39: Sampling. This solution, which takes 
roughly 1.75 minutes to run realtime (0.010 sec user time) is so short, I 
present it here in its entirety:

#! /usr/bin/env ruby

require 'set'

def sample(members, range)
   selected = Set.new
   members.times {
     val = rand(range)
     val = rand(range) until selected.add?(val)
   }
   selected.to_a.sort
end

puts sample(ARGV[0].to_i, ARGV[1].to_i).join("\n")

This solution is completely out-of-the-box. I played with a few optimizations, 
without looking for this algorithm anywhere online. Instead of using a Set 
(which is backed by a Hash), I wanted to create a range-length array and mark 
each selected value using that array, but ran out of memory with a range of 10e9.

Disk I/O took about 45 seconds of the total time. There's probably a way to 
speed that up.

Jim
-- 
Jim Menard, jimm@io.com, http://www.io.com/~jimm
"Verbing weirds language." -- Calvin