On 3/6/07, John W. Krahn <[EMAIL PROTECTED]> wrote:
Gary wrote:
snip
> I'm curious about how much time it takes to do something like insert into the
> middle ofan array. Is that O(1)?
Yes.
$ perl -le'
my @array = 0 .. 20;
print "@array";
splice @array, 10, 0, "X", "Y", "Z";
print "@array";
'
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 1 2 3 4 5 6 7 8 9 X Y Z 10 11 12 13 14 15 16 17 18 19 20
snip
Splice is not 0(1). I believe it is 0(k+m) when k is < n/2 and 0(n-k,
m) when k >= n/2 where n is the size of the target array, k is the
offset, and m is the size of the list or array to insert. That is if
I didn't screw up the logic. In plainer words, the length of time it
takes is dependent upon the number of array elements it must move plus
the size of the number of elements it must copy in. Since a Perl
array can grow in both directions splices near the front or end are
less expensive than slices near the middle.
Here is the output of a benchmark that splices a 0 into the middle of
the array and then uses splice to remove the 0 again.
10: 0 wallclock secs ( 1.04 usr + 0.00 sys = 1.04 CPU) @
827076.92/s (n=860160)
100: 0 wallclock secs ( 1.00 usr + 0.00 sys = 1.00 CPU) @
724345.00/s (n=724345)
1000: 0 wallclock secs ( 1.07 usr + 0.00 sys = 1.07 CPU) @
338478.50/s (n=362172)
10000: 1 wallclock secs ( 1.05 usr + 0.00 sys = 1.05 CPU) @
54613.33/s (n=57344)
100000: 1 wallclock secs ( 1.08 usr + 0.00 sys = 1.08 CPU) @
5530.56/s (n=5973)
1000000: 1 wallclock secs ( 1.06 usr + 0.00 sys = 1.06 CPU) @
225.47/s (n=239)
Here is the benchmark I used. You can play around with $k (the
offset) to see it's role.
#!/usr/bin/perl
use strict;
use Benchmark;
my @max = (10, 100, 1_000, 10_000, 100_000, 1_000_000);
my %arrays;
for my $max (@max) {
$arrays{$max} = [ 1 .. $max ];
}
my %these;
for my $max (@max) {
my $mid = int $max/2;
$these{$max} = sub {
#add a zero into the middle of the array
splice @{$arrays{$max}}, $mid, 0, 0;
#remove the zero from the middle of the array
splice @{$arrays{$max}}, $mid, 1;
};
};
timethese(-1, \%these);
--
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
http://learn.perl.org/
