Hello, Le sam. 28 août 2021 à 19:38, Tim Peters <tim.pet...@gmail.com> a écrit :
> [Laurent Lyaudet <laurent.lyau...@gmail.com>] > > ... > > 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. > > Cool! Could you move this to the issue report already open on this? > > Replace list sorting merge_collapse()? > https://bugs.python.org/issue34561 > > Thanks for the fast and kind answer :) I just did. Sorry for not checking the bugs reports before posting. I only checked that Shivers and Jugé did not appear in the archive of the python-dev mailing list. (If it does then the search here: https://mail.python.org/archives/list/python-dev@python.org/ is broken.) > Alas, that's been inactive for nearly 3 years, but we _were_ making > some decent progress before everyone got distracted by "more > important" stuff. > > You'll see there that Vincent Jugé contributed another version, > designed to address that his sort did substantially worse than what we > already have in some cases with very few runs. Which, for reasons > explained there, is likely important. > > Before that, the best alternative known was - and by far - Munro & > Wild's "powersort" merge strategy. That's deeply rooted in theory > about fast approximations to optimal binary search trees. > > Where that left off, Vincent was going to try proving properties of > his new variant, plus investigate other ideas. Alas, that's where it > ended, as Vincent ran out of time too. > > In any case, yes, I'm entirely in favor of replacing timsort's merge > strategy, by something with provably good properties even in worst > cases. As explained in the issue report, the merge strategy I made up > was merely the first thing I tried that didn't obviously suck ;-) - > almost all the work went into making merging itself as zippy as > reasonably possible.. > I will try to provide a patch before the end of the week. But first I will read https://www.python.org/psf/contrib/ https://devguide.python.org/ I took 5 minutes to fork and do a PR on my fork with the code for merge collapse : https://github.com/LLyaudet/cpython/pull/1 As soon as I have something more polished I'll do a PR on python repo. Any early feedback is welcome :) Best regards, Laurent
_______________________________________________ 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/O3U3DWBLMG67TS55UJ3F2D5CYQZMMRJT/ Code of Conduct: http://python.org/psf/codeofconduct/
