perl function complexity

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Is there a good reference out there describing the complexity (run-time, space) of various Perl builtin functions and data structures? In particular, I'm wondering about shift, unshift, push, pop, substr, split, and join as well as the typical space requirements (per key or element) for perl arrays and hashes.

Comment on perl function complexity

Replies are listed 'Best First'.
Re: perl function complexity by xdg (Monsignor) on Feb 08, 2007 at 22:38 UTC
Good starting points are perlguts and Perl Guts Illustrated. -xdg Code written by xdg and posted on PerlMonks is public domain. It is provided as is with no warranties, express or implied, of any kind. Posted code may not have been tested. Use of posted code is at your own risk.	[reply]
Re: perl function complexity by GrandFather (Saint) on Feb 08, 2007 at 22:56 UTC
Discussion of these issues have been aired in the past. You might like to take a look at some of: Linked lists as arrays: inserting values, To push and pop or not to push and pop? and Shift, Pop, Unshift and Push with Impunity!. DWIM is Perl's answer to Gödel	[reply]
Re: perl function complexity by kyle (Abbot) on Feb 08, 2007 at 22:36 UTC
You can measure the size of a given data structure using Devel::Size.	[reply]
Re: perl function complexity by ikegami (Patriarch) on Feb 08, 2007 at 22:51 UTC
`splice` operations that add/remove leading/trailing elements to/from arrays are very fast. They do not copy the array. That means they have a O(N) run time, where N is the number of elements added/removed. Same goes for the shortcuts `shift`, `unshift`, `push` and `pop`. Or so I was told.	[reply] [d/l] [select]