December 2009 - Pharo-dev - lists.pharo.org

Re: [Pharo-project] Fwd: sort: and sortBlock:

by StÃ©phane Ducasse

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

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by StÃ©phane Ducasse

> 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 >>>> Pharo-project(a)lists.gforge.inria.fr >>>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >>> _______________________________________________ >>> Pharo-project mailing list >>> Pharo-project(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >>> >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 23, 2009

Re: [Pharo-project] SUnit forked, gofer it

by Mariano Martinez Peck

On Wed, Dec 23, 2009 at 7:36 PM, StÃ©phane Ducasse <stephane.ducasse(a)inria.fr > wrote: > Adrian > > I know that in GNUSMalltalk paolo long time ago added logging facilities (I > never looked at it > so may be this is just the description: but joseph once talked about that > when he presented toothpick at Bern). > > In addition I also remember Kieth work for Logging which was a frontend for different loggers such us SimpleLog. Links: http://wiki.squeak.org/squeak/3706 http://wiki.squeak.org/squeak/5890 Sorry for go a bit offtopic, but is it possible to run only ONE test from the browser??? I would like to right click on a test method and be execute. Just like the "run tests" option but only for THAT test and not all the tests of that class. Is that possible ? how? Cheers, Mariano > Stef > > On Dec 23, 2009, at 7:20 PM, Adrian Kuhn wrote: > > > Mariano Martinez Peck <marianopeck@...> writes: > > > >> Can I add something to my dear santa list ??Many times, I have tests > that > >> freeze the image. And I don't known what test was the "guilty". I always > hack > >> the runCase to show in Transcript the test selector. Maybe adding a > >> configurable logging option (enable/disable) may help. > > > > Good point. > > > > I plan to add a TestListener that can be used to do this. > > > > --AA > > > > > > > > -- > > 4th Workshop on Dynamic Languages and Applications > > Submit papers by March 31, 2010. http://bit.ly/dyla2010 > > > > > > _______________________________________________ > > Pharo-project mailing list > > Pharo-project(a)lists.gforge.inria.fr > > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 23, 2009

Re: [Pharo-project] Fwd: hasEqualElements:

by Eliot Miranda

On Wed, Dec 23, 2009 at 10:41 AM, <csrabak(a)bol.com.br> wrote: > Em 23/12/2009 16:10, Eliot Miranda < eliot.miranda(a)gmail.com > escreveu: > > > > > Core.SequenceableCollection comparing > > isSameSequenceAs: otherCollection > > > > "Answer whether the receiver's size is the same as otherCollection's > > size, and each of the receiver's elements equal the corresponding > > element of otherCollection." > > > > | size | > > (size := self size) = otherCollection size ifFalse: [^false]. > > 1 to: size do: [:index | > > (self at: index) = (otherCollection at: index) ifFalse: [^false]]. > > ^true > > > > i.e. trust the caller is providing a sequence and if > > otherCollection doesn't implement at: there will be a run-time > > error, hence any otherCollection isKindOf: SequenceableCollection is > > just wasted cycles. > > > > I don't think that "trusting the caller" makes sense in this case, so > I propose instead that you implementation be complemented by: > > Object>>isSameSequenceAs: otherCollection > ^false > We're talking about the argument otherCollection not the receiver. i.e. leaving out isKindOf: in isSameSequenceAs: otherCollection "Answer whether the receiver's size is the same as otherCollection's size, and each of the receiver's elements equal the corresponding element of otherCollection." | size | (otherCollection isKindOf: SequenceableCollection) ifFalse: [^false]. "this is a horrible wart" (size := self size) = otherCollection size ifFalse: [^false]. 1 to: size do: [:index | (self at: index) = (otherCollection at: index) ifFalse: [^false]]. ^true You could use double dispatching: SequenceableCollection>>isSameSequenceAs: otherThing ^otherThing isSameSequenceAsSequence: self SequenceableCollection>> isSameSequenceAsSequence: aSequenceableCollection aSequenceableCollection size ~= self size ifTrue: [^false]. etc Object isSameSequenceAsSequence: aSequenceableCollection ^false but I think in this case it's overkill. > -- > Cesar Rabak > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by Levente Uzonyi

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? 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. Levente > > Stef > > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by csrabak＠bol.com.br

:-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 < stephane.ducasse(a)inria.fr > 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 Pharo-project(a)lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by Levente Uzonyi

On Wed, 23 Dec 2009, Nicolas Cellier wrote: > 2009/12/23 Levente Uzonyi <leves(a)elte.hu>: >> 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... Indeed. > 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 >>> Pharo-project(a)lists.gforge.inria.fr >>> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> >> _______________________________________________ >> Pharo-project mailing list >> Pharo-project(a)lists.gforge.inria.fr >> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >> > > _______________________________________________ > Pharo-project mailing list > Pharo-project(a)lists.gforge.inria.fr > http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project >

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by StÃ©phane Ducasse

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

Dec. 23, 2009

Re: [Pharo-project] Fwd: sort: and sortBlock:

by StÃ©phane Ducasse

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

Dec. 23, 2009

Re: [Pharo-project] Fwd: hasEqualElements:

by csrabak＠bol.com.br

Em 23/12/2009 16:10, Eliot Miranda < eliot.miranda(a)gmail.com > escreveu: > > Core.SequenceableCollection comparing > isSameSequenceAs: otherCollection > > "Answer whether the receiver's size is the same as otherCollection's > size, and each of the receiver's elements equal the corresponding > element of otherCollection." > > | size | > (size := self size) = otherCollection size ifFalse: [^false]. > 1 to: size do: [:index | > (self at: index) = (otherCollection at: index) ifFalse: [^false]]. > ^true > > i.e. trust the caller is providing a sequence and if > otherCollection doesn't implement at: there will be a run-time > error, hence any otherCollection isKindOf: SequenceableCollection is > just wasted cycles. > I don't think that "trusting the caller" makes sense in this case, so I propose instead that you implementation be complemented by: Object>>isSameSequenceAs: otherCollection ^false -- Cesar Rabak

Dec. 23, 2009