Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^2: Is there a better way to generate unique set of random numbers ?

by JavaFan (Canon)
on Jul 28, 2011 at 10:02 UTC ( #917237=note: print w/ replies, xml ) Need Help??


in reply to Re: Is there a better way to generate unique set of random numbers ?
in thread Is there a better way to generate unique set of random numbers ?

If you need to generate many more than 10 distinct random numbers, this solution will be faster because the hash lookup works in constant time, whereas your solution has to iterate over the whole array for each number. For 10 there won't be a big difference.
But do note that the only reason your algorithm guarantees to terminate is because rand uses a pseudo random number generator. Were rand to be truly random, neither algorithm could guarantee to be finished before Perl 6 dominates the world.

Here's an algorithm that does terminate:

use List::Util 'shuffle'; my @set = (shuffle(0..1184))[0..9];


Comment on Re^2: Is there a better way to generate unique set of random numbers ?
Select or Download Code
Re^3: Is there a better way to generate unique set of random numbers ?
by moritz (Cardinal) on Jul 28, 2011 at 10:09 UTC
    Were rand to be truly random, neither algorithm could guarantee to be finished before Perl 6 dominates the world.

    Though if you do the math and calculate the probability that either algorithm does not terminate with the given parameters in, let's say, 2 seconds on a modern machine, you'll probably find that the chance of computation errors in the CPU caused by cosmic rays is much higher.

    Doing the strict theory only makes sense if the actual machine corresponds to the machine model that the theory assumes.

      Doing the strict theory only makes sense if the actual machine corresponds to the machine model that the theory assumes.
      Sure, but what's the fun of that? That makes all algorithms either O(1) (aka, "it terminates") or they loop and never terminate.
      use List::Util; sub unique_random_list { my ($from, $to, $count) = @_; $count = List::Util::min ($count, $to - $from); my @result; my @queue = [ $from, $to - $from, $count ]; while (my $job = shift @queue) { my ($from, $length, $count) = @$job; if ($count == $length) { push @result, $from .. $from + $length; } elsif ($count == 1) { push @result, $from + int rand $length; } else { my $split_length = int ($length / 2); my $split_count = List::Util::min (int rand $count, $spli +t_length); my $pad_length = $length - $split_length; my $pad_count = $count - $split_count; $split_count += $pad_count - $pad_length if $pad_count > $pad_length; unshift @queue, grep $_->[2], [ $from, $split_length, $split_count ], [ $from + $split_length, $length - $split_length, $count + - $split_count ]; } } @result; } my @list = unique_random_list (10, 100, 30);

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (8)
As of 2014-07-31 06:35 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (245 votes), past polls