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