Stack should be reimplemented with Array
Locked
12
12
 
|
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.
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 [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Stack.st (2K)
Re: Stack should be reimplemented with Array
|
|
2010/10/14 jaayer <[hidden email]> 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.
_______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
|
|
In reply to this post by jaayer
The original contains an error; it send min: where it should max:. This one contains the correction.
_______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
|
|
In reply to this post by Eliot Miranda-2
---- 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 [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
In reply to this post by jaayer
Thanks!!!
Stef On Oct 14, 2010, at 8:32 PM, jaayer wrote: > The original contains an error; it send min: where it should max:. This one contains the correction.<Stack.st>_______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
BTW, why Stack inherits from LinkedList instead of just using it? Should an Stack have the entire Collection protocol? I don't think so...
On Thu, Oct 14, 2010 at 5:31 PM, Stéphane Ducasse <[hidden email]> wrote: Thanks!!! _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
|
|
In reply to this post by jaayer
On closer inspection, it appears the main reason why Stack is faster than OrderedCollection is that OrderedCollection will reallocate its Array even when #new: is supplied with what should be the correct size. To prevent reallocation, one must actually give it 1.5 times the size needed. This is because OrderedCollection keeps the first one-third of its Array empty so that #addFirst: operations will not require O(n) copying. This means that creating an OrderedCollection with new: 10 will require reallocation when the eighth element is added. If you create an OrderedCollection 50% bigger than what you expect to need, the performance gap closes to about ~7%, which isn't very significant:
Smalltalk garbageCollect. r1 :=[100000 timesRepeat: [ s := Stack new: 100. 100 timesRepeat: [s push: #foo]]] timeToRun. Smalltalk garbageCollect. r2 := [100000 timesRepeat: [ oc := OrderedCollection new: 150. 100 timesRepeat: [oc addLast: #foo]]] timeToRun. _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
|
|
In reply to this post by Guillermo Polito
---- On Fri, 15 Oct 2010 07:41:24 -0700 Guillermo Polito wrote ---- >BTW, why Stack inherits from LinkedList instead of just using it? Should an Stack have the entire Collection protocol? I don't think so... That was the subject of the earlier discussion, and yes, I think it should implement all appropriate messages in Collection, including #add: (as #push:), #size and #do:. The Array-based Stack I wrote does not implement #remove:ifAbsent: and only supports removal at the top of the Stack through #pop. _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
In reply to this post by Eliot Miranda-2
On Thu, 14 Oct 2010, Eliot Miranda wrote:
> 2010/10/14 jaayer <[hidden email]> > >> 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've never seen any code using Stack. People are more familiar with OrderedCollection. The O(1) worst case time for push is true in theory, but if we take into account GCs and cache locality, then things are a lot worse. GC pauses caused by the allocation of link objects are longer and happen more often than the pause caused by array growing (though it may also cause GC pauses). An array based implementation has much better cache locality: related object pointers (push/pop) are next to each other and 4x more pointers fit in same amount of cache. There are no speedups that could be applied to OrderedCollection in the code. The code implements a stack which is like an OrderedColelction with a few extra constraints: - firstIndex is always 1 - you can only add to the end - you can only remove from the end The implementation relies on these constraints. That's what makes it faster than an OrderedCollection. Levente > > >> >> 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 >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
In reply to this post by jaayer
On Thu, 14 Oct 2010, jaayer wrote:
> 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. > > 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). Please write more realistic benchmarks. Adding 10 elements to your Stack implementation won't make it's array grow. Also the benchmark measures a lot of other stuff besides the cost of push and pop. Something like this should do it: "The linked Stack implementation" (1 to: 5) collect: [ :run | | stack | Smalltalk garbageCollect. stack := Stack new. { [ 1 to: 1000000 do: [ :each | stack push: each ] ] timeToRun. [ 1 to: 1000000 do: [ :each | stack pop ] ] timeToRun } ] #(#(167 88) #(169 91) #(169 88) #(166 87) #(166 88)) "OrderedCollection" (1 to: 5) collect: [ :run | | stack | Smalltalk garbageCollect. stack := OrderedCollection new. { [ 1 to: 1000000 do: [ :each | stack addLast: each ] ] timeToRun. [ 1 to: 1000000 do: [ :each | stack removeLast ] ] timeToRun } ] #(#(87 98) #(87 100) #(87 98) #(88 97) #(87 99)) "The new stack implementation" (1 to: 5) collect: [ :run | | stack | Smalltalk garbageCollect. stack := Stack new. { [ 1 to: 1000000 do: [ :each | stack push: each ] ] timeToRun. [ 1 to: 1000000 do: [ :each | stack pop ] ] timeToRun } ] #(#(89 62) #(90 63) #(89 62) #(89 62) #(89 64)) All benchmarks were run in the latest Squeak 4.2 alpha using the latest CogVM. Conclusion: OrderedCollection >> #removeLast uses #emptyCheck which is slow. Other than that the difference between OrderedCollection and an array-based stack implementation is neglible in Squeak using CogVM. Replacing self emptyCheck with lastIndex < firstIndex ifTrue: [ self errorEmptyCollection] in OrderedCollection >> #removeLast and running the benchmark again gives the following results: #(#(88 65) #(90 66) #(89 66) #(88 68) #(87 66)) Also please send #postCopy to super if you implement #postCopy. Levente _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
In reply to this post by jaayer
thanks levente!
this is always nice to read such kind of post since they educate us and we need that :) I want to be taught a lot :) Stef On Oct 15, 2010, at 6:33 PM, Levente Uzonyi wrote: > On Thu, 14 Oct 2010, jaayer wrote: > >> 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. >> >> 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). > > Please write more realistic benchmarks. Adding 10 elements to your Stack implementation won't make it's array grow. Also the benchmark measures a lot of other stuff besides the cost of push and pop. Something like this should do it: > > "The linked Stack implementation" > (1 to: 5) collect: [ :run | > | stack | > Smalltalk garbageCollect. > stack := Stack new. > { > [ 1 to: 1000000 do: [ :each | stack push: each ] ] timeToRun. > [ 1 to: 1000000 do: [ :each | stack pop ] ] timeToRun } ] > #(#(167 88) #(169 91) #(169 88) #(166 87) #(166 88)) > > "OrderedCollection" > (1 to: 5) collect: [ :run | > | stack | > Smalltalk garbageCollect. > stack := OrderedCollection new. > { > [ 1 to: 1000000 do: [ :each | stack addLast: each ] ] timeToRun. > [ 1 to: 1000000 do: [ :each | stack removeLast ] ] timeToRun } ] > #(#(87 98) #(87 100) #(87 98) #(88 97) #(87 99)) > > "The new stack implementation" > (1 to: 5) collect: [ :run | > | stack | > Smalltalk garbageCollect. > stack := Stack new. > { > [ 1 to: 1000000 do: [ :each | stack push: each ] ] timeToRun. > [ 1 to: 1000000 do: [ :each | stack pop ] ] timeToRun } ] > #(#(89 62) #(90 63) #(89 62) #(89 62) #(89 64)) > > All benchmarks were run in the latest Squeak 4.2 alpha using the latest CogVM. > > Conclusion: OrderedCollection >> #removeLast uses #emptyCheck which is slow. Other than that the difference between OrderedCollection and an array-based stack implementation is neglible in Squeak using CogVM. > > Replacing > self emptyCheck > with > lastIndex < firstIndex ifTrue: [ self errorEmptyCollection] > in OrderedCollection >> #removeLast and running the benchmark again gives the following results: > #(#(88 65) #(90 66) #(89 66) #(88 68) #(87 66)) > > > Also please send #postCopy to super if you implement #postCopy. > > > Levente > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
In reply to this post by jaayer
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 > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
On Mon, Oct 18, 2010 at 1:02 PM, Stéphane Ducasse <[hidden email]> wrote: Eliot No. The VM doesn't know anything about Stack.
_______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
Stephane, i could say more:
- i don't like how LinkedList implemented. I don't see why it should mimic things like #at: #at:put: at all.. IMO this protocol should be pruned from it, to not provoke uses which completely do not fit for given data structure. Removing/inserting into the middle of list is quite ineffective operation (O(n)), while inserting at the begginning/end of list is O(1). Lists are sequenceable.. but sequenceable ~~ indexable. Period. -- Best regards, Igor Stasenko AKA sig. _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
On Mon, 18 Oct 2010, Igor Stasenko wrote:
> Stephane, i could say more: > - i don't like how LinkedList implemented. > > I don't see why it should mimic things like #at: #at:put: at all.. It's not mimicing those methods. A list usually support things like this, but the user should know the consequences. > IMO this protocol should be pruned from it, to not provoke uses which > completely do not fit for given data structure. I'm not sure if it's okay to remove features, because users lacking really basic CS knowledge may use them the wrong way. > > Removing/inserting into the middle of list is quite ineffective > operation (O(n)), As long as you don't give away the link objects, it's O(n), otherwise it can be O(1). > while inserting at the begginning/end of list is O(1). > > Lists are sequenceable.. but sequenceable ~~ indexable. Period. Sequenceable is indexable, but good performance is not guaranteed. Levente > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
On 19 October 2010 00:25, Levente Uzonyi <[hidden email]> wrote:
> On Mon, 18 Oct 2010, Igor Stasenko wrote: > >> Stephane, i could say more: >> - i don't like how LinkedList implemented. >> >> I don't see why it should mimic things like #at: #at:put: at all.. > > It's not mimicing those methods. A list usually support things like this, > but the user should know the consequences. > The consequences of such approach is much more far-reaching: leads to bad design practices, crappy application performance, and then tons of bugs and workarounds. >> IMO this protocol should be pruned from it, to not provoke uses which >> completely do not fit for given data structure. > > I'm not sure if it's okay to remove features, because users lacking really > basic CS knowledge may use them the wrong way. > Imo, we should prohibit this from the beginning. Standard, core classes should not contain an API, which could lead to careless, abusive programming techniques. IMO, a kernel APIs should serve not only as an implementation of basic system funcionality, it also must serve as guide, how to best use these facilities, so people will learn what is the right way to use it. We should teach users to use right tools for things they need. >> >> Removing/inserting into the middle of list is quite ineffective >> operation (O(n)), > > As long as you don't give away the link objects, it's O(n), otherwise it can > be O(1). giving away link objects... oh, that's the worst thing, which could possibly happen :) > >> while inserting at the begginning/end of list is O(1). >> >> Lists are sequenceable.. but sequenceable ~~ indexable. Period. > > Sequenceable is indexable, but good performance is not guaranteed. > Unless you representing an infinite collection(s). Streams are good example of sequenceable, however non-indexable containers. > > Levente > >> >> -- >> Best regards, >> Igor Stasenko AKA sig. >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig. _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
On Tue, 19 Oct 2010, Igor Stasenko wrote:
> On 19 October 2010 00:25, Levente Uzonyi <[hidden email]> wrote: >> On Mon, 18 Oct 2010, Igor Stasenko wrote: >> >>> Stephane, i could say more: >>> - i don't like how LinkedList implemented. >>> >>> I don't see why it should mimic things like #at: #at:put: at all.. >> >> It's not mimicing those methods. A list usually support things like this, >> but the user should know the consequences. >> > > The consequences of such approach is much more far-reaching: leads to > bad design practices, crappy application performance, > and then tons of bugs and workarounds. Are programmers idiots? If not, then we shouldn't treat them like idiots. > >>> IMO this protocol should be pruned from it, to not provoke uses which >>> completely do not fit for given data structure. >> >> I'm not sure if it's okay to remove features, because users lacking really >> basic CS knowledge may use them the wrong way. >> > > Imo, we should prohibit this from the beginning. Standard, core > classes should not contain an API, which could lead to > careless, abusive programming techniques. So we should get rid of SortedCollection, remove #includes: #indexOf: from ArrayedCollections, get rid of OrderedCollection >> #remove:, etc. Am I right? > IMO, a kernel APIs should serve not only as an implementation of basic > system funcionality, it also must serve as guide, > how to best use these facilities, so people will learn what is the > right way to use it. That's right, but there's no need to remove useful features to achieve this. > > We should teach users to use right tools for things they need. > > >>> >>> Removing/inserting into the middle of list is quite ineffective >>> operation (O(n)), >> >> As long as you don't give away the link objects, it's O(n), otherwise it can >> be O(1). > > giving away link objects... oh, that's the worst thing, which could > possibly happen :) No. It's the user's responsibility to use it wisely. If you don't need to access a internal nodes, just adding/removing elements to/from the list, then you probably shouldn't use a list at all. > >> >>> while inserting at the begginning/end of list is O(1). >>> >>> Lists are sequenceable.. but sequenceable ~~ indexable. Period. >> >> Sequenceable is indexable, but good performance is not guaranteed. >> > Unless you representing an infinite collection(s). > Streams are good example of sequenceable, however non-indexable containers. Streams are more like external iterators, than containers IMHO. But you can get/set the position of most streams. Levente > > >> >> Levente >> >>> >>> -- >>> Best regards, >>> Igor Stasenko AKA sig. >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> [hidden email] >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
On 19 October 2010 02:51, Levente Uzonyi <[hidden email]> wrote:
> On Tue, 19 Oct 2010, Igor Stasenko wrote: > >> On 19 October 2010 00:25, Levente Uzonyi <[hidden email]> wrote: >>> >>> On Mon, 18 Oct 2010, Igor Stasenko wrote: >>> >>>> Stephane, i could say more: >>>> - i don't like how LinkedList implemented. >>>> >>>> I don't see why it should mimic things like #at: #at:put: at all.. >>> >>> It's not mimicing those methods. A list usually support things like this, >>> but the user should know the consequences. >>> >> >> The consequences of such approach is much more far-reaching: leads to >> bad design practices, crappy application performance, >> and then tons of bugs and workarounds. > > Are programmers idiots? If not, then we shouldn't treat them like idiots. > And that's why as non-idiot (i hope), i was wondering, what things like #at: #at:put: doing in classes like Stack, or LikedList. You know, its like you driving the car and along the road you see a beatiful park with pool and attractions for the kids to play to the right side, and a toxic waste dump to the left side of road.. And you keep driving, thinking about a diner and wife, which waits you at home, but at some moment your attention gets back to that place and you have a gut feeling that there was something wrong with a picture you just seen, and then you got it: they are close to each other, just across the road! >> >>>> IMO this protocol should be pruned from it, to not provoke uses which >>>> completely do not fit for given data structure. >>> >>> I'm not sure if it's okay to remove features, because users lacking >>> really >>> basic CS knowledge may use them the wrong way. >>> >> >> Imo, we should prohibit this from the beginning. Standard, core >> classes should not contain an API, which could lead to >> careless, abusive programming techniques. > > So we should get rid of SortedCollection, remove #includes: #indexOf: from > ArrayedCollections, get rid of OrderedCollection >> #remove:, etc. Am I > right? > And should be handled in a way like Array>>add: does. >> IMO, a kernel APIs should serve not only as an implementation of basic >> system funcionality, it also must serve as guide, >> how to best use these facilities, so people will learn what is the >> right way to use it. > > That's right, but there's no need to remove useful features to achieve this. > you should convince me first, that things like LinkedList>>at: is userful. >> >> We should teach users to use right tools for things they need. >> >> >>>> >>>> Removing/inserting into the middle of list is quite ineffective >>>> operation (O(n)), >>> >>> As long as you don't give away the link objects, it's O(n), otherwise it >>> can >>> be O(1). >> >> giving away link objects... oh, that's the worst thing, which could >> possibly happen :) > > No. It's the user's responsibility to use it wisely. If you don't need to > access a internal nodes, just adding/removing elements to/from the list, > then you probably shouldn't use a list at all. > I prefer making own lists and own classes for list items, because implementation of LinkedList raising many questions starting from being optimal, and up to concerns i presented above. >> >>> >>>> while inserting at the begginning/end of list is O(1). >>>> >>>> Lists are sequenceable.. but sequenceable ~~ indexable. Period. >>> >>> Sequenceable is indexable, but good performance is not guaranteed. >>> >> Unless you representing an infinite collection(s). >> Streams are good example of sequenceable, however non-indexable >> containers. > > Streams are more like external iterators, than containers IMHO. But you can > get/set the position of most streams. > > > Levente > >> >> >>> >>> Levente >>> >>>> >>>> -- >>>> Best regards, >>>> Igor Stasenko AKA sig. >>>> >>>> _______________________________________________ >>>> Pharo-project mailing list >>>> [hidden email] >>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>> >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> [hidden email] >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> >> >> -- >> Best regards, >> Igor Stasenko AKA sig. >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > -- Best regards, Igor Stasenko AKA sig. _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
On Tue, 19 Oct 2010, Igor Stasenko wrote:
> On 19 October 2010 02:51, Levente Uzonyi <[hidden email]> wrote: >> On Tue, 19 Oct 2010, Igor Stasenko wrote: >> >>> On 19 October 2010 00:25, Levente Uzonyi <[hidden email]> wrote: >>>> >>>> On Mon, 18 Oct 2010, Igor Stasenko wrote: >>>> >>>>> Stephane, i could say more: >>>>> - i don't like how LinkedList implemented. >>>>> >>>>> I don't see why it should mimic things like #at: #at:put: at all.. >>>> >>>> It's not mimicing those methods. A list usually support things like this, >>>> but the user should know the consequences. >>>> >>> >>> The consequences of such approach is much more far-reaching: leads to >>> bad design practices, crappy application performance, >>> and then tons of bugs and workarounds. >> >> Are programmers idiots? If not, then we shouldn't treat them like idiots. >> > No, of course not. > And that's why as non-idiot (i hope), i was wondering, what things > like #at: #at:put: doing in classes like Stack, > or LikedList. Okay, it's not nice if a Stack allows indexing, but most linked list implementations support it. > You know, its like you driving the car and along the road you see a > beatiful park with pool and attractions for the kids to play to the > right side, and a toxic waste dump to the left side of road.. And you > keep driving, thinking about a diner and wife, which waits you at > home, but at some moment your attention gets back to that place and > you have a gut feeling that there was something wrong with a picture > you just seen, and then you got it: they are close to each other, just > across the road! > >>> >>>>> IMO this protocol should be pruned from it, to not provoke uses which >>>>> completely do not fit for given data structure. >>>> >>>> I'm not sure if it's okay to remove features, because users lacking >>>> really >>>> basic CS knowledge may use them the wrong way. >>>> >>> >>> Imo, we should prohibit this from the beginning. Standard, core >>> classes should not contain an API, which could lead to >>> careless, abusive programming techniques. >> >> So we should get rid of SortedCollection, remove #includes: #indexOf: from >> ArrayedCollections, get rid of OrderedCollection >> #remove:, etc. Am I >> right? >> > Roughly speaking, yes. But they are inherited.. this is a little another story. > And should be handled in a way like Array>>add: does. Array >> #add: is different, because Arrays are not resizable. You could say that one could use #become: to grow the array, but then I'd say that following your suggestions we have to remove #become: from the system, because it's slow and people may use it to write slow code. > >>> IMO, a kernel APIs should serve not only as an implementation of basic >>> system funcionality, it also must serve as guide, >>> how to best use these facilities, so people will learn what is the >>> right way to use it. >> >> That's right, but there's no need to remove useful features to achieve this. >> > you should convince me first, that things like LinkedList>>at: is userful. Ok. Here's an example: What happens if you remove OrderedCollection >> #remove: from the system? People will write code like this (or worse): gotIt := false. 1 to: o size do: [ :index | gotIt ifTrue: [ o at: index - 1 put: (o at: index) ] ifFalse: [ (o at: index) = myObject ifTrue: [ gotIt := true ] ]. gotIt ifTrue: [ o removeLast ]. This kind of code is a lot worse than using #remove:, because it's harder to understand, harder to debug, really easy to mess up. And it will be reimplemented several times. Levente > >>> >>> We should teach users to use right tools for things they need. >>> >>> >>>>> >>>>> Removing/inserting into the middle of list is quite ineffective >>>>> operation (O(n)), >>>> >>>> As long as you don't give away the link objects, it's O(n), otherwise it >>>> can >>>> be O(1). >>> >>> giving away link objects... oh, that's the worst thing, which could >>> possibly happen :) >> >> No. It's the user's responsibility to use it wisely. If you don't need to >> access a internal nodes, just adding/removing elements to/from the list, >> then you probably shouldn't use a list at all. >> > > I prefer making own lists and own classes for list items, because > implementation of > LinkedList raising many questions starting from being optimal, and up > to concerns i presented above. > > >>> >>>> >>>>> while inserting at the begginning/end of list is O(1). >>>>> >>>>> Lists are sequenceable.. but sequenceable ~~ indexable. Period. >>>> >>>> Sequenceable is indexable, but good performance is not guaranteed. >>>> >>> Unless you representing an infinite collection(s). >>> Streams are good example of sequenceable, however non-indexable >>> containers. >> >> Streams are more like external iterators, than containers IMHO. But you can >> get/set the position of most streams. >> >> >> Levente >> >>> >>> >>>> >>>> Levente >>>> >>>>> >>>>> -- >>>>> Best regards, >>>>> Igor Stasenko AKA sig. >>>>> >>>>> _______________________________________________ >>>>> Pharo-project mailing list >>>>> [hidden email] >>>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>>> >>>> >>>> _______________________________________________ >>>> Pharo-project mailing list >>>> [hidden email] >>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>>> >>> >>> >>> >>> -- >>> Best regards, >>> Igor Stasenko AKA sig. >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> [hidden email] >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> _______________________________________________ >> Pharo-project mailing list >> [hidden email] >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Stack should be reimplemented with Array
|
|
In reply to this post by Eliot Miranda-2
one point at a time :)
I'm talking about stack :) On Oct 18, 2010, at 10:49 PM, Igor Stasenko wrote: > Stephane, i could say more: > - i don't like how LinkedList implemented. > > I don't see why it should mimic things like #at: #at:put: at all.. > IMO this protocol should be pruned from it, to not provoke uses which > completely do not fit for given data structure. > > Removing/inserting into the middle of list is quite ineffective > operation (O(n)), > while inserting at the begginning/end of list is O(1). > > Lists are sequenceable.. but sequenceable ~~ indexable. Period. > > -- > Best regards, > Igor Stasenko AKA sig. > > _______________________________________________ > Pharo-project mailing list > [hidden email] > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
«
Return to Pharo Smalltalk Developers
|
1 view|%1 views
| Free forum by Nabble | Edit this page |