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? > > > 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
