|
Posted by xhoster on March 22, 2008, 7:59 pm
Please log in for more thread options
> I have always imagined arrays in Perl as contiguous stretches
> of elements (pointers, or annotated pointers) in ram.
> And push and pop as adding and removing from the right side,
> without affecting more than one element.
>
> Whereas I imagine shift and unshift as moving the whole
> lot of them left and right. Which would make unshift and shift
> considerably less efficient, time-wise, than push and pop.
>
> Is that true?
The internal data structure allows for buffered space on each end which
means moving/allocating has to take place much less often than on every
push/unshift. However, the space seems to be either more generous or
handled more efficiently for push/pop than shift/unshift, making them
slightly faster (on my version of Perl, on my system, etc.)
On the other hand, running ltrace on simple push loops shows that "memmove"
is called on very push or unshift. I suspect some of these memmoves are
degenerate do-nothings, but since I can't figure out how to map the 5
arguments that ltrace reports to the 3 arguments that memmove takes, I
can't figure out exactly what is happening.
Any way, the empirical time differences seem to be negligible.
> When modeling a stack, if there's a choice,
> is using push and pop always preferable to using unshift and shift?
> (For that reason, or any other?)
If modeling a simple LIFO stack, push and pop are preferable. That is
because "push" and "pop" are the words normally associated with LIFO
stacks.
Xho
--
-------------------- http://NewsReader.Com/ --------------------
The costs of publication of this article were defrayed in part by the
payment of page charges. This article must therefore be hereby marked
advertisement in accordance with 18 U.S.C. Section 1734 solely to indicate
this fact.
| 
XML Sitemap