develooper Front page | perl.beginners | Postings from April 2002

RE: Scripts picks random elements from array , but it repeats sometimes

Thread Next
From:
Bob Showalter
Date:
April 29, 2002 14:04
Subject:
RE: Scripts picks random elements from array , but it repeats sometimes
Message ID:
2E4528861499D41199D200A0C9B15BC031B9D7@taylorwhite.com
> -----Original Message-----
> From: drieux [mailto:drieux@wetware.com]
> Sent: Monday, April 29, 2002 4:51 PM
> To: beginners@perl.org
> Subject: Re: Scripts picks random elements from array , but it repeats
> som etimes
> 
> 
> 
> On Monday, April 29, 2002, at 01:03 , Bob Showalter wrote:
> 
> > May I suggest a modification of the algorithm that avoids this
> > problem:
> >
> >    1. generate a random index from 1 to (number of 
> remaining elements)
> >    2. use the element at that index
> >    3. move the last element into the index generated
> >    4. decrement the number of remaining elements.
> 
> My complements on a well written analysis of the core algorithm.
> 
> My concern of course is that since this strategy is destructive
> of the @array being searched, that one might find it slightly
> faster to simply slice the array in flight....
> 
> http://www.wetware.com/drieux/CS/lang/Perl/Beginners/BenchMark
s/randTest.txt

splice() will be slower as the size of the array grows. If I take
your benchmark and change to array from 1..100 to 1..10000, I get
the following results for 100 iterations (on an old Pentium 266):

Benchmark: timing 100 iterations of consume, decLoop...
   consume: 51 wallclock secs (50.72 usr +  0.03 sys = 50.75 CPU) @  1.97/s
(n=100)
   decLoop: 19 wallclock secs (19.45 usr +  0.01 sys = 19.46 CPU) @  5.14/s
(n=100)


Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About