[Pharo-project] Stack should be reimplemented with Array

Eliot Miranda eliot.miranda at gmail.com
Mon Oct 18 16:34:36 EDT 2010


On Mon, Oct 18, 2010 at 1:02 PM, Stéphane Ducasse <stephane.ducasse at inria.fr
> wrote:

> Eliot
>
> > There was a post on this list back in August complaining about Stack
> inheriting from LinkedList. There was some discussion, but apparently no
> resolution, as Stack still inherits from LinkedList in the Pharo 1.2 Core
> Image I just downloaded. Rather than reimplementing it to forward to a
> contained LinkedList, I think it should use an Array internally like
> OrderedCollection does. An Array-based implementation of Stack would be
> faster than one based on LinkedList due to the basic stack operations (push,
> pop and top) being able to rely more on primitives. This assumes that you
> know roughly how a big a stack you need; if you don't, reallocating the
> array and copying its contents over and over again will cost you, but this
> is an exceptional case;-- most stacks are small and when they aren't, the
> programmer usually has enough information to select a reasonable stack size.
> >
> > *No*.  Stack and OrderedCollection differ *usefully*.  Adding an item to
> a Stack is always O(1).  Adding an item to an OrderedCollection is O(N)
> because when the array overflows a new one must be allocated and the old
> objects copied to the new.  Why not apply your speedups to
> OrderedCollection, or is that not possible?  If not possible, then come up
> with a new name and add that.  Please /don't/ change Stack.
>
> I would really like not having Stack inheriting from LinkedList (I hate
> subclassing). Now from a VM point of view
> is there a constraint that Stack as to be a subclass of LList?
>

No.  The VM doesn't know anything about Stack.


>
>
> >
> >
> > Enclosed is a fileout of an Array-based Stack implementation. It trounces
> the LinkedList-based implementation easily, but more interestingly, it
> performs better than an OrderedCollection when used like a stack:
> >
> > Pushing is roughly ~30% faster:
> > r1 :=[100000 timesRepeat: [
> >                s := Stack new.
> >                10 timesRepeat: [s push: #foo]]] timeToRun.
> > r2 := [100000 timesRepeat: [
> >                oc := OrderedCollection new.
> >                10 timesRepeat: [oc addLast: #foo]]] timeToRun.
> > 100 - ((r1 / r2) asFloat * 100).
> >
> > as is pushing + popping:
> > r3 := [100000 timesRepeat: [
> >                s := Stack new.
> >                10 timesRepeat: [s push: #foo].
> >                10 timesRepeat: [s pop]]] timeToRun.
> > r4 := [100000 timesRepeat: [
> >                oc := OrderedCollection new.
> >                10 timesRepeat: [oc addLast: #foo].
> >                10 timesRepeat: [oc removeLast]]] timeToRun.
> > 100 - ((r3 / r4) asFloat * 100).
> > _______________________________________________
> > Pharo-project mailing list
> > Pharo-project at lists.gforge.inria.fr
> > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
> >
> > _______________________________________________
> > Pharo-project mailing list
> > Pharo-project at lists.gforge.inria.fr
> > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>
>
> _______________________________________________
> Pharo-project mailing list
> Pharo-project at lists.gforge.inria.fr
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.pharo.org/pipermail/pharo-dev_lists.pharo.org/attachments/20101018/4d6a620c/attachment-0001.html>


More information about the Pharo-dev mailing list