From: Ezra Zygmuntowicz <ezra@...>
Date: 2005-07-16T06:30:15+09:00
Subject: Re: [QUIZ] Sampling (#39)


On Jul 15, 2005, at 1:27 PM, jason r tibbetts 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?
>
>
>
>
Nope This is running on a single 1.6Ghz G5 tower with about 15 other  
programs running including photoshop and dreamweaver. And my solution  
is only 9 lines of code ;-) Here's some more results with a little  
more time shaved off:
ezra:~/Sites/______raill_stuff ez$ time ./sample.rb 5_000_000  
1_000_000_000 >  big_sample.txt

real    0m39.860s
user    0m34.343s
sys     0m1.370s
ezra:~/Sites/______raill_stuff ez$ ls -l big_sample.txt
-rw-r--r--   1 ez  ez  49444444 Jul 15 14:25 big_sample.txt
ezra:~/Sites/______raill_stuff ez$ head big_sample.txt
61
260
555
666
816
1126
1349
1552
1740
1862
ezra:~/Sites/______raill_stuff ez$ tail big_sample.txt
999998018
999998306
999998426
999998735
999998949
999999011
999999340
999999480
999999643
999999840
ezra:~/Sites/______raill_stuff ez$

-Ezra Zygmuntowicz
Yakima Herald-Republic
WebMaster
509-577-7732
ezra@yakima-herald.com