Beefy Boxes and Bandwidth Generously Provided by pair Networks
Welcome to the Monastery
 
PerlMonks  

Re: Linked lists as arrays: inserting values

by shmem (Canon)
on Sep 25, 2006 at 16:27 UTC ( #574779=note: print w/ replies, xml ) Need Help??


in reply to 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];

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

_($_=" "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 (Parson) 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% --

    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:

      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

      _($_=" "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}

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

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://574779]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (14)
As of 2015-07-31 12:21 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (277 votes), past polls