[Finn Bock] > ... > The old sorting code in jython was the 1.5 code from CPython with a > quicksort implementaion also inspired by Tim Peters. The sad thing is, that was a very good quicksort -- I thought I was done when I wrote that <wink>. > Switching to timsort is obviously a nobrainer for us. Thanks for sharing this! Made my day <smile>. I noted in the Jython patch that you should see a nice speedup by nuking the assert() calls once you're confident in the port; Java is checking out-of-bound array indices for you, and that's largely what the asserts are guarding against in the C implementation. > You also don't need to hold back on giving stability garanties in the > documentation for jython's sake. I didn't <wink>. Stability doesn't come free, and for all I know, in another 3 years a method will be discovered that's 3x faster but not stable. For example, Splaysort is (as an email correspondent reminded me) provably adaptive to all known measures of presortedness, but when I looked at the code it "was obvious" that it wouldn't be competitive on random data; it also requires two pointers per list element. In coming years, researchers may well dream up quicker ways to get the same goodness, but Splaysort isn't stable, and very few fast algorithms are. So I don't want to hobble future implementations by holding Python to promises I don't care much about. OTOH, I do expect that once code relies on stability, we'll have about as much chance of taking that away as getting rid of list.append().
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4