in reply to Re^4: Random data generation.
in thread Random data generation.

The length of the generated data is a parameter that does not modify the ranking because the costs of all the given solutions are linear to it.

If you change the set size or the maximun number of consecutive repetitions instead, then the ranking is not so stable. The benchmarks below show it.

I have also added a new solution salva2 (much faster in average) and some variations of almut's one.

The code: 

ur @set;
our $max_reps;
our $len;

sub gen_almut {
    my $result = '';
    while (length($result) < $len) {
        my $char = $set[ rand @set ];
        next if substr($result, -$max_reps) eq $char x $max_reps;
        $result .= $char;
    }
    $result;
}

sub gen_almut_mod2 {
    my $result = '';
    for (1..$len) {
        my $char = $set[ rand @set ];
        redo if substr($result, -$max_reps) eq $char x $max_reps;
        $result .= $char;
    }
    $result;
}

sub gen_almut_mod3 {
    my $result = '';
    my $char;
    for (1..$len) {
        do { $char = $set[ rand @set ] }
            while substr($result, -$max_reps) eq $char x $max_reps;
        $result .= $char;
    }
    $result;
}

sub gen_almut_mod4 {
    my $result = '';
    while (length($result) < $len) {
        my $char = $set[ rand @set ];
        $result .= $char 
            if substr($result, -$max_reps) ne $char x $max_reps;
    }
    $result;
}

my $buf;
sub gen_salva2 {
    while (length $buf < $len) {
        $buf .= $set[rand @set] for (1..$len*100);
        $buf =~ s/(.)\1{$max_reps,}/$1 x $max_reps/ge;
    }
    substr($buf, -$len, $len, '');
}

sub gen_salva {
    my $out = '';
    my $last_ix = -1;
    my $reps = 0;
    for (1..$len) {
        my $ix;
        if ($reps >= $max_reps) {
            $ix = int rand(@set - 1);
            $ix++ if $ix >= $last_ix;
        }
        else {
            $ix = int rand(@set);
        }
        if ($ix == $last_ix) {
            $reps++;
        }
        else {
            $last_ix = $ix;
            $reps = 1;
        }
        $out .= $set[$ix];
    }
    $out;
}

use Benchmark qw(cmpthese);

$len = 12;

for my $elements (2, 5, 10) {
    @set = (1..$elements);
    for $max_reps (1, 2, 3) {
        print "elements: $elements max_reps: $max_reps\n";
        $buf = '';
        cmpthese(-4, {
                      almut      => \&gen_almut,
                      almut_mod2 => \&gen_almut_mod2,
                      almut_mod3 => \&gen_almut_mod3,
                      almut_mod4 => \&gen_almut_mod4,
                      salva2     => \&gen_salva2,
                      salva      => \&gen_salva
                     } );
    }
}

[download]

And the benchmarking results: 

elements: 2 max_reps: 1
              Rate     almut almut_mod4 almut_mod3 almut_mod2   salva2
+     salva
almut      37325/s        --        -2%       -10%       -10%     -13%
+      -28%
almut_mod4 38188/s        2%         --        -8%        -8%     -11%
+      -26%
almut_mod3 41453/s       11%         9%         --        -0%      -3%
+      -20%
almut_mod2 41553/s       11%         9%         0%         --      -3%
+      -20%
salva2     42707/s       14%        12%         3%         3%       --
+      -18%
salva      51951/s       39%        36%        25%        25%      22%
+        --
elements: 2 max_reps: 2
              Rate almut_mod3     almut almut_mod4 almut_mod2     salv
+a   salva2
almut_mod3 56662/s         --       -2%        -2%        -3%       -3
+%     -15%
almut      57823/s         2%        --        -0%        -1%       -1
+%     -14%
almut_mod4 58097/s         3%        0%         --        -0%       -1
+%     -13%
almut_mod2 58234/s         3%        1%         0%         --       -1
+%     -13%
salva      58651/s         4%        1%         1%         1%        -
+-     -12%
salva2     66988/s        18%       16%        15%        15%       14
+%       --
elements: 2 max_reps: 3
              Rate     salva almut_mod3     almut almut_mod4 almut_mod
+2   salva2
salva      60150/s        --        -0%       -8%        -9%       -10
+%     -24%
almut_mod3 60258/s        0%         --       -8%        -9%       -10
+%     -24%
almut      65430/s        9%         9%        --        -1%        -2
+%     -18%
almut_mod4 65946/s       10%         9%        1%         --        -1
+%     -17%
almut_mod2 66827/s       11%        11%        2%         1%         -
+-     -16%
salva2     79446/s       32%        32%       21%        20%        19
+%       --
elements: 5 max_reps: 1
              Rate     salva     almut almut_mod3 almut_mod4 almut_mod
