From: jason r tibbetts <tibbettj@...>
Date: 2005-07-16T01:38:16+09:00
Subject: Re: [QUIZ] Sampling (#39)

James,

What are your machine's specs, just for comparison's sake? I don't want 
to get too discouraged by my 5+ year-old Sun beater workstation. :)

I've also found that the printing of the results (in the form of an 
array) is taking several minutes in and of itself. Since optimizing the 
printout probably isn't the point of the quiz, can anyone recommend 
something faster than arr.each{ | elem | p elem } ?

Ruby Quiz wrote:
> The three rules of Ruby Quiz:
> 
> 1.  Please do not post any solutions or spoiler discussion for this quiz until
> 48 hours have passed from the time on this message.
> 
> 2.  Support Ruby Quiz by submitting ideas as often as you can:
> 
> http://www.rubyquiz.com/
> 
> 3.  Enjoy!
> 
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
> 
> This week's Ruby quiz is a classic sampling problem that I've seen many
> interesting solutions for in the past.
> 
> The challenge is to implement a program called "sample" that takes exactly two
> integer inputs.  The first of those should be the number of members you would
> like included in the sample.  The second is the upper boundary (exclusive) of
> the range of integers members can be selected from.  The lower boundary is zero
> (inclusive).
> 
> Your program should output exactly the requested number of members from the
> defined range to STDOUT, one number per line.  Each member must be unique and
> they should appear in sorted order.
> 
> Here are some sample runs of my solution to illustrate the task:
> 
> 	$ ./sample 
> 	Usage:  sample MEMBERS LIMIT
> 	
> 	MEMBERS:  The number of members you want in the sample.  (Integer)
> 	  LIMIT:  The upper limit for the sample range.  All     (Integer)
> 	          members will between 0 and LIMIT - 1.
> 	
> 	Note that MEMBERS must be less than LIMIT.
> 	$ ./sample 3 10
> 	0
> 	1
> 	5
> 	$ ./sample 3 10
> 	1
> 	2
> 	8
> 	$ ./sample 3 10
> 	2
> 	3
> 	9
> 	$ ./sample 9 10
> 	0
> 	2
> 	3
> 	4
> 	5
> 	6
> 	7
> 	8
> 	9
> 	$ ./sample 20 400
> 	1
> 	3
> 	4
> 	25
> 	32
> 	36
> 	42
> 	56
> 	93
> 	111
> 	137
> 	139
> 	153
> 	213
> 	222
> 	226
> 	263
> 	289
> 	293
> 	314
> 
> Now for all the algorithm junkies out there that enjoy a little friendly
> competition, here's the time to beat:
> 
> 	$ time ./sample 5_000_000 1_000_000_000 > big_sample.txt
> 	
> 	real    30m10.593s
> 	user    29m54.544s
> 	sys     0m4.736s
> 	$ ls -l big_sample.txt 
> 	-rw-r--r--   1 james  staff  49011436 Jul 11 15:26 big_sample.txt
> 	$ head big_sample.txt 
> 	112
> 	221
> 	450
> 	655
> 	900
> 	1216
> 	1399
> 	1469
> 	1494
> 	1628
> 	$ tail big_sample.txt 
> 	999995325
> 	999996330
> 	999996552
> 	999996682
> 	999997426
> 	999997676
> 	999998253
> 	999999153
> 	999999658
> 	999999693
> 
> 
>