Sorting oddity - feature or ??
Hannes Hirzel
hannes.hirzel.squeaklist at bluewin.ch
Wed May 1 17:00:42 UTC 2002
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
|