Fwd: sort: and sortBlock:
Locked
1234
1234
Re: Fwd: sort: and sortBlock:
 
|
On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
> > On Dec 23, 2009, at 6:09 PM, Levente Uzonyi wrote: > >> On Wed, 23 Dec 2009, Adrian Kuhn wrote: >> >>> Stéphane Ducasse <stephane.ducasse@...> writes: >> >>>>> I started to implement OrderedSet (OrderedCollection no duplicate) >> but I think that I want probably UniqueOrdered. >> I will publish what I have done and ask for feedback and that other can >>>>> improve. I like the idea of using the TraitsTest to have coherent sets of >>>>> behavior. > > Oh yeah, TreeSet ftw, missed that already sometime! >>> what is TreeSet? >> >> The common data structure to implement ordered sets. Which one do you use? >> >> >> IMO ordered sets (where ordering means the same as in OrderedCollection) should be implemented with a hashtable of linked elements. > > Why not an OrderedCollection? removal from sets/dictionaries is rare in smalltalk. Of course this means that the cost of accessing an element by index is O(n) instead of O(1), but I wouldn't expect a set to be indexable even if it's "ordered". Levente > if we mean UniqueOrderedCollection > For an OrderedSet I imagine that this is because you want a constant access to elements (which happend to be ordered)? > Stef > _______________________________________________ > 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: Fwd: sort: and sortBlock:
|
|
In reply to this post by Stéphane Ducasse
On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
>>> >> >> What bugs me is that #sortBy: does not what it says. I would expect that >> >> aCollection sortBy: [ :each | each name ] >> >> does the same as >> >> aCollection sort: [ :a :b | a name <= b name ] >> >> if you want that, I can provide a fast implementation of #sortBy: >> >> >> Not all collections are sortable and #sort: is sorting in-place, so it's hardly doable. > > But it would be nice to have sort: and sortBlock: polymorph. > Because right now we cannot have OrderedCollection and Array or SortedCollection interchanged. used for sorting which is a misuse of this data structure (I wonder why such data strucure exists at all, it's almost never useful). 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). Levente > > Stef > _______________________________________________ > 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: Fwd: sort: and sortBlock:
|
|
In reply to this post by Julian Fitzell-2
> #sortBlock: is defined by ANSI on SortedCollection as an accessor and
> an instance creation method. That's what it sounds like and shouldn't > be implemented on non-sorted collections. Why? what would be the reason not to use sortBlock: for others? I like this consortium design that neglects basic polymorphism. May be in the future ANSI 1996 will look so old that we will be done with it. > #asSortedCollection is defined by ANSI on Collection and returns an > instance of SortedCollection. Yes it makes sense. > #sort and #sort: -- Squeak/Pharo have it on ArrayedCollection, VW has > it on SequenceableCollection, and VASt will now add it. This sorts the > instance in place. I think that collection hierarchy shows the little of single inheritance and this is normal. Of course Interval is Sequenceable but I imagine cannot be sorted in place. Still some leaves like OrderedCollection could be really polymorphic. Now we would have it on OrderedCollection too and the subclasses of Sequenceable which make sense. > #sorted, #sorted: -- VW already has this. VA is adding it. What is sorted? a boolean predicate method? What a bad name. Did they forgot Kent? I remember this cool period where moose stopped to work because sort was changed. They introduced that in VW and broke all our code by changing the sort: semantics. Now I checked and here is what I read SequenceableCollection>>sorted: aBlock "Return a sorted copy of the receiver using aBlock as the sort criteria. e.g. #(1 4 -5 -2 3) sorted: [:a :b | a abs <= b abs] returns a sorted copy of the receiver as #(1 -2 3 4 -5)" SequenceableCollection>>sorted "Return a sorted copy of the receiver." SequenceableCollection>>sort "Sort the receiver in place." Which clearly does not work on subclasses, of course. (1 to: -100 by: 3 ) sorted: [:a :b | a abs <= b abs] Why they did not use sortBlock: and sort: ? So we have conceptually sortInPlace: -> does not copy sort: -> does not do a copy as in pharo/squeak and VW and both could use sortBlock: (accessor and instance creation for SortedCollection) sort "Sort the receiver in place." > Squeak/Pharo should add it, IMO, but we'll add it to Grease if not. It > returns a sorted copy of SequenceableCollections and a sorted Array of > all other collections. Please not this is bogus. It does not work with certain subclasses of Sequenceable And much more important it has a bad name. Because with a nice name sortCopy then it would be much better. So with one method in VW you can get it sortCopy ^ self sorted > #sortBy: is silly, as you mention and not supported on any other > platform. We're adding it to our lint rules as a "do not use" method. Yes. I would discard it. > We didn't notice #asSortedArray but I think that's a terrible name -- > the pattern with #as* methods is that the thing after the "as" should > be a class. That behaviour could be easily achieved with "aCollection > sorted asArray" or "aCollection asArray sort" if really needed. Yes we could probably remove them. > So that's what VASt/Seaside/Grease are doing... I encourage you to > follow our lead. :) :) yes but you can also avoid to propagate bad names in the community and sorted is a bad one. Because collections are not functional style as point in smalltalk so I have no clue to know if I get a new object or not. > > Julian > > _______________________________________________ > 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 |
|
|
In reply to this post by Levente Uzonyi-2
Levente Uzonyi <leves@...> writes:
> > what is TreeSet? > > The common data structure to implement ordered sets. Which one do you use? > > IMO ordered sets (where ordering means the same as in OrderedCollection) > should be implemented with a hashtable of linked elements. You're right. I confused ordered and sorted. --AA _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Fwd: sort: and sortBlock:
|
|
In reply to this post by Levente Uzonyi-2
On Dec 23, 2009, at 6:43 PM, Levente Uzonyi wrote: > On Wed, 23 Dec 2009, Stéphane Ducasse wrote: > >>>> >>> >>> What bugs me is that #sortBy: does not what it says. I would expect that >>> >>> aCollection sortBy: [ :each | each name ] >>> >>> does the same as >>> >>> aCollection sort: [ :a :b | a name <= b name ] >>> >>> if you want that, I can provide a fast implementation of #sortBy: >>> >>> >>> Not all collections are sortable and #sort: is sorting in-place, so it's hardly doable. >> >> But it would be nice to have sort: and sortBlock: polymorph. >> Because right now we cannot have OrderedCollection and Array or SortedCollection interchanged. > > SortedCollection should be used as rarely as possible. In the past it was used for sorting which is a misuse of this data structure (I wonder why such data strucure exists at all, it's almost never useful). Indeed I understand that now. sort is much better bette because it is orthogonal to the datastructure > 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). Ok I will have a look. > > > Levente > >> >> Stef >> _______________________________________________ >> 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: Fwd: sort: and sortBlock:
|
|
In reply to this post by Adrian Kuhn
2009/12/23 Adrian Kuhn <[hidden email]>:
> Levente Uzonyi <leves@...> writes: > >> > what is TreeSet? >> >> The common data structure to implement ordered sets. Which one do you use? >> >> IMO ordered sets (where ordering means the same as in OrderedCollection) >> should be implemented with a hashtable of linked elements. That's probably why Stephane proposed a UniqueOrderedCollection: he must have the expectation that this collection can be indexed in O(1) Nicolas > > You're right. > > I confused ordered and sorted. > > --AA > > > _______________________________________________ > 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 |
|
|
In reply to this post by Adrian Kuhn
I just would like to point out that English plus the use of some [of their] overloaded words may create havoc in a discussion.
TreeSets would be a common data structure to implement *sorted* sets in Smalltalk parlance. Although /ordered/ and /sorted/ may be synonyms in lay English, in Smalltalk the use of "Ordered" in the Collection classes has to the property of being indexable and sequenceable which other languages will call the behaviour of "random access". just my 0.0199999.... Em 23/12/2009 14:34, Adrian Kuhn < [hidden email] > escreveu: Stéphane Ducasse writes: > >> I started to implement OrderedSet (OrderedCollection no duplicate) > >> but I think that I want probably UniqueOrdered. > >> I will publish what I have done and ask for feedback and that other can > >> improve. I like the idea of using the TraitsTest to have coherent sets of > >> behavior. > > > > Oh yeah, TreeSet ftw, missed that already sometime! > > what is TreeSet? The common data structure to implement ordered sets. Which one do you use? --AA _______________________________________________ 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: Fwd: sort: and sortBlock:
|
|
In reply to this post by Levente Uzonyi-2
2009/12/23 Levente Uzonyi <[hidden email]>:
> On Wed, 23 Dec 2009, Stéphane Ducasse wrote: > >>>> >>> >>> What bugs me is that #sortBy: does not what it says. I would expect that >>> >>> aCollection sortBy: [ :each | each name ] >>> >>> does the same as >>> >>> aCollection sort: [ :a :b | a name <= b name ] >>> >>> if you want that, I can provide a fast implementation of #sortBy: >>> >>> >>> Not all collections are sortable and #sort: is sorting in-place, so it's >>> hardly doable. >> >> But it would be nice to have sort: and sortBlock: polymorph. >> Because right now we cannot have OrderedCollection and Array or >> SortedCollection interchanged. > > SortedCollection should be used as rarely as possible. In the past it was > used for sorting which is a misuse of this data structure (I wonder why such > data strucure exists at all, it's almost never useful). > The only case should be to keep collection automatically sorted when its contents further evolves... Of course, using repeated #add: is inefficient (#addAll: has a rule for sorting once or at every #add:). > 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 >> [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: Fwd: sort: and sortBlock:
|
|
In reply to this post by Nicolas Cellier
>
> That's probably why Stephane proposed a UniqueOrderedCollection: he > must have the expectation that this collection can be indexed in O(1) Not really :) I was more looking at the user perspective. You often want an orderedCollection (add:) vs Array at: but which deals with duplicate as a Set. I will rename it because OrderedSet is not a good name because this is not a Set. Now this is boring because this is not an OrderedCollection (or you do not have to be forced to implement insert:after:..... I really see that the collection classes suffers from single inheritance and sometimes are too fat. A Nilish collection would be a fun exercise. May be we should start and get a cool OOPSLA paper out of that. Stef _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Fwd: sort: and sortBlock:
|
|
In reply to this post by Nicolas Cellier
Let me know if we can integrate them and we will.
Stef >> > > 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 > _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Fwd: sort: and sortBlock:
|
|
In reply to this post by Julian Fitzell-2
2009/12/23 Julian Fitzell <[hidden email]>:
> On Wed, Dec 23, 2009 at 1:45 AM, Nicolas Cellier > <[hidden email]> wrote: >> 2009/12/23 Stéphane Ducasse <[hidden email]>: >>> Apparently sort: is not understood by SortedCollection :( >>> And sortBlock: is not understood by ArrayedCollection subclasses :( >>> So this is cool OrderedCollection does not understand sort: >>> >>> Could we dare to fix that? Does anybody have a solution? >>> >>> Stef >>> >>> ArrayedCollection>>sort: aSortBlock >>> "Sort this array using aSortBlock. The block should take two arguments >>> and return true if the first element should preceed the second one." >>> >>> self >>> mergeSortFrom: 1 >>> to: self size >>> by: aSortBlock >>> >>> >>> SortedCollection>>sortBlock: aBlock >>> "Answer an instance of me such that its elements are sorted according to >>> the criterion specified in aBlock." >>> >>> ^(super new: 10) sortBlock: aBlock >>> >>> >> >> Oh that one bugs me... >> You also have >> >> asSortedArray >> asSortedCollection >> asSortedCollection: >> sortBy: >> >> A bit too many selectors? >> >> The different semantics currently are: >> - sort in place - #sort and #sort: >> - make a sorted copy - #asSortedArray does except if already >> isMemberOf: Array and isSorted, #sortBy: does too but is only >> understood by SequenceableCollection (stupid) >> - make a sorted collection that can further sort added elements - >> #asSortedCollection #asSortedCollection: >> #sortBlock: has 2 semantics: instance creation and modifying the sort >> block of an instance... >> >> And I would like another message to avoid all these keys asArray sort >> I spreaded in trunk: >> - sort in place if possible (if Sequenceable), or create a sorted >> sequence otherwise >> But you can understand I did not dare adding a new selector :) > > Funnily I just spent last week with John O'Keefe looking at > non-VASt-compatible protocol that Seaside uses, comparing it across > platforms, and pondering which pieces to include tests for in Grease > and which to stop using in Seaside. (by the way, he was happy to add a > whole bunch of "useful" protocol to their base image, which is great > news). I need to write a summary of everything we came up with as well > over the holidays, but in the meantime, here's what we came up with > around sorting: > > #sortBlock: is defined by ANSI on SortedCollection as an accessor and > an instance creation method. That's what it sounds like and shouldn't > be implemented on non-sorted collections. > > > #asSortedCollection is defined by ANSI on Collection and returns an > instance of SortedCollection. > > > #sort and #sort: -- Squeak/Pharo have it on ArrayedCollection, VW has > it on SequenceableCollection, and VASt will now add it. This sorts the > instance in place. > > > #sorted, #sorted: -- VW already has this. VA is adding it. > Squeak/Pharo should add it, IMO, but we'll add it to Grease if not. It > returns a sorted copy of SequenceableCollections and a sorted Array of > all other collections. > Oh, that's exactly the one I would have chosen :) We should go for it, both Squeak and Pharo. > > #sortBy: is silly, as you mention and not supported on any other > platform. We're adding it to our lint rules as a "do not use" method. > And in the future, change semantic as a filter before sorting like proposed here... > > We didn't notice #asSortedArray but I think that's a terrible name -- > the pattern with #as* methods is that the thing after the "as" should > be a class. That behaviour could be easily achieved with "aCollection > sorted asArray" or "aCollection asArray sort" if really needed. > > > So that's what VASt/Seaside/Grease are doing... I encourage you to > follow our lead. :) > > Julian > > _______________________________________________ > 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: Fwd: sort: and sortBlock:
|
|
In reply to this post by Nicolas Cellier
levente
I compared in Squeak Arrayed ... sort: nil mergeFirst: first middle: middle last: last into: dst by: aBlock ... [ (i1 <= middle) and: [ i2 <= last ] ] whileTrue: [ (aBlock ifNil: [ val1 <= val2 ] ifNotNil: [ aBlock value: val1 value: val2 ]) ifTrue: [ dst at: (out := out + 1) put: val1. val1 := self at: (i1 := i1 + 1)] ifFalse: [ dst at: (out := out + 1) put: val2. (i2 := i2 + 1) <= last ifTrue: [ val2 := self at: i2 ] ] ]. ... in pharo Arrayed ... sort: [:a :b | a <= b] mergeFirst: first middle: middle last: last into: dst by: aBlock ... [(i1 <= middle) and: [i2 <= last]] whileTrue: [(aBlock value: val1 value: val2) ifTrue: [dst at: (out := out + 1) put: val1. val1 := self at: (i1 := i1 + 1)] ifFalse: [dst at: (out := out + 1) put: val2. i2 := i2 + 1. i2 <= last ifTrue: [val2 := self at: i2]]]. what is the best? Stef _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Fwd: sort: and sortBlock:
|
|
In reply to this post by Nicolas Cellier
>>> #sorted, #sorted: -- VW already has this. VA is adding it. >> Squeak/Pharo should add it, IMO, but we'll add it to Grease if not. It >> returns a sorted copy of SequenceableCollections and a sorted Array of >> all other collections. >> > > Oh, that's exactly the one I would have chosen :) > We should go for it, both Squeak and Pharo. Fun I always hated it may be because the change broke our code. Stef _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Fwd: sort: and sortBlock:
|
|
In reply to this post by Nicolas Cellier
On Wed, 23 Dec 2009, Nicolas Cellier wrote:
> 2009/12/23 Levente Uzonyi <[hidden email]>: >> On Wed, 23 Dec 2009, Stéphane Ducasse wrote: >> >>>>> >>>> >>>> What bugs me is that #sortBy: does not what it says. I would expect that >>>> >>>> aCollection sortBy: [ :each | each name ] >>>> >>>> does the same as >>>> >>>> aCollection sort: [ :a :b | a name <= b name ] >>>> >>>> if you want that, I can provide a fast implementation of #sortBy: >>>> >>>> >>>> Not all collections are sortable and #sort: is sorting in-place, so it's >>>> hardly doable. >>> >>> But it would be nice to have sort: and sortBlock: polymorph. >>> Because right now we cannot have OrderedCollection and Array or >>> SortedCollection interchanged. >> >> SortedCollection should be used as rarely as possible. In the past it was >> used for sorting which is a misuse of this data structure (I wonder why such >> data strucure exists at all, it's almost never useful). >> > > The only case should be to keep collection automatically sorted when > its contents further evolves... > 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) And in squeak: | s | s := (1 to: 300000) asOrderedCollection. [ s addAll: (1 to: 100000); sort ] timeToRun ===> 763 (mergesort beats quicksort) 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 >>> [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 > Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
|
|
In reply to this post by Stéphane Ducasse
:-D when even the ANSI standard has a sort of "multiple inheritance" diagram to explain its collection hierarchy, you see this suffering is lingering for a long time behaving as some Lost characters. . .!
<warning> all the possible puns intended by the author or to be discovered by more careful reading are there to be enjoyed and are not accidental1 </warning> Well, now that nanotraits and a figment to have something like a mixin in Squeak/Pharo is around the corner, who knows??!! -- Cesar Rabak Em 23/12/2009 16:28, Stéphane Ducasse < [hidden email] > escreveu: > > That's probably why Stephane proposed a UniqueOrderedCollection: he > must have the expectation that this collection can be indexed in O(1) Not really :) I was more looking at the user perspective. You often want an orderedCollection (add:) vs Array at: but which deals with duplicate as a Set. I will rename it because OrderedSet is not a good name because this is not a Set. Now this is boring because this is not an OrderedCollection (or you do not have to be forced to implement insert:after:..... I really see that the collection classes suffers from single inheritance and sometimes are too fat. A Nilish collection would be a fun exercise. May be we should start and get a cool OOPSLA paper out of that. Stef _______________________________________________ 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: Fwd: sort: and sortBlock:
|
|
In reply to this post by Stéphane Ducasse
On Wed, 23 Dec 2009, Stéphane Ducasse wrote:
> levente > > I compared > > in Squeak > > Arrayed > ... > sort: nil > > > > mergeFirst: first middle: middle last: last into: dst by: aBlock > > ... > [ (i1 <= middle) and: [ i2 <= last ] ] whileTrue: [ > (aBlock > ifNil: [ val1 <= val2 ] > ifNotNil: [ aBlock value: val1 value: val2 ]) > ifTrue: [ > dst at: (out := out + 1) put: val1. > val1 := self at: (i1 := i1 + 1)] > ifFalse: [ > dst at: (out := out + 1) put: val2. > (i2 := i2 + 1) <= last ifTrue: [ > val2 := self at: i2 ] ] ]. > ... > > in pharo > > Arrayed > ... > sort: [:a :b | a <= b] > > > mergeFirst: first middle: middle last: last into: dst by: aBlock > ... > [(i1 <= middle) and: [i2 <= last]] whileTrue: > [(aBlock value: val1 value: val2) > ifTrue: [dst at: (out := out + 1) put: val1. > val1 := self at: (i1 := i1 + 1)] > ifFalse: [dst at: (out := out + 1) put: val2. > i2 := i2 + 1. > i2 <= last ifTrue: [val2 := self at: i2]]]. > > > what is the best? This gives the best performance if you're sorting by <= which is the default. Levente > > Stef > > > _______________________________________________ > 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: Fwd: sort: and sortBlock:
|
|
In reply to this post by Levente Uzonyi-2
> 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? > 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 >>>> [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 > _______________________________________________ > 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: Fwd: sort: and sortBlock:
|
|
In reply to this post by Levente Uzonyi-2
>> mergeFirst: first middle: middle last: last into: dst by: aBlock
>> >> ... >> [ (i1 <= middle) and: [ i2 <= last ] ] whileTrue: [ >> (aBlock >> ifNil: [ val1 <= val2 ] >> ifNotNil: [ aBlock value: val1 value: val2 ]) >> ifTrue: [ >> dst at: (out := out + 1) put: val1. >> val1 := self at: (i1 := i1 + 1)] >> ifFalse: [ >> dst at: (out := out + 1) put: val2. >> (i2 := i2 + 1) <= last ifTrue: [ >> val2 := self at: i2 ] ] ]. >> ... > > It's a hack, I took it from SortedCollection's quicksort implementation. This gives the best performance if you're sorting by <= which is the default. Thanks for the explanation. _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
|
|
In reply to this post by Levente Uzonyi-2
Levente Uzonyi <leves@...> writes:
> > It's a hack, I took it from SortedCollection's quicksort implementation. This > > gives the best performance if you're sorting by <= which is the default. Shouldn't `sort` do what `sort: nil` does? A simple `aBlock ifNil: [ ^self sort ]` might be more intention revealing (of course assumed that `sort` implements a #<= based sort :) --AA _______________________________________________ Pharo-project mailing list [hidden email] http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project |
Re: Fwd: sort: and sortBlock:
|
|
On Wed, 23 Dec 2009, Adrian Kuhn wrote:
> Levente Uzonyi <leves@...> writes: > >>> It's a hack, I took it from SortedCollection's quicksort implementation. This >>> gives the best performance if you're sorting by <= which is the default. > > Shouldn't `sort` do what `sort: nil` does? > > A simple `aBlock ifNil: [ ^self sort ]` might be more intention revealing (of > course assumed that `sort` implements a #<= based sort :) In squeak #sort is implemented as self sort: nil. So that check would mean infinite recursion. Levente > > --AA > > > > _______________________________________________ > 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 |