On Thu, Mar 13, 2008 at 9:02 AM, Jenda Krynicky <[EMAIL PROTECTED]> wrote:
snip
> right
> @a = (pop(@a), @a);
>
> left
> @a = (@a[1..$#a], $a[0]);
snip
These are O(n) operations and are fine if n is small, but the push/shift and
unshift/pop implementations are O(1). Of course, the push/shift and
unshift/pop versions are destructive, so you may need to use these if you
aren't assigning back to the same array (which would be O(n) anyway so there
wouldn't be a noticeable performance hit).
test with ten elements
left_push_shift [2] [3] [4] [5] [6] [7] [8] [9] [1]
left_slice [2] [3] [4] [5] [6] [7] [8] [9] [1]
right_slice [9] [1] [2] [3] [4] [5] [6] [7] [8]
right_unshift_pop [9] [1] [2] [3] [4] [5] [6] [7] [8]
results for n of 10
Rate left_slice right_slice right_unshift_pop
left_push_shift
left_slice 297890/s -- -36% -92%
-93%
right_slice 463698/s 56% -- -87%
-89%
right_unshift_pop 3574691/s 1100% 671% --
-13%
left_push_shift 4111294/s 1280% 787% 15%
--
results for n of 100
Rate left_slice right_slice right_unshift_pop
left_push_shift
left_slice 36885/s -- -34% -99%
-99%
right_slice 55854/s 51% -- -98%
-99%
right_unshift_pop 3300471/s 8848% 5809% --
-22%
left_push_shift 4249037/s 11420% 7507% 29%
--
results for n of 1000
Rate left_slice right_slice right_unshift_pop
left_push_shift
left_slice 3459/s -- -37% -100%
-100%
right_slice 5493/s 59% -- -100%
-100%
right_unshift_pop 3247802/s 93806% 59024% --
-14%
left_push_shift 3780922/s 109221% 68729% 16%
--
results for n of 10000
Rate left_slice right_slice right_unshift_pop
left_push_shift
left_slice 352/s -- -38% -100%
-100%
right_slice 565/s 61% -- -100%
-100%
right_unshift_pop 3276799/s 931108% 580055% --
-13%
left_push_shift 3776122/s 1073007% 668459% 15%
--
#!/usr/bin/perl
use strict;
use warnings;
use Benchmark;
my @a;
my %subs = (
left_push_shift => sub { push @a, shift @a; return 0 },
left_slice => sub { @a = (@a[1..$#a], $a[0]); return 0 },
right_unshift_pop => sub { unshift @a, pop @a; return 0 },
right_slice => sub { @a = (pop @a, @a); return 0 },
);
print "test with ten elements\n";
for my $sub (sort keys %subs) {
@a = 1 .. 9;
$subs{$sub}->();
printf "%-20s %s\n", $sub, join " ", map {"[$_]"} @a;
}
for my $n (10, 100, 1_000, 10_000) {
@a = 1 .. $n;
print "results for n of $n\n";
Benchmark::cmpthese(-1, \%subs);
}
--
Chas. Owens
wonkden.net
The most important skill a programmer can have is the ability to read.
