Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
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.


In reply to Re: Re: Shift, Pop, Unshift and Push with Impunity! by Anonymous Monk
in thread Shift, Pop, Unshift and Push with Impunity! by lhoward

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!
  • 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, 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
  • Outside of code tags, you may need to use entities for some characters:
            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.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others rifling through the Monastery: (5)
    As of 2014-09-22 05:11 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (178 votes), past polls