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

Jacob Fugal wrote:
> 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.

Try Jim Freeze's example of doing a run that writes to /dev/null to 
remove disk speed from the equation.