Fast random string generation

D

Derek Fountain

I need to generate a string of random characters, say about 20,000
characters long. And I need to do it quickly! I tried the obvious:

for( my $i=0; $i<20000; $i++ ) {
$str .= chr(int(rand(256)));
}

which works, but I have a feeling there must be a faster way than doing
20,000 string concatenations...?
 
D

Dave Oswald

"Derek Fountain" wrote in message
I need to generate a string of random characters, say about 20,000
characters long. And I need to do it quickly! I tried the obvious:

for( my $i=0; $i<20000; $i++ ) {
$str .= chr(int(rand(256)));
}

which works, but I have a feeling there must be a faster way than doing
20,000 string concatenations...?

If speed actually matters (which it may not), you'll have to benchmark this
solution, comparing it to yours. They may turn out to be reasonably close
to each other in speed.

my $string = join '', map { chr int rand(256) } 1 .. 20_000;

Here's another solution that pre-generates the 'chr' possibilities, and
thus, MAY be a little more efficient.

my @characters = map { chr $_ } 0 .. 255;
my $string = join '', map { $characters[ rand 256 ] } 1 .. 20_000;

Dave
 
A

Ala Qumsieh

Derek said:
I need to generate a string of random characters, say about 20,000
characters long. And I need to do it quickly! I tried the obvious:

for( my $i=0; $i<20000; $i++ ) {
$str .= chr(int(rand(256)));
}

which works, but I have a feeling there must be a faster way than doing
20,000 string concatenations...?

I didn't benchmark, but I would guess it's faster to call chr() 256
times instead of 20000 times:

# untested code
my @list = map chr, 0 .. 256;
my $str = '';
$str .= $list[rand @list] for 1 .. 20_000;

--Ala
 
P

Peter J. Acklam

Derek Fountain said:
I need to generate a string of random characters, say about
20,000 characters long. And I need to do it quickly! I tried the
obvious:

for( my $i=0; $i<20000; $i++ ) {
$str .= chr(int(rand(256)));
}

which works, but I have a feeling there must be a faster way
than doing 20,000 string concatenations...?

my $str = "\000" x 20_000;
my @chr = map { chr $_ } 0 .. 255;
substr $str, $_, 1, $chr[rand 256] for 1 .. 20_000;

Peter
 
R

Randal L. Schwartz

Peter> my $str = "\000" x 20_000;
Peter> my @chr = map { chr $_ } 0 .. 255;
Peter> substr $str, $_, 1, $chr[rand 256] for 1 .. 20_000;

maybe:

pack "C*", map rand 256 for 1 .. 20_000;
 
B

Bart Lateur

Ala said:
I didn't benchmark, but I would guess it's faster to call chr() 256
times instead of 20000 times:

# untested code
my @list = map chr, 0 .. 256;
my $str = '';
$str .= $list[rand @list] for 1 .. 20_000;

It's also not very random. I don't think it's the idea to have a repeat
period of 256 cycles.
 
B

Bart Lateur

Derek said:
I need to generate a string of random characters, say about 20,000
characters long. And I need to do it quickly! I tried the obvious:

for( my $i=0; $i<20000; $i++ ) {
$str .= chr(int(rand(256)));
}

which works, but I have a feeling there must be a faster way than doing
20,000 string concatenations...?

I have the following basic 3 ideas:

1) prebuild a string of 20000 bytes, and use substr to replace the
concatenation:

$x = " " x 20000;
substr($x, $_, 1) = chr rand 256 for 0 .. 19999;


2) ditto, but use vec() (bypasses chr()):

$x = " " x 20000;
vec($x, $_, 8) = rand 256 for 0 .. 19999;


3) use pack 'C*' to replace all of the chr() calls + concat/join:

$x = pack 'C*', map int rand 256, 1 .. 20000;
 
J

John W. Kennedy

Bart said:
Ala Qumsieh wrote:

I didn't benchmark, but I would guess it's faster to call chr() 256
times instead of 20000 times:

