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