Hello,
I developed a C sorting algorithms library that currently has a few
dozens of algorithms and thousands of variants when choosing
parameters (like threshold for switching to insertion sort, etc.).
(I compile each variant on demand in custom tests
to avoid having a bloated source file.)
My benchmarks could be improved but however I found that Shivers' sort
and adaptive Shivers' sort (aka Jugé's sort) performs better than
Tim's sort.
I don't know if it will still be true with the benchmarks in Python.
If you're open to the idea that maybe Tim's sort can be improved and
are willing to benchmark it, it can be done easily by switching the
main natural merge strategy like I did here :
https://github.com/LLyaudet/TSODLULS/commit/2968c4b4ca58ae794157dc9636ed87017e5f7a17
The relevant code is not very long :
/**
* This strategy is from ShiversSort:
* see the research report by Olin Shivers, Georgia Institute of
Technology, 2002.
* It uses bitwise tricks to check condition on floor of logarithms in
base 2 of runs lengths.
* When I benchmark it, it is slightly faster than Tim's sort strategy.
*/
#define TSODLULS_natural_merge_main_strategy__Shivers_sort \
while(merge_state.i_run_instances_count > 1){\
size_t i_merge_at = merge_state.i_run_instances_count - 2;\
size_t i_order_of_magnitude =
merge_state.arr_run_instances[i_merge_at + 1].i_length;\
if(i_order_of_magnitude < ((~i_order_of_magnitude) &
merge_state.arr_run_instances[i_merge_at].i_length) ){\
break;\
}\
i_compare_result = TSODLULS_MERGE_TWO_RUNS(&merge_state, i_merge_at);\
if(i_compare_result != 0){\
goto clean_and_return_error;\
}\
}\
/**
* This strategy is from AdaptiveShiversSort:
* see the articles by Vincent Jugé, for example 1024 Bulletin de la
SIF, avril 2020, in French,
* or the preprint on arXiv or SODA 2020 proceedings.
* It uses bitwise tricks to check condition on floor of logarithms in
base 2 of runs lengths.
* When I benchmark it, it is slightly faster than Tim's sort strategy.
* Despite its ressemblance with Shivers's sort,
* the distinct properties of this strategy make that JugéSort would
probably be a better name than AdaptiveShiversSort,
* or an even better name for the whole algorithm should be
TimShiversJugéSort and I must have missed many names ;)
* With AdaptiveShiversSort we avoid 'é' and diacritics in function names ;P
*/
#define TSODLULS_natural_merge_main_strategy__adaptive_Shivers_sort \
while(merge_state.i_run_instances_count > 2){\
size_t i_merge_at = merge_state.i_run_instances_count - 3;\
size_t i_order_of_magnitude =
merge_state.arr_run_instances[i_merge_at + 1].i_length |
merge_state.arr_run_instances[i_merge_at + 2].i_length;\
if(i_order_of_magnitude < ((~i_order_of_magnitude) &
merge_state.arr_run_instances[i_merge_at].i_length) ){\
break;\
}\
i_compare_result = TSODLULS_MERGE_TWO_RUNS(&merge_state, i_merge_at);\
if(i_compare_result != 0){\
goto clean_and_return_error;\
}\
}\
In my library the merge strategy is a parameter and I switch its macro
when compiling competitors algorithms on demand.
I hope it may help.
Thanks for your time.
If you want to look further at my library, it works with gcc and
glibc. I have not tested it on other platforms and whilst I have no
compilation warning on my personal dev laptop, I do have one when I
run it on the laptop I'm currently writing this email. The tests
passes nevertheless.
Best regards,
Laurent Lyaudet
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at
https://mail.python.org/archives/list/python-dev@python.org/message/MHK54GBJRKUKMTXKUK3S52LMCWDNMZCK/
Code of Conduct: http://python.org/psf/codeofconduct/
