How expensive is reverse?

bless$self=>perlmonks; has asked for the wisdom of the Perl Monks concerning the following question:

How expensive is it to reverse an array? Is it an O(1) or O(n) operation? Or something else?

Anyone want to give a quick overview of how arrays and strings are implemented in Perl? What data structures, etc.?

Comment on How expensive is reverse?

Replies are listed 'Best First'.
Re: How expensive is reverse? by maverick (Curate) on Sep 01, 2001 at 21:35 UTC
I'm not sure how they are implemented or what the (O) is (I suspect it's O(n)). Here's what a quick benchmark says from my Dual Celeron 400: `#!/usr/bin/perl use Benchmark; @one = ('a' x 100); @two = ('a' x 1000); @three = ('a' x 10000); timethese( 100000, { 'rev 100' => sub { reverse @one }, 'rev 1000' => sub { reverse @two }, 'rev 10000' => sub { reverse @three }, } );` [download] Gives me this: `Benchmark: timing 100000 iterations of rev 100, rev 1000, rev 10000... rev 100: 1 wallclock secs ( 0.24 usr + 0.00 sys = 0.24 CPU) @ 41 +6666.67/s (n=100000) (warning: too few iterations for a reliable count) rev 1000: 1 wallclock secs ( 0.87 usr + 0.00 sys = 0.87 CPU) @ 11 +4942.53/s (n=100000) rev 10000: 8 wallclock secs ( 7.65 usr + 0.00 sys = 7.65 CPU) @ 13 +071.90/s (n=100000)` [download] At a 100,000 iterations of a 1,000 element list, it took 0.87 seconds of CPU time. Not too expensive I'd say. Updated CRAP! nardo is quite right. I hate it when I make silly mistakes. /\/\averick perl -l -e "eval pack('h*','072796e6470272f2c5f2c5166756279636b672');"	[reply] [d/l] [select]
Re: Re: How expensive is reverse? by nardo (Friar) on Sep 01, 2001 at 22:08 UTC
ITYM `@one = (('a') x 100); @two = (('a') x 1000); @three = (('a') x 10000);` [download] As it is written each array has one element 100, 1000, or 10000 characters long rather than having 100, 1000, or 10000 elements one character long. With this change (and changing it to run 10,000 times) I get: `Benchmark: timing 10000 iterations of rev 100, rev 1000, rev 10000... rev 100: 0 wallclock secs ( 0.54 usr + -0.01 sys = 0.53 CPU) @ 18 +867.92/s (n=10000) rev 1000: 4 wallclock secs ( 5.52 usr + -0.01 sys = 5.51 CPU) @ 18 +14.88/s (n=10000) rev 10000: 59 wallclock secs (58.33 usr + -0.00 sys = 58.33 CPU) @ 17 +1.44/s (n=10000)` [download]	[reply] [d/l] [select]
Re: How expensive is reverse? by tachyon (Chancellor) on Sep 01, 2001 at 22:14 UTC
Anyone want to give a quick overview of how arrays and strings are implemented in Perl? What data structures, etc? All the gory details are here perlman:perlguts. It's all in C to me. As well as this you can always RTFS - if you're into that sort of masochism - as the Perl source code is freely available :-) cheers tachyon s&&rsenoyhcatreve&&&s&n.+t&"$'$`$\"$\&"&ee&&y&srve&&d&&print	[reply]
Re (tilly) 1: How expensive is reverse? by tilly (Archbishop) on Sep 03, 2001 at 04:57 UTC
Reversing an array is O(n), but you are just reversing an array of pointers so the size of the data in the array does not enter into it. Some of the information you want about Perl's internal structure is at Shift, Pop, Unshift and Push with Impunity!. When Perl 5.8 comes out building a list with unshift will be relatively efficient as well. By and large Perl's data structures are implemented with buffered allocation for efficiency. What I mean by that is that an array has a contiguous block of space allocated for it, but the allocation is done in powers of 2 so that there is some buffer at the end. When you add to it, as long as it fits in the existing space, it just goes there. When you want to remove from it, it just marks the end as being a little shorter. What this does is waste some space, but if you go to build up a large array or string incrementally (eg using push or .=) the amortized cost per increment is O(1) and the overall allocation overhead winds up being O(n).	[reply]

Back to Seekers of Perl Wisdom