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).

In reply to Re (tilly) 1: How expensive is reverse? by tilly
in thread How expensive is reverse? by bless$self=>perlmonks;

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.