Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^2: Linked lists as arrays: inserting values

by Not_a_Number (Parson)
on Sep 25, 2006 at 20:25 UTC ( #574821=note: print w/ replies, xml ) Need Help??


in reply to Re: Linked lists as arrays: inserting values
in thread Linked lists as arrays: inserting values

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:

use strict; use warnings; use Benchmark 'cmpthese'; my ( $START, $END ) = @ARGV >= 2 ? @ARGV : ( 5000, 6000 ); my $SIZE = $ARGV[2] ? $ARGV[2] : 10000; die "Bad input!\n" if $START > $END or $END > $SIZE; my $TIMES = int 10_000_000 / $SIZE / 2; print "Array size: $SIZE\n"; print "Inserting: $START .. $END\n"; sub insert1 { my ( $ra, $index, $elem ) = @_; @$ra = @$ra[0 ..$ index-1], $elem, @$ra[$index .. @$ra-1]; } sub insert2 { my ( $ra, $index, $elem ) = @_; splice( @$ra, $index, 0, $elem ); } cmpthese ( $TIMES, { radiant => sub { my @ary = 1 .. $SIZE; insert1( \@ary, 1, $_ ) for $START .. $END }, splicing => sub { my @ary = 1 .. $SIZE; insert2( \@ary, 1 ,$_ ) for $START .. $END }, } );


Comment on Re^2: Linked lists as arrays: inserting values
Select or Download Code
Re^3: Linked lists as arrays: inserting values
by shmem (Canon) 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% --

    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}
Re^3: Linked lists as arrays: inserting values
by ikegami (Pope) 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% --

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (18)
As of 2014-07-25 16:45 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (174 votes), past polls