Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Perl Misc (http://www.velocityreviews.com/forums/f67-perl-misc.html)
-   -   Fast random string generation (http://www.velocityreviews.com/forums/t888669-fast-random-string-generation.html)

Derek Fountain 10-24-2004 03:38 AM

Fast random string generation
 
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...?

Dave Oswald 10-24-2004 04:41 AM

Re: Fast random string generation
 

"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




Ala Qumsieh 10-24-2004 06:37 AM

Re: Fast random string generation
 
Derek Fountain wrote:

> 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


Peter J. Acklam 10-24-2004 12:50 PM

Re: Fast random string generation
 
Derek Fountain <nospam@example.com> wrote:

> 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

--
#!/local/bin/perl5 -wp -*- mode: cperl; coding: iso-8859-1; -*-
# matlab comment stripper (strips comments from Matlab m-files)
s/^((?:(?:[])}\w.]'+|[^'%])+|'[^'\n]*(?:''[^'\n]*)*')*).*/$1/x;

Randal L. Schwartz 10-24-2004 03:00 PM

Re: Fast random string generation
 
>>>>> "Peter" == Peter J Acklam <pjacklam@online.no> writes:

Peter> Derek Fountain <nospam@example.com> wrote:
>> 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...?


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;

--
Randal L. Schwartz - Stonehenge Consulting Services, Inc. - +1 503 777 0095
<merlyn@stonehenge.com> <URL:http://www.stonehenge.com/merlyn/>
Perl/Unix/security consulting, Technical writing, Comedy, etc. etc.
See PerlTraining.Stonehenge.com for onsite and open-enrollment Perl training!

Bart Lateur 10-25-2004 07:42 AM

Re: Fast random string generation
 
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.

--
Bart.

Bart Lateur 10-25-2004 07:51 AM

Re: Fast random string generation
 
Derek Fountain wrote:

>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;

--
Bart.

John W. Kennedy 10-25-2004 02:11 PM

Re: Fast random string generation
 
Bart Lateur wrote:
> 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.

--
John W. Kennedy
"The poor have sometimes objected to being governed badly; the rich have
always objected to being governed at all."
-- G. K. Chesterton. "The Man Who Was Thursday"

Michele Dondi 10-25-2004 02:36 PM

Re: Fast random string generation
 
On Sun, 24 Oct 2004 11:38:30 +0800, Derek Fountain
<nospam@example.com> wrote:

>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
--
{$_=pack'B8'x25,unpack'A8'x32,$a^=sub{pop^pop}->(map substr
(($a||=join'',map--$|x$_,(unpack'w',unpack'u','G^<R<Y]*YB='
..'KYU;*EVH[.FHF2W+#"\Z*5TI/ER<Z`S(G.DZZ9OX0Z')=~/./g)x2,$_,
256),7,249);s/[^\w,]/ /g;$ \=/^J/?$/:"\r";print,redo}#JAPH,

Bart Lateur 10-25-2004 03:02 PM

Re: Fast random string generation
 
Michele Dondi wrote:

> 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.

--
Bart.


All times are GMT. The time now is 07:04 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.