Sorting oddity - feature or ??
David A. Smith
dastrs at bellsouth.net
Wed May 1 16:59:33 UTC 2002
Well, actually...
The default for #asSortedCollection is <=.
If instead, one were to replace this with:
[((1 to: 10000) collect: [:x |3]) asSorterdCollection:[ :a :b | a<b ]
timeToRun ==> 183
compared with:
[((1 to: 10000) collect: [:x |3]) asSorterdCollection:[ :a :b | a<=b]]
timeToRun ==> 29150
Obviously, the comparison is always true, hence something always happens
(probably a swap).
Hence, not a bug - though I think sorting on <= is inefficient.
DAS
At 06:00 PM 5/1/2002 +0100, you wrote:
>Bob Arning <arning at charm.net> wrote:
> > Hi all,
> >
> > Is the following a known and accepted feature of our sorting algorithm?
> >
> > [((1 to: 10000) collect: [ :x | x]) asSortedCollection] timeToRun ==> 98
> >
> > [((1 to: 10000) collect: [ :x | 3]) asSortedCollection] timeToRun ==> 20826
> >
> > Cheers,
> > Bob
>
>No, I don't think it is known and accepted.
>
>Another test:
>[((1 to: 10000) collect: [ :x | 10001 - x]) asSortedCollection]
>timeToRun ==> 87
>
>
>
>asSortedCollection
>
>calls
>
>newFrom: aCollection "implemented in OrderedCollection"
> "Answer an instance of me containing the same elements as
> aCollection."
>
> | newCollection |
> newCollection _ self new: aCollection size.
> newCollection addAll: aCollection.
> ^newCollection
>
>
>And #addAll: is implemented in SortedCollection
>
>addAll: aCollection
> aCollection size > (self size // 3)
> ifTrue:
> [aCollection do: [:each | self addLast: each].
> self reSort]
> ifFalse: [aCollection do: [:each | self add: each]].
> ^ aCollection
>
>
>which calls #add:
>
>add: newObject
> ^ super insert: newObject before: (self indexForInserting: newObject)
>
>which finally calls
>#insert:before:
>
>and
>#indexForInserting:
>
>
>Two methods which are fairly complex and must contain an error
>somewhere.
>
>Are there sorting specialists out there?
>
>Regards
>Hannes
More information about the Squeak-dev
mailing list
|