On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
Of course, using repeated #add: is inefficient (#addAll: has a rule
for sorting once or at every #add:).
That's true, but #addAll:'s rule is not generally useful. For example:
| s | s := (1 to: 300000) asSortedCollection. [ s addAll: (1 to: 100000) ] timeToRun ===> 24698
| s | s := (1 to: 300000) asSortedCollection. [ s addAll: (1 to: 100001) ] timeToRun ===> 1124 (+1 element makes a big difference)
why + 1 makes a so big difference?
Because #addAll: has a simple check that doesn't care about the performance of the different methods of addition: addAll: aCollection aCollection size > (self size // 3) ifTrue: [aCollection do: [:each | self addLast: each]. self reSort] ifFalse: [aCollection do: [:each | self add: each]]. ^ aCollection A better check could solve this, but who wants to come up with a formula that's easy to calculate (aka fast) and gives accurate results? Levente
And in squeak: | s | s := (1 to: 300000) asOrderedCollection. [ s addAll: (1 to: 100000); sort ] timeToRun ===> 763 (mergesort beats quicksort)
cool. This is fun to see that during years we pushed so that squeak moves and we got bashed for that and now squeak is moving because of us. At least we succeeded in something.
So the only use-case where SortedCollection is useful (IMO) is when you - have to keep the collection sorted and - you rarely some elements to it
Getting rid of other uses is hard because #asSortedCollection always returns a copy, while most #as* selectors don't.
Levente
If you pick the changes from squeak trunk, Array and OrderedCollection (and SortedCollection) will understand #sort and #sort: and will have the same semantics: sort in place (by a stable sorting algorithm).
Don't open a new issue. There is http://code.google.com/p/pharo/issues/detail?id=1214 http://code.google.com/p/pharo/issues/detail?id=1346
Nicolas
Levente
Stef _______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project