This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author LLyaudet
Recipients LLyaudet, koos.zevenhoven, tim.peters, vincent.juge, xtreak
Date 2021-08-29.20:51:56
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1630270316.24.0.936221129014.issue34561@roundup.psfhosted.org>
In-reply-to
Content
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.

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;\
  }\
}\

I will try to provide a patch before the end of the week.
History
Date User Action Args
2021-08-29 20:51:56LLyaudetsetrecipients: + LLyaudet, tim.peters, koos.zevenhoven, xtreak, vincent.juge
2021-08-29 20:51:56LLyaudetsetmessageid: <1630270316.24.0.936221129014.issue34561@roundup.psfhosted.org>
2021-08-29 20:51:56LLyaudetlinkissue34561 messages
2021-08-29 20:51:56LLyaudetcreate