Re: Generating 0 .. N Randomly and Efficiently

Here is a first shot, I get perl to allocate me a zero filled string of the correct size. calculate a chance step based on number of numbers left to find. Pick a random number then decrement this in countstep increments each time if find an unset bit in my string. once this is < 0 I look for the next unset bit (if I am not on one), set the bit and return its index.

I can think of a couple of optimisations, moving the endpoints would be a help. for the early numbers I may partiton the space and dive into about the right subblock searching from there although this does risk reducing the randomness...

#!/usr/local/bin/perl
use strict;

my $number=1000;
my $string;
vec $string, $number, 1;

while ($number) {
    my $chance_step = 1/$number;
    my $rand=rand;
    my $i=0;
    while ($rand > 0) {
        if (vec $string, $i++, 1) {
            next
        } else {
            $rand-=$chance_step
        }
    }
    while (vec $string, $i, 1){$i++}
    vec($string, $i, 1)=1;
    print "$i, ";
    $number--
}
[download]

Cheers,
R.

Comment on Re: Generating 0 .. N Randomly and Efficiently Download Code

Replies are listed 'Best First'.
Re^2: Generating 0 .. N Randomly and Efficiently by Limbic~Region (Chancellor) on Oct 19, 2004 at 17:28 UTC
Random_Walk, This is very much like one of my first implementations. The trouble is that by using vec to determine if a bit has been selected, it will get slower and slower the closer to the end it gets. Try changing $number to 50_000 and see what happens the longer it runs. Cheers - L~R	[reply] [d/l]
Re^3: Generating 0 .. N Randomly and Efficiently by Random_Walk (Prior) on Oct 20, 2004 at 13:31 UTC
The problem is not with vec, it is the way I start at the start of the string and count off non set bits till I reach $rand. The following timings are on a dev machine being used by a few so there is plenty of noise. The time to read the last bits of a long string using vec looks constant even with strings spanning several orders of magnitude. #!/usr/local/bin/perl -w use strict; use Benchmark qw(timethese); timethese(5000000, { '1K' => vectest(1000), '10K' => vectest(10000), '100K' => vectest(100000), '1M' => vectest(1000000), '10M' => vectest(10000000), }); sub vectest { my $n=shift; my $s=""; vec $s,$n,1; my $look=vec $s,$n-10,1 } __END__ Benchmark: timing 5000000 iterations of 100K, 10K, 10M, 1K, 1M... 100K: 0 wallclock secs ( 0.59 usr + 0.00 sys = 0.59 CPU) 10K: 1 wallclock secs ( 0.42 usr + 0.00 sys = 0.42 CPU) 10M: 1 wallclock secs ( 0.49 usr + 0.00 sys = 0.49 CPU) 1K: 1 wallclock secs ( 0.89 usr + 0.00 sys = 0.89 CPU) 1M: 1 wallclock secs ( 0.51 usr + 0.00 sys = 0.51 CPU) [download] I have a serious optimisation up my sleave but and rather too busy to code it now :( Hope to have a shot when I get home this evening Cheers, R.	[reply] [d/l]