Re: Linked lists as arrays: inserting values

[shmem]

Benchmarking your code (insert_array_elem1)against the same code using splice (insert_array_elem2), changing the line

    @$ra = @$ra[0..$index-1], $elem, @$ra[$index..@$ra-1];

with

    splice(@$ra,$index,0,$elem);

and using

cmpthese (5000, {
    radiantmatrix => sub { my $array = [1..1000]; insert_array_elem1($
+array,1,$_) for 50..100 },
    use_splice => sub { my $array = [1..1000]; insert_array_elem2($arr
+ay,1,$_) for 50..100 },
});

results in

                Rate radiantmatrix    use_splice
radiantmatrix  467/s            --          -83%
use_splice    2762/s          492%            --

radiantmatrix - use_splice :-)

--shmem

[Not_a_Number]

Update: Ignore this post (mistakes pointed out by shmem and ikegami below.

Perhaps I'm doing something wrong, but my benchmarking results are radically different from shmem's.

For a start, with the same data (programme run several times), I get something like this:

           Rate splicing  radiant
splicing 2371/s       --     -19%
radiant  2936/s      24%       --

This is not the first time that I have got very different benchmarking results than other Monks on this forum, but this time the difference is particularly egregious.

In case you're wondering:

C:\Perl\progs>perl -v
This is perl, v5.8.8 built for MSWin32-x86-multi-thread
<snip>
Binary build 817 provided by ActiveState

And the bigger the original array gets (and the greater the number of elements to insert), the more radiantmatrix's code appears to outperform splice:

C:\Perl\progs>scratchpad.pl 6000 7000 10000
Array size: 10000
Inserting: 6000 .. 7000
           Rate splicing  radiant
splicing 28.1/s       --     -86%
radiant   198/s     603%       --

C:\Perl\progs>scratchpad.pl 60000 61000 100000
Array size: 100000
Inserting: 60000 .. 61000
           Rate splicing  radiant
splicing 2.87/s       --     -93%
radiant  42.7/s    1388%       --

Perhaps I've got something very very wrong, but my findings seem to be borne out by this extract from Mastering algorithms with Perl, Chapter 3:

...splicing elements into or out of the middle of a large array can be very expensive.

Here's my benchmarking code, demolish it at will:

Read more... (1017 Bytes)

[shmem]

Running your code on my Linux box, I get:

qwurx [shmem] ~> perl 574821.pl 6000 7000 10000
Array size: 10000
Inserting: 6000 .. 7000
           Rate splicing  radiant
splicing 46.8/s       --     -66%
radiant   137/s     193%       --

You are inserting a number between 6000 and 7000 at index 1, in every call to insert1 and insert2.

# called as insert1( \@ary, 1, $_ ) for $START .. $END
sub insert1 {
  my ( $ra, $index, $elem ) = @_;
  @$ra = @$ra[0 .. $index-1], $elem, @$ra[$index .. @$ra-1];
}
# I tested with 
sub insert1 {
  my ( $ra, $elem, $index ) = @_;
  @$ra = @$ra[0 .. $index-1], $elem, @$ra[$index .. @$ra-1];
}
# called as insert1( \@ary, 1, $_ ) for $START .. $END

If I swap $elem and $index (i.e. insert 1 at an index from $START to $END) I get:

qwurx [shmem] ~> perl 574821.pl 600 700 1000 
Array size: 1000
Inserting: 600 .. 700
           Rate  radiant splicing
radiant  30.5/s       --     -98%
splicing 1672/s    5377%       --

The insert somewhere in the middle is more expensive, that's why $_/10 for @params here.

My perl:

$ perl -v
This is perl, v5.8.8 built for i586-linux-thread-multi
...

--shmem

[ikegami]

Here's my benchmarking code, demolish it at will:

First rule of Benchmarking, make sure the code you are benchmarking actually works!

@$ra = @$ra[0 ..$ index-1], $elem, @$ra[$index .. @$ra-1];
means
(@$ra = @$ra[0 ..$ index-1]), $elem, @$ra[$index .. @$ra-1];
You want
@$ra = ( @$ra[0 ..$ index-1], $elem, @$ra[$index .. @$ra-1] );

Also, your arguments are backwards:
insert1( \@ary, 1, $_ ) for $START .. $END
insert2( \@ary, 1 ,$_ ) for $START .. $END
should be
insert1( \@ary, $_, 1 ) for $START .. $END
insert2( \@ary ,$_, 1 ) for $START .. $END

Once fixed (and setting the loop count to -3 cause it was taking forever):

>perl 574845.pl 500 600 1000
Array size: 1000
Inserting: 500 .. 600
           Rate  radiant splicing
radiant  17.3/s       --     -99%
splicing 1470/s    8392%       --