# untested code
my @list = map chr, 0 .. 256;
my $str = '';
$str .= $list[rand @list] for 1 .. 20_000;


It's also not very random. I don't think it's the idea to have a repeat
period of 256 cycles.

Neither suggestion does.
 
M

Michele Dondi

I need to generate a string of random characters, say about 20,000
characters long. And I need to do it quickly! I tried the obvious:

OK, here are the benchmarks of some of the proposed solutions along
with some other idea.

BTW: I'm to say the least in a rush and I could absoultely NOT verify
that my 'Pack2' solution is correct. But in case it is notm then I
guess that it can be easily corrected.

#!/usr/bin/perl

use strict;
use warnings;

use Benchmark qw/:all/;

cmpthese 500, {
Loop1 => \&Loop1,
Loop2 => \&Loop2,
Map1 => \&Map1,
Map2 => \&Map2,
Subst => \&Subst,
Vec => \&Vec,
Pack1 => \&Pack1,
Pack2 => \&Pack2,
S => \&S
};


sub Loop1 {
my $str = '';
$str .= chr int rand 256 for 1..20_000;
$str;
}

sub Loop2 {
my @chrs = map chr, 0..255;
my $str = '';
$str .= $chrs[rand 256] for 1..20_000;
$str;
}

sub Map1 {
join '', map { chr int rand 256 } 1..20_000;
}

sub Map2 {
my @chrs = map chr, 0..255;
join '', map $chrs[rand 256], 1..20_000;
}

sub Subst {
my $str = "\000" x 20_000;
my @chrs = map chr, 0..255;
substr $str, $_, 1, $chrs[rand 256] for 0..19_999;
$str;
}

sub Vec {
my $str = ' ' x 20000;
vec($str, $_, 8) = rand 256 for 0..19_999;
$str;
}

sub Pack1 {
pack 'C*', map int rand 256, 1..20_000;
}

sub Pack2 {
# Is this OK, BTW?
pack 'L*', map rand ~0, 1..5_000;
}

sub S {
local $_ = ' ' x 20_000;
s/ /chr int rand 256/ge;
$_;
}

__END__


Rate Map2 Map1 S Subst Vec Pack1 Loop1 Loop2 Pack2
Map2 47.8/s -- -1% -5% -32% -36% -39% -44% -48% -84%
Map1 48.3/s 1% -- -4% -32% -35% -38% -43% -47% -84%
S 50.2/s 5% 4% -- -29% -33% -36% -41% -45% -84%
Subst 70.6/s 48% 46% 41% -- -5% -9% -17% -22% -77%
Vec 74.6/s 56% 54% 49% 6% -- -4% -12% -18% -76%
Pack1 78.0/s 63% 61% 55% 10% 5% -- -8% -14% -75%
Loop1 84.7/s 77% 75% 69% 20% 14% 9% -- -7% -72%
Loop2 91.1/s 91% 89% 81% 29% 22% 17% 7% -- -70%
Pack2 307/s 542% 535% 511% 334% 311% 293% 262% 237% --


Any correction/cmt/etc. welcome!


HTH,
Michele
 
B

Bart Lateur

Michele said:
sub Pack2 {
# Is this OK, BTW?
pack 'L*', map rand ~0, 1..5_000;
}

I don't think you'll ever see "\xFF\xFF\xFF\xFF" there. Better add 1 to
it.
 
M

Michele Dondi

OK, here are the benchmarks of some of the proposed solutions along
with some other idea.

BTW: I'm to say the least in a rush and I could absoultely NOT verify
that my 'Pack2' solution is correct. But in case it is notm then I
guess that it can be easily corrected.

OK, I'm back again and now I have some more time. I done some *quick*
tests on 'Pack2' and[*] it *seems* to work as expected. At least, I
can't see any big misbehaviour...

