Re: Linked lists as arrays: inserting values

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];
[download]

with

    splice(@$ra,$index,0,$elem);
[download]

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 },
});
[download]

results in

                Rate radiantmatrix    use_splice
radiantmatrix  467/s            --          -83%
use_splice    2762/s          492%            --
[download]

radiantmatrix - use_splice :-)

--shmem

_($_=" "x(1<<5)."?\n".q·/)Oo.  G°\        /
                              /\_¯/(q    /
----------------------------  \__(m.====·.(_("always off the crowd"))."·
");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}

Comment on Re: Linked lists as arrays: inserting values Select or Download Code

Replies are listed 'Best First'.
Re^2: Linked lists as arrays: inserting values by Not_a_Number (Prior) on Sep 25, 2006 at 20:25 UTC
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% --` [download] 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` [download] 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% --` [download] `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% --` [download] 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)	[reply] [d/l] [select]
Re^3: Linked lists as arrays: inserting values by shmem (Chancellor) on Sep 25, 2006 at 23:01 UTC
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% --` [download] 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` [download] 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% --` [download] 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 ...` [download] --shmem _($_=" "x(1<<5)."?\n".q·/)Oo. G°\ / /\_¯/(q / ---------------------------- \__(m.====·.(_("always off the crowd"))."· ");sub _{s./.($e="'Itrs `mnsgdq Gdbj O`qkdq")=~y/"-y/#-z/;$e.e && print}	[reply] [d/l] [select]
Re^3: Linked lists as arrays: inserting values by ikegami (Patriarch) on Sep 25, 2006 at 23:37 UTC
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% --` [download]	[reply] [d/l] [select]