[m-dev.] Sorting results
Ralph Becket
rbeck at microsoft.com
Thu Feb 8 02:13:58 AEDT 2001
>From Adrian Pellas-Rice on 07/02/2001 14:45:52
> > n | sort | fwds bwds rand
> > --------+-------+---------------
> > 1000 | merge | 200 200 200
> > 10000 | merge | 213 157 204
> > 100000 | merge | 242 272 294
> ^^^
> A sudden-ish increase from 204 to 294?
>
> > --------+-------+---------------
> > 1000 | heap | 33 100 66
> > 10000 | heap | 77 114 150
> > 100000 | heap | 104 165 226
> > --------+-------+---------------
> > 1000 | quick | 50 100 100
> > 10000 | quick | 106 100 175
> > 100000 | quick | 145 152 255
>
> At this 3-result stage, the heap and quick sorts seem to be enjoying
> logarithmic improvement (relative to list-merge-sort).
>
> On the other hand, the relative improvement of the merge sort would appear
> to be better than linear. If put on the spot, I would explain the sudden
> improvement for the merge sort as a consequence of the n = 100 000 data
> set stressing the L1 cache while the n = 10 000 data set does not (as
> much).
What strikes me as most odd is that mergesort should be largely
insensitive to the order of the input data, yet there's quite a
bit of variance. I used time__clock//1 and converted the results
to milliseconds before computing the ratios (this was under linux).
I thought time__clock returned elapsed processor time for the process
(this is what the docs say), but that fails to explain the difference
in results on differently ordered data.
Ralph
--
Ralph Becket | MSR Cambridge | rbeck at microsoft.com
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to: mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions: mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------
More information about the developers
mailing list