In the meanwhile I thought that *if* the program will be run only
under Linux (don't know about other unices), then it may read from
/dev/urandom as well. So I added, more out of curiosity than for other
reasons, a sub like

sub Dev1 {
open my $fh, '<', '/dev/urandom' or
die "Can't access `/dev/urandom': $!\n";
local $/ = \20_000;
scalar <$fh>;
}

and I noticed that it was much faster than I had expected, so I also
tested a version

sub Dev2 {
local $/ = \20_000;
scalar <$fh>;
}

that doesn't open() /dev/urandom each time. The speed increase is
noticeable but not impressive. Here are the updated results (omitting
qw/Map1 Map2 S/ solutions from previous post):


Rate Subst Vec Pack1 Loop1 Loop2 Dev1 Dev2 Pack2
Subst 71.0/s -- -3% -9% -18% -24% -73% -73% -78%
Vec 73.2/s 3% -- -6% -15% -21% -72% -73% -77%
Pack1 78.1/s 10% 7% -- -10% -16% -70% -71% -76%
Loop1 86.4/s 22% 18% 11% -- -7% -67% -68% -73%
Loop2 93.1/s 31% 27% 19% 8% -- -64% -65% -71%
Dev1 259/s 265% 254% 232% 200% 178% -- -3% -19%
Dev2 267/s 276% 265% 242% 210% 187% 3% -- -17%
Pack2 321/s 351% 338% 310% 271% 244% 24% 20% --


[*] Apart the naive assumption that ~0 will yield (2**32-1), which in
fact does (here, now!) - but of course it is not reliable in terms of
portability...


Michele
 
T

Tassilo v. Parseval

Also sprach Michele Dondi:
[*] Apart the naive assumption that ~0 will yield (2**32-1), which in
fact does (here, now!) - but of course it is not reliable in terms of
portability...

It's a pretty safe assumption, though, that nowadays integers are at
least 32 bits wide. So you will have to guard against 64-bit machines.
You can force 32 bits by doing C<~0 & Oxffffffff>.

Tassilo
 
M

Michele Dondi

I don't think you'll ever see "\xFF\xFF\xFF\xFF" there. Better add 1 to
it.

Obviously! As I wrote, I was really in a big hurry, so I just put down
what seemed to me the fastest way (in terms of keystrokes/thinkering)
to do it.


Michele
 
B

Bart Lateur

Michele said:
OK, I'm back again and now I have some more time. I done some *quick*
tests on 'Pack2' and[*] it *seems* to work as expected. At least, I
can't see any big misbehaviour...

I can think of a caveat: I seem to recall that at least some random
generators only had 24 significant bits. Now if you plan on using 32, it
won't be completely random. Instead, I expect the lowest byte to always
be the same, or at least, close to the same few values. (taking odd
rounding into account)
 
M

Michele Dondi

[*] Apart the naive assumption that ~0 will yield (2**32-1), which in
fact does (here, now!) - but of course it is not reliable in terms of
portability...

It's a pretty safe assumption, though, that nowadays integers are at
least 32 bits wide. So you will have to guard against 64-bit machines.
You can force 32 bits by doing C<~0 & Oxffffffff>.

But then I would loose the only reason why I used ~0 in the first
place, i.e. to write 2**32 (err, well: not exactly, as it has already
been pointed out!) in just as few keystrokes as possible: and no, no
good reason for golfing but the fact that I *had* to leave home in a
minute or so! (so that even thinking better about it was not an
option! ;-)

Oh, and BTW: if it could have been C<~0 & Oxffffffff>, then it would
have been C<Oxffffffff>! :)


Michele
 
M

Michele Dondi

I can think of a caveat: I seem to recall that at least some random
generators only had 24 significant bits. Now if you plan on using 32, it
won't be completely random. Instead, I expect the lowest byte to always
be the same, or at least, close to the same few values. (taking odd
rounding into account)

Well, as I wrote, this doesn't seem to be the case. At least under
Linux, but then see the "Linux vs. Windows: different behaviour [re
rand()]" thread started anew about this very topic...


