On Mon, Oct 18, 2010 at 1:02 PM, Stéphane Ducasse <[email protected] > 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 > > [email protected] > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > > _______________________________________________ > > Pharo-project mailing list > > [email protected] > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > _______________________________________________ > Pharo-project mailing list > [email protected] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >
_______________________________________________ Pharo-project mailing list [email protected] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
