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 }, } );
|
---|
Replies are listed 'Best First'. | |
---|---|
Re^3: Linked lists as arrays: inserting values
by shmem (Chancellor) on Sep 25, 2006 at 23:01 UTC | |
Re^3: Linked lists as arrays: inserting values
by ikegami (Patriarch) on Sep 25, 2006 at 23:37 UTC |