Michele
 
M

Michele Dondi

Peter> my $str = "\000" x 20_000;
Peter> my @chr = map { chr $_ } 0 .. 255;
Peter> substr $str, $_, 1, $chr[rand 256] for 1 .. 20_000;
maybe:

pack "C*", map rand 256 for 1 .. 20_000;

If you read my other posts in this thread (those with the benchmarks)
you'll notice that this solution doesn't perform well if compared to a
naive loop of the kind of that used by the OP. But a pack() solution
wins if we pack at four[*] bytes at a time (and in the meanwhile we
discovered that this depends on the RANDBITS compile option).

However it also resulted that map()-versions of the naive loop
solutions were, reasonably, slower than these. So I wondered wether a
solution like 'Loop3' below could perform even better. For ease of
reading I'll repeat my complete test here:


#!/usr/bin/perl

use strict;
use warnings;

use Benchmark qw/:all/;

# For 'Dev2'
open my $fh, '<', '/dev/urandom' or
die "Can't access `/dev/urandom': $!\n";

cmpthese 500, {
Loop1 => \&Loop1,
Loop2 => \&Loop2,
# Map1 => \&Map1,
# Map2 => \&Map2,
# Subst => \&Subst,
Vec => \&Vec,
Pack1 => \&Pack1,
Pack2 => \&Pack2,
# S => \&S,
Dev1 => \&Dev1,
Dev2 => \&Dev2,
Loop3 => \&Loop3 };


sub Loop1 {
my $str = '';
$str .= chr int rand 256 for 1..20_000;
$str;
}

sub Loop2 {
my @chrs = map chr, 0..255;
my $str = '';
$str .= $chrs[rand 256] for 1..20_000;
$str;
}

sub Map1 {
join '', map { chr int rand 256 } 1..20_000;
}

sub Map2 {
my @chrs = map chr, 0..255;
join '', map $chrs[rand 256], 1..20_000;
}

sub Subst {
my $str = "\000" x 20_000;
my @chrs = map chr, 0..255;
substr $str, $_, 1, $chrs[rand 256] for 0..19_999;
$str;
}

sub Vec {
my $str = ' ' x 20000;
vec($str, $_, 8) = rand 256 for 0..19_999;
$str;
}

sub Pack1 {
pack 'C*', map int rand 256, 1..20_000;
}

sub Pack2 {
# Is this OK, BTW?
pack 'L*', map rand ~0, 1..5_000;
}

sub S {
local $_ = ' ' x 20_000;
s/ /chr int rand 256/ge;
$_;
}

sub Dev1 {
open my $fh, '<', '/dev/urandom' or
die "Can't access `/dev/urandom': $!\n";
local $/ = \20_000;
scalar <$fh>;
}

sub Dev2 {
local $/ = \20_000;
scalar <$fh>;
}

sub Loop3 {
my $str = '';
$str .= pack 'L*', rand 2**32 for 1..5_000;
$str;
}

__END__


Results:

Rate Vec Pack1 Loop1 Loop2 Loop3 Dev1 Dev2 Pack2
Vec 74.7/s -- -5% -12% -16% -70% -71% -72% -77%
Pack1 78.7/s 5% -- -7% -11% -68% -70% -71% -75%
Loop1 84.7/s 13% 8% -- -4% -65% -67% -68% -74%
Loop2 88.5/s 18% 12% 4% -- -64% -66% -67% -72%
Loop3 245/s 228% 211% 189% 177% -- -6% -8% -24%
Dev1 260/s 248% 231% 207% 194% 6% -- -3% -19%
Dev2 267/s 258% 240% 216% 202% 9% 3% -- -17%
Pack2 321/s 329% 307% 278% 262% 31% 23% 20% --


So: no, it wasn't a good idea...


[*] Eight on 64-bit CPUs?


Michele
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,769
Messages
2,569,576
Members
45,054
Latest member
LucyCarper

Latest Threads

Top