|Speeding up unshift
may explain what is going on.
Through Perl 5.6.1, unshift left the array aligned on the left. So if you build up an array with unshift's it is forced to realign it on every single unshift. If you build an array with repeated unshifts this makes the cost of each linear, for quadratic total time. What tilly's patch does is realign it indented to the length of the current array. So you only realign after you unshift the length of the array elements. In the simple case of adding one element at a time, this boils down to realigning at powers of 2, for a constant amortized cost.
The code could be more efficient, but there don't seem to be order of magnitude algorithmic improvements left.
Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
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:
You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
- a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, 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, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
Link using PerlMonks shortcuts! What shortcuts can I use for linking?
See Writeup Formatting Tips and other pages linked from there for more info.
| & || & |
| < || < |
| > || > |
| [ || [ |
| ] || ] ||