From: Jacob Fugal <lukfugl@...>
Date: 2005-07-16T05:37:04+09:00
Subject: Re: [QUIZ] Sampling (#39)

On 7/15/05, jason r tibbetts <tibbettj@verdi.iisd.sra.com> wrote:
> David Brady wrote:
> > Belorion wrote:
> >
> >> I think Jim's point was that if your last digit is 462470382 then you
> >> don't have a random sample... which is specified as a criteria for the
> >> quiz.
> >>
> > "People who think about this topic almost invariably get into
> > philosophical discussions about what the word "random" means.  In a
> > sense, there is no such thing as a random number; for example, is 2 a
> > random number?"
> > -- Donald Knuth, The Art of Computer Programming, Vol II (2nd Edition),
> > page 2.
> >
> > Knuth, in turn, quotes John Von Neumann, on the preceding page:
> > "Any one who considers arithmetical methods of producing random digits
> > is, of course, in a state of sin."
> >
> > Knuth goes on to quantify various properties of randomness; Cassio's
> > method fails the very first one (uniform distribution).  But meh: Cassio
> > has just steeped in the evil a little longer. :-)
> >
> > I would be interested to see a uniform solution approach Cassio's solution.
> >
> > This is a GREAT Quiz, by the way.  I've keyed in a standard, textbook
> > solution to this problem and my runtime is 9.5 minutes for ONE TENTH of
> > the sample (sampling 500K from 100M).  Assuming purely O(n), that's 1.6
> > *hours* to run the full sample on my Athlon 2200.  So, I have a
> > solution, and I could quit now.  But now I want to try my hand playing
> > with the profiler.  :-)
> 
> Ezra's output looks like what you're looking for, but it seems to have
> gone unnoticed in the wake of Cassio's post.
> 
> > ezra:~/Sites ez$ time ./sample.rb 5_000_000 1_000_000_000 >  big_sample.txt
> >
> > real    0m43.838s
> > user    0m35.820s
> > sys     0m1.360s
> > ezra:~/Sites ez$ ls -l big_sample.txt
> > -rw-r--r--   1 ez  ez  49444445 Jul 15 10:46 big_sample.txt
> > ezra:~/Sites ez$ head big_sample.txt
> > 168
> > 285
> > 566
> > 604
> > 912
> > 1183
> > 1335
> > 1473
> > 1728
> > 1919
> > ezra:~/Sites ez$ tail big_sample.txt
> > 999998155
> > 999998313
> > 999998484
> > 999998680
> > 999998825
> > 999999151
> > 999999330
> > 999999465
> > 999999621
> > 999999877
> > ezra:~/Sites ez$
> 
> I /really/ want to know how this is possible. Multi-processor solution?

The thing that really gets me is the disk latency. Here's my trial for
just writing 5_000_000 numbers to disk:

$ cat test.rb
5_000_000.times { |i| puts i }

$ time ruby test.rb > big_file.txt 

real    0m41.781s
user    0m26.436s
sys     0m2.626s

That's 41 seconds just to write to disk. Ezra's disk may be
faster/better, but still I'd bet at least half the time reported is
spent in I/O. His algorithm must be phenomenal to get down to that
speed.

As a side note (not saying Ezra did this, but I am tempted to do it),
would a program utilizing RubyInline be permitted? :)

Jacob Fugal