From: Dominik Bathon <dbatml@...>
Date: 2005-07-18T08:05:18+09:00
Subject: Re: [SOLUTION] Sampling (#39)

On Sun, 17 Jul 2005 23:52:46 +0200, James Edward Gray II  
<james@grayproductions.net> wrote:

> On Jul 17, 2005, at 8:13 AM, Dominik Bathon wrote:
>
>> Here is my solution:
>
> I need a little revenge, since you slaughtered my initial quiz time...   
> ;)

I have wondered about this, since I first read this week's quiz: Did your  
solution really need half an hour? What is it doing that long?

> Neo:~/Documents/Ruby/Ruby Quiz/solutions/Dominik Bathon$ time ./sample  
> 999_999 1_000_000 > /dev/null
>
> real    0m28.151s
> user    0m27.846s
> sys     0m0.298s
> Neo:~/Documents/Ruby/Ruby Quiz/solutions/Dominik Bathon$ cd ../James\  
> Edward\ Gray\ II/
> Neo:~/Documents/Ruby/Ruby Quiz/solutions/James Edward Gray II$ time ./ 
> sample 999_999 1_000_000 > /dev/null
>
> real    0m5.903s
> user    0m5.884s
> sys     0m0.019s
>
> Not really picking on you Dominik.  Just showing that there are other  
> problems in this challenge besides the one I initially posted.

Yes, I (and most of the others) didn't handle that special case. As Joost  
Diepenmaat said in his reply to Bill Kelly's solution:

As soon as samples.size > total.size / 2 it's trivial to turn the
algorithm on its head (i.e. randomly select items that you'll skip,
then loop through the set and print all items that aren't selected).

I've extended my solution a bit to see how many values are rejected until  
999_999 unique values in 0...1_000_000 are found: about 12_000_000

> My code above is what I used in creating the quiz.  I'll post it when I  
> get some time.
>
> James Edward Gray II