Beefy Boxes and Bandwidth Generously Provided by pair Networks
Don't ask to ask, just ask
 
PerlMonks  

Re: Random Sampling

by ferrency (Deacon)
on Jun 25, 2002 at 20:18 UTC ( #177199=note: print w/ replies, xml ) Need Help??


in reply to Random Sampling

Those are very interesting algorithms, which I was not familiar with. Thank you very much for implementing them.

However, no offense to Mr. Knuth or his S algorithm, but selecting n unique elements from an array containing N elements only needs to consider n elements. The solution below is based on a linear shuffle algorithm I saw on perlmonks. Instead of shuffling all N elements of the array, I instead shuffle the first n elements and return only those shuffled.

The code:

sub selection_sample { my ($array, $n) = @_; my @result; die "Too few elements (". scalar @$array .") to select $n from\n" unless $n <= @$array; my %i; for (0..$n - 1) { my $r = int($_ + rand(@$array - $_)); push @result, $array->[defined($i{$r}) ? $i{$r} : $r]; $i{$r} = defined($i{$_}) ? $i{$_} : $_; } return \@result; }
The basic operation of the linear shuffle is: For each element in the array, randomly choose any element from this element up to the end of the array, and swap the two elements. Please see the original linear shuffle code for a clear demonstration of how to shuffle an entire array.

In the code above, I use a shadow hash %i to store the indices of the shuffled elements of $array. I do this so I can choose a random set from $array without changing the contents of $array, and without copying the entire array. I use a hash %i and defined() tests instead of having to initialize an entire array @i with (0..@$array-1).

I'm not sure of the original requirements of the algorithm, but even using a shadow hash instead of copying the array, my code does use more memory than Knuth's S algorithm. This may not be acceptable in all cases, but if it isn't, then you probably shouldn't be using perl :)

Depending on your requirements, it may be faster or more efficient to chop out the optimizations, which only make sense for a large $array compared to $n (and/or, if you don't want the array to actually be shuffled).

Thanks for the good and inspiring post!

Alan

Update: Ah, your point is well taken: In the context of any data storage which allows only linear access to the records, Knuth's algorithm is definitely the better solution. I'm sorry I seemed to have missed this point.

I do very much like the second algorithm you presented, probably because I didn't miss the point of that one :) I think that most of the time that would be the more appropriate algorithm for my uses when I'm dealing with file access. "Select N random lines from a file" seems like a common task which this would solve efficiently. Most of the time I'm not going to know how many lines I have in the file without counting, which defeats the purpose.


Comment on Re: Random Sampling
Select or Download Code
Re: Re: Random Sampling
by demerphq (Chancellor) on Jun 26, 2002 at 11:15 UTC
    Well, to be honest I think your criticism should be aimed at the way I presented the algorithm (mostly as "proof of concept") than the algorithm itself.

    For instance it would work just fine for a picking N elelements from a file of known arbitrarily large size, regardless of fixed record or not, and of media restrictions (for instance it would work fine for data stroed on a tape).

    Whereas the algorithm you mention (and thanks :-) needs to have the full set in memory at one time, or efficient random access to the records as stored on some form of fixed media (which afaict would require fixed record lengths).

    I realize this criticism applys to my implementation as well, since I used an array. Clearly I shouldnt have as it distracts from the point I was making. :-)

    Thanks for the comments though, added value for the thread for sure.

    Update
    Dont be sorry, I should have explained in more detail. You know the old saying about how

    Ass u me

    is a bad thing...

    ;-)

    Yves / DeMerphq
    ---
    Writing a good benchmark isnt as easy as it might look.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://177199]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (6)
As of 2014-10-25 09:55 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (142 votes), past polls