[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: sorting in C
From: |
Andrew Cohen |
Subject: |
Re: sorting in C |
Date: |
Wed, 23 Feb 2022 20:53:28 +0800 |
User-agent: |
Gnus/5.13 (Gnus v5.13) Emacs/29.0.50 (gnu/linux) |
>>>>> "EZ" == Eli Zaretskii <eliz@gnu.org> writes:
[...]
EZ> The 5-fold slowdown is a pain, IMO. Can we do better in the
EZ> worst case?
Maybe, but probably not too much. That is the point of these
hybrids---they improve on some cases and do worse on others. Its a win
only if the real-world data favors the improved case.
I played around a bit more and lowering the length threshold to 40
might be a better compromise. I am working on a more thorough set of
tests first.
We can always dispense with the insertion sort bit (or set a very low
threshold) and just keep the vector routine. This is a consistent 30%
win across the board.
>> And implementing TIMSORT will be even better---similar or better
>> speedup for the best cases, and only marginal degradation of the
>> worst. But I think even this small change here is a win.
EZ> Can we see the numbers? This sounds like a net win to me.
Err, no? I have it all working but I'm using a C version of TIMSORT from
the web. I don't think the license is acceptable so it probably needs to
be written from scratch. Shouldn't be that difficult (the algorithm
itself is well-documented) but I'm not sure how much time I have to
finish it.
Best,
Andy
--
Andrew Cohen
- sorting in C, Andrew Cohen, 2022/02/21
- Re: sorting in C, Eli Zaretskii, 2022/02/22
- Re: sorting in C, Andrew Cohen, 2022/02/22
- Re: sorting in C, Andrew Cohen, 2022/02/22
- Re: sorting in C, Eli Zaretskii, 2022/02/23
- Re: sorting in C,
Andrew Cohen <=
- Re: sorting in C, Eli Zaretskii, 2022/02/23
- Re: sorting in C, Andrew Cohen, 2022/02/23
- Re: sorting in C, Andrew Cohen, 2022/02/23
- Re: sorting in C, Eli Zaretskii, 2022/02/23
- Re: sorting in C, Andrew Cohen, 2022/02/26
- Re: sorting in C, Andrew Cohen, 2022/02/26
- Re: sorting in C, Eli Zaretskii, 2022/02/27
- Re: sorting in C, Andrew Cohen, 2022/02/27
- Re: sorting in C, Eli Zaretskii, 2022/02/27
- Re: sorting in C, Andrew Cohen, 2022/02/27