+2   salva2
salva      51954/s        --       -8%        -9%       -10%       -14
+%     -23%
almut      56479/s        9%        --        -1%        -2%        -7
+%     -16%
almut_mod3 56799/s        9%        1%         --        -1%        -6
+%     -15%
almut_mod4 57418/s       11%        2%         1%         --        -5
+%     -15%
almut_mod2 60666/s       17%        7%         7%         6%         -
+-     -10%
salva2     67156/s       29%       19%        18%        17%        11
+%       --
elements: 5 max_reps: 2
              Rate     salva almut_mod3 almut_mod2 almut_mod4     almu
+t   salva2
salva      57703/s        --       -11%       -18%       -18%      -18
+%     -34%
almut_mod3 65188/s       13%         --        -7%        -7%       -7
+%     -25%
almut_mod2 70102/s       21%         8%         --        -0%       -0
+%     -19%
almut_mod4 70338/s       22%         8%         0%         --       -0
+%     -19%
almut      70435/s       22%         8%         0%         0%        -
+-     -19%
salva2     87051/s       51%        34%        24%        24%       24
+%       --
elements: 5 max_reps: 3
              Rate     salva almut_mod3     almut almut_mod2 almut_mod
+4   salva2
salva      59097/s        --       -11%      -17%       -17%       -18
+%     -36%
almut_mod3 66428/s       12%         --       -7%        -7%        -8
+%     -28%
almut      71086/s       20%         7%        --        -0%        -2
+%     -23%
almut_mod2 71117/s       20%         7%        0%         --        -2
+%     -23%
almut_mod4 72395/s       23%         9%        2%         2%         -
+-     -21%
salva2     91896/s       56%        38%       29%        29%        27
+%       --
elements: 10 max_reps: 1
              Rate     salva almut_mod3 almut_mod2     almut almut_mod
+4   salva2
salva      51468/s        --       -17%       -22%      -26%       -26
+%     -39%
almut_mod3 61696/s       20%         --        -7%      -11%       -11
+%     -27%
almut_mod2 66266/s       29%         7%         --       -4%        -4
+%     -21%
almut      69256/s       35%        12%         5%        --        -0
+%     -18%
almut_mod4 69269/s       35%        12%         5%        0%         -
+-     -18%
salva2     84117/s       63%        36%        27%       21%        21
+%       --
elements: 10 max_reps: 2
              Rate     salva almut_mod3 almut_mod2 almut_mod4     almu
+t   salva2
salva      57688/s        --       -12%       -20%       -25%      -26
+%     -41%
almut_mod3 65386/s       13%         --        -9%       -15%      -17
+%     -33%
almut_mod2 72116/s       25%        10%         --        -6%       -8
+%     -26%
almut_mod4 77021/s       34%        18%         7%         --       -2
+%     -21%
almut      78381/s       36%        20%         9%         2%        -
+-     -19%
salva2     97336/s       69%        49%        35%        26%       24
+%       --
elements: 10 max_reps: 3
              Rate     salva almut_mod3 almut_mod2 almut_mod4     almu
+t   salva2
salva      59236/s        --        -9%       -18%       -25%      -25
+%     -39%
almut_mod3 65161/s       10%         --       -10%       -17%      -17
+%     -33%
almut_mod2 72259/s       22%        11%         --        -8%       -8
+%     -26%
almut_mod4 78569/s       33%        21%         9%         --       -0
+%     -19%
almut      78580/s       33%        21%         9%         0%        -
+-     -19%
salva2     97565/s       65%        50%        35%        24%       24
+%       --

[download]
Note that the salva2 algorithm has some bias. It is able to generate all the valid solutions but not all of them have the same probability.

Replies are listed 'Best First'.
Re^6: Random data generation.
by BrowserUk (Patriarch) on Jun 28, 2010 at 11:48 UTC

    Actually, the number of reps allowed is the one parameter that doesn't vary for my scenario. Also, the length of the string will never be less than the size of the set.

    The approach you use in salva2 is very interesting, and does make it come out first in every benchmark I've run. One of my own alternatives used a similar approach: Generate a big string completely at random and then pick out a compliant N-char length lump with a regex and return it. Your innovations of a) making the whole string compliant using a regex, b) retaining the buffer across calls; combine to make the approach viable.

    The funny thing is that I'm already effectively using the latter part in my code (but not the benchmarks), in as much as I need a bunch of short strings, but I'm calling the generator for one long string and then chopping it into bits using unpack "(A$N)*', gen( $N * 100, @set ). That negates a part of salva2's advantage, and also trades the cost of unpack against the cost of multiple calls to the generator.

    Now I have to consider whether your generate a big string and the regex it into compliance approach would still be quicker in-situ. It's not an easy thing to benchmark. Neither is considering the affect it has on the randomness of the result.

    It's quite amazing how many variations can result from an ostensibly simple spec. Many thanks for your input.

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]
[d/l]
      Neither is considering the affect it has on the randomness of the result

      Well, actually it is!

      Given the $size of the test, the probability of salva2 generating a string starting by two equal characters is 1/($size+1) instead of the 1/$size in the other methods.

      The funny thing is that salva2 is unbiased, they are the other methods that are actually biased!!!

      The following code counts the number of repetitions at any given position in the generated strings: 

      @set = (1..3);
