From: dhesi@rahul.net (Rahul Dhesi)
Subject: Re: randomize.c
Organization: a2i network
Date: Wed, 2 Sep 1992 08:54:15 GMT

In <1992Sep1.210332.26149@netlabs.com> lwall@netlabs.com (Larry Wall) writes:

>This one's weird enough that you might be able
>to beat splice by copying the actual strings like you did.  As it happens,
>on a sparc the splice wins by about 20%.

Taking this advice, I went ahead and tried it!  I ran my benchmarks on
a SPARCstation-1+ with 64 megs of main memory.  In addition to
"ize.copy" (my original perl version, which copies lines) and "splice"
(splice version, from camel book p20), I also tried "ize.ind", which
only copies integers, at the cost of an extra level of indirection for
subscripting.

This turned out to be quite a bit of fun.

     program     no. of data lines     real time, min:sec
     -------     ----------            ------------------
     ize.copy      1,914               0:01.42
     ize.ind       1,914               0:01.35
     splice        1,914               0:01.06
     ize.copy     78,474               0:53
     ize.ind      78,474               1:01
     splice       78,474               6:51

For typical uses (small amount of input), there isn't much difference.
For atypical uses (e.g., randomizing 40 csh manuals), the traditional
array method wins over splice.

Session transcript follows, and then sources for each program.

===== begin edited session log =====
% ls -F
ize.copy*  ize.ind*   splice*
% man csh | col -b > small.data
% repeat 40 cat small.data >> big.data
% wc -l *.data
   76560 big.data
    1914 small.data
   78474 total
% time ize.copy < small.data > junk
1.1u 0.2s 0:01.41 97.1% 0+430k 3+12io 0pf+0w
% time ize.ind < small.data > junk
1.1u 0.2s 0:01.36 101.4% 0+468k 0+12io 0pf+0w
% time splice < small.data > junk
0.8u 0.2s 0:01.06 102.8% 0+422k 0+8io 0pf+0w
% time ize.copy < small.data > junk
1.1u 0.2s 0:01.35 101.4% 0+429k 0+9io 0pf+0w
% time ize.ind < small.data > junk
1.1u 0.2s 0:01.34 101.4% 0+469k 0+9io 0pf+0w
% time splice < small.data > junk
0.8u 0.2s 0:01.06 102.8% 0+420k 0+9io 0pf+0w
% time ize.copy < big.data > junk
43.3u 8.5s 0:52.76 98.2% 0+8217k 1+363io 0pf+0w
% time ize.ind < big.data > junk
42.8u 17.5s 1:01.76 97.8% 0+10278k 2+361io 0pf+0w
% time splice < big.data > junk
379.8u 14.9s 6:52.05 95.7% 0+8861k 3+384io 0pf+0w
% time ize.copy < big.data > junk
43.1u 8.8s 0:52.94 98.2% 0+8179k 7+362io 0pf+0w
% time ize.ind < big.data > junk
42.9u 15.5s 0:59.25 98.7% 0+10226k 4+362io 0pf+0w
% time splice < big.data > junk
379.4u 12.5s 6:51.03 95.3% 0+8853k 10+385io 0pf+0w

===== begin ize.copy =====
#! /usr/bin/perl
# Copy input lines output in random order.  R. Dhesi 1992/08/29.
@lines = <STDIN>;
$limit = $#lines;
$first = 0;
srand;

while ($first <= $limit) {
   $r = rand($limit - $first) + $first;
   print $lines[$r];
   $lines[$r] = $lines[$first++];
}
===== begin ize.ind =====
#! /usr/bin/perl
# Copy input lines output in random order.  R. Dhesi 1992/09/02.
@lines = <STDIN>;
$limit = $#lines;
@ind  = (0 .. $limit);	# indirect indexes
$first = 0;
srand;

while ($first <= $limit) {
   $r = rand($limit - $first) + $first;
   print $lines[$ind[$r]];
   $ind[$r] = $first++;
}
===== begin splice =====
#! /usr/bin/perl
# from camel book p20
srand;
@lines=<>;
while (@lines) {
   print splice(@lines, rand @lines, 1);
}
===== end =====
--
Rahul Dhesi <dhesi@rahul.net>
also:  dhesi@cirrus.com
Newsgroups: comp.lang.perl