Sorting oddity - feature or ??
danielv at netvision.net.il
danielv at netvision.net.il
Wed May 1 22:48:44 UTC 2002
He's right, the "pivot" (in quicksort terms) is always selected as the
first for this degenerate case, this line is at fault:
[l _ l - 1. k <= l and: [self should: dij precede: (array at: l)]]
whileTrue. "i.e. while dl succeeds dij"
Since "self should: x precede: x" is always true for sortBlock = [:x:y |
x <= y]. So l zips right to the beginning, and that's where the
recursion becomes very unbalanced.
I personally don't feel very much compelled to "fix" this by changing
the sort. One might argue that giving a sort block like <= and many
equal values, if it isn't itself a bug, certainly deserves some
punishment ;-)
Ned Konz <ned at bike-nomad.com> wrote:
> On Wednesday 01 May 2002 09:59 am, David A. Smith wrote:
> > 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.
>
> It is, but I think there is a bug.
>
> The main problem seems to be that defaultSort:to: recurses way too
> much. I'd expect its recursion depth to max out at log2(size) (I
> think), but it's going down to about (size).
>
> I ran it on 100 items, and it got to a recursion depth of 98 (!).
> Twice.
>
> defaultSort: 1 to: 1000
> calls defaultSort: 1 to: 0
> and defaultSort: 2 to: 1000
>
> which doesn't seem right. For one thing, sorting 1 to: 0 is a waste of
> time.
>
> --
> Ned Konz
> http://bike-nomad.com
> GPG key ID: BEEA7EFE
More information about the Squeak-dev
mailing list
|