$max_reps = 2;
$len = 10;

my @acu = ([], []);
my @gen = (\&gen_salva, \&gen_salva2);

my ($total, $ds) = (0,0);
my $n = 10000000;
for (1..$n) {
    for (0, 1) {
        my $out = $gen[$_]->();
        while ($out =~ /(.)\1/g) {
            $acu[$_]->[pos($out) - 2]++;
        }
    }
}

use Data::Dumper;
print Dumper \@acu;

      [download]
      And this is the result: 
      salva  => [ 3333044, 2222094, 2591285, 2469706, 2509595, 2496496, 2501
+039, 2501529, 2497584 ]
salva2 => [ 2500639, 2498220, 2499044, 2501878, 2500880, 2500962, 2498
+685, 2499675, 2508077 ]

      [download]

      So, with salva2 the probability of finding a repetition at any position is 1/($size+1) while with the rest of methods the probability varies between the maximum 1/$size (at position 0) and the minimum ($size-1)/$size**2 (at position 1).

[reply]
[d/l]
[select]

        Wow!

        Please excuse my lack of literacy and analysis; but wow! A mathematician that can program. Well, who knew :)

        Sorry to conform to the "Brit stereotype", and complain about the weather, but 10 days of no rain; 4 days of 30C days and 20C+ nights leave me stupefied through lack of sleep. I'll attempt the analysis understanding later when I hopefully will have had more than 60 contiguous minutes of slumber.

[reply]
Re^6: Random data generation.
by furry_marmot (Pilgrim) on Jun 29, 2010 at 17:48 UTC

    I think there might be a little bug in salva2. I copied the code from Re^5: Random data generation to try my own solution (middle of the pack, not worth posting), but while studying the code, I noticed a potential problem. my $buf is declared just before gen_salva2.

    my $buf;
sub gen_salva2 {
    while (length $buf < $len) {
        $buf .= $set[rand @set] for (1..$len*100);
        $buf =~ s/(.)\1{$max_reps,}/$1 x $max_reps/ge;
    }
    substr($buf, -$len, $len, '');
}

    [download]

    So I put it inside sub gen_salva2{} and ran it again. I bencharked only for $elements = 6, $max_reps = 2, to match BrowserUK's original parameters. That and the change to gen_salva2 are the only changes. Notice how the rankings change.

    elements: 6 max_reps: 2
              Rate   salva2     salva almut_mod3 almut_mod4 almut_mod2
+     almut
salva2      1077/s       --      -98%       -98%       -98%       -98%
+      -98%
salva      54086/s    4922%        --       -10%       -13%       -13%
+      -17%
almut_mod3 59766/s    5450%       11%         --        -4%        -4%
+       -8%
almut_mod4 61953/s    5653%       15%         4%         --        -1%
+       -5%
almut_mod2 62270/s    5682%       15%         4%         1%         --
+       -5%
almut      65222/s    5956%       21%         9%         5%         5%
+        --

    [download]

    I thought gen_salva2 got its amazing speed boost by using an already populated $buf. After running the benchmark, I reduced the count to 100 and added a print line before creating $buf to test this theory.

    my $buf;
sub gen_salva2 {
    print "$buf\n";
    while (length $buf < $len) {
        $buf .= $set[rand @set] for (1..$len*100);
        $buf =~ s/(.)\1{$max_reps,}/$1 x $max_reps/ge;
    }
    substr($buf, -$len, $len, '');
}

    [download]

    This printed a string 1164 chars long: 4235621656212414423622661645561656223662351124233115.... Each time through, it reduces the length by 12, which is then printed. When the string is too small, it generates a new one. The while() loop is simply not executed very often -- about 1 in 96 to 98 times on average.

    --marmot
[reply]
[d/l]
[select]
      It is not a bug, gen_salva2 is designed to work that way!

      $buf is populated by gen_salva2 but instead of generating data for just one output string it generates data for 100 of them (a few less, actually). Next calls to gen_salva2 do not need to fill $buf again as it already contains data (until exhausted, then it is refilled).

      That's also the reason my previous comment said it was faster on average!

[reply]

        OOOHHHHhhhhhh... Now I get it. Never mind. :-(

[reply]

In Section Seekers of Perl Wisdom