On Thursday 27 June 2002 12:10, Ketil Z. Malde wrote:
*lights go on*
Of course! While I have about 90K values to sort, it's only a range
from 0 to about 5-600, and a less than even distribution at that. (I
must be a lot denser than I thought. Colin, if you ever happen to pass
by, do let
Ketil Z. Malde wrote:
5.02 uses quicksort,
That's funny, since I see quadratic scaling, I must be hitting worst
case both times? 'sort' and 'sortBy' *are* implemented in the same
way, right?
Implementations of QuickSort on lists usually take the easy option of
using the head of the list as
Colin Runciman [EMAIL PROTECTED] writes:
Also, curiously enough, it could just as well be the problem that your
int-sorting phase has too *little* sorting to do, as this common
version of quickSort degenerates both for in-order and reverse-order
inputs.
*lights go on*
Of course! While I
Hi,
I have what I think is a really strange problem. I have a fair sized
problem, which involves sorting a data set, first on labels (which are
Strings) and then on scores (which are Ints).
The strange thing is that string sorting is *vastly* faster than int
scoring! Now, I've tried
Ketil Z. Malde wrote:
I have what I think is a really strange problem. I have a fair sized
problem, which involves sorting a data set, first on labels (which are
Strings) and then on scores (which are Ints).
The strange thing is that string sorting is *vastly* faster than int
scoring! Now,
Colin Runciman [EMAIL PROTECTED] writes:
Could it be that the string-comparison sort simply has less sorting to do
than the int-comparison sort?
Not quite improbable, hang on while I print the profiling (with
comparison in its own function): Yes, that seems to be the case, for
90K values to
[EMAIL PROTECTED] (Ketil Z. Malde) writes:
for 90K values to sort, I get 7M string comparisons and 321M integer
..and with different parameters giving 127K values, ie. a factor of
1.4, I get 12M and 614M comparisons, *very* close to the expected
O(n²) behavior of insertion sort.
The default
On Wednesday 26 June 2002 04:19 am, Colin Runciman wrote:
Could it be that the string-comparison sort simply has less sorting to do
than the int-comparison sort? The default definition of sortBy uses
insertion sort, so if the string-sort input happens to be already sorted
it takes linear
