comment on

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;

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


laziness, impatience, and hubris
	PerlMonks