---- On Thu, 14 Oct 2010 10:51:31 -0700 Eliot Miranda wrote ----
>*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.
Yes, that point was made in the prior discussion regarding Stack and its
superclass in defense of having such a class at all when OrderedCollection is
already there. Further, you are correct that I am suggesting we trade
guaranteed O(1) complexity when pushing/popping for worst-case O(n) complexity.
However, asymptotic analysis does not the whole story tell, as it ignores the
underlying constants, and in the real world, when n is small enough, the
constants *do* matter. As it turns out, "small enough" in this case means a
Stack created with the default initial capacity of 10 grown incrementally into
one big enough to hold 500,000-1,000,000 elements.
I ran the following benchmark with both versions, and the array-based Stack was
~60% faster when grown big enough to contain 100,000 elements, slightly faster
for 500,000 elements, and two to three times slower for a million elements:
s := nil.
Smalltalk garbageCollect.
[s := Stack new.
100000 timesRepeat: [s push: #foo]] timeToRun.
s := nil.
Smalltalk garbageCollect.
[s := Stack new.
500000 timesRepeat: [s push: #foo]] timeToRun.
s := nil.
Smalltalk garbageCollect.
[s := Stack new.
1000000 timesRepeat: [s push: #foo]] timeToRun.
That means that even if you unknowingly create an enormous Stack without
specifying the right size, you still come out ahead for at least the first
500,000 elements. Of course, the Array-based stack never deallocates any of its
memory, which means a worst case of 2 * n memory complexity (where n is the
largest number of elements a given Stack ever held). But as I said in my
initial post, most Stacks are small, and when they aren't, you often have
enough information to choose an appropriate size. If you really need constant
time and memory complexity, which I argue is the exception, why not just use
LinkedList directly with #addLast: and #removeLast to simulate a Stack as
people did and still do with OrderedCollection? The rueful requirement that
LinkList elements inherit from Link is gone.
Stack, if it is to exist at all, should support *fast* push and pop operations.
The current implementation does not. This one does, and should replace it.
_______________________________________________
Pharo-project mailing list
[email protected]
http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
