Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

Re: Re: Shift, Pop, Unshift and Push with Impunity!

by Anonymous Monk
on Sep 06, 2002 at 20:56 UTC ( #195776=note: print w/ replies, xml ) Need Help??


in reply to Re: Shift, Pop, Unshift and Push with Impunity!
in thread Shift, Pop, Unshift and Push with Impunity!

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.


Comment on Re: Re: Shift, Pop, Unshift and Push with Impunity!

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://195776]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (6)
As of 2014-07-30 04:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (229 votes), past polls