[Tim] > ... > There's also a significant systematic regression in timsort's +sort case, > ... also a mix of small regressions and speedups in 3sort. > These are because, to simplify experimenting, ...(and as many as > N-1 temp pointers can be needed, up from N/2). That's all repairable, > it's just a PITA to do it. It's repaired, and those glitches went away: > timsort > i 2**i *sort \sort /sort 3sort +sort ~sort =sort !sort > 15 32768 0.17 0.01 0.02 0.01 0.01 0.05 0.01 0.02 > 16 65536 0.24 0.02 0.02 0.02 0.02 0.09 0.02 0.04 > 17 131072 0.54 0.05 0.04 0.05 0.05 0.19 0.04 0.09 > 18 262144 1.17 0.09 0.09 0.10 0.10 0.38 0.09 0.18 > 19 524288 2.56 0.18 0.17 0.20 0.20 0.79 0.17 0.36 > 20 1048576 5.54 0.37 0.35 0.37 0.41 1.62 0.35 0.73 Now at 15 32768 0.17 0.01 0.01 0.01 0.02 0.09 0.01 0.03 16 65536 0.24 0.02 0.02 0.02 0.02 0.09 0.02 0.04 17 131072 0.53 0.05 0.04 0.05 0.05 0.18 0.04 0.09 18 262144 1.17 0.09 0.09 0.10 0.09 0.38 0.09 0.18 19 524288 2.56 0.18 0.18 0.19 0.19 0.78 0.17 0.36 20 1048576 5.53 0.37 0.35 0.36 0.37 1.60 0.35 0.74 In other news, an elf revealed that Perl is moving to an adaptive stable mergesort(!!!harmonic convergence!!!), and sent some cleaned-up source code. The comments reference a non-existent paper, but if I change the title and the year I find it here: Optimistic sorting and information theoretic complexity. Peter McIlroy. SODA (Fourth Annual ACM-SIAM Symposium on Discrete Algorithms), pp 467-474, Austin, Texas, 25-27 January 1993. Jeremy got that for me, and it's an extremely relevant paper. What I've been calling galloping he called "exponential search", and the paper has some great analysis, pretty much thoroughly characterizing the set of permutations for which this kind approach is helpful, and even optimal. It's a large set <wink>. Amazingly, citeseer finds only one reference to this paper, also from 1993, and despite all the work done on adaptive sorting since then. So it's either essentially unknown in the research community, was shot full of holes (but then people would have delighted in citing it just to rub that in <0.5 wink>), or was quickly superceded by a better result (but then ditto!). I'll leave that a mystery. I haven't had time yet to study the Perl code. The timsort algorithm is clearly more frugal with memory: worst-case N/2 temp pointers needed, and, e.g., in +sort it only needs (at most) 10 temp pointers (independent of N). That may or may not be good, though, depending on whether the Perl algorithm makes more effective use of the memory hierarchy; offhand I don't think it does. OTOH, timsort has 4 flavors of galloping and 2 flavors of binary search and 2 merge routines, because the memory-saving gimmick can require merging "from the left" or "from the right", depending on which run is smaller. Doubling the number of helper routines is what "PITA" meant in the quote at the start <wink>. One more bit of news: cross-box performance of this stuff is baffling. Nobody else has tried timsort yet (unless someone who asked for the code tried an earlier version), but there are Many Mysteries just looking at the numbers for /sort under current CVS Python. Recall that /sort is the case where the data is already sorted: it does N-1 compares in one scan, and that's all. For an array with 2**20 distinct floats that takes 0.35 seconds on my Win98SE 866MHz Pentium box, compiled w/ MSVC6. On my Win2K 866MHz Pentium box, compiled w/ MSVC6, it takes 0.58(!) seconds, and indeed all the sort tests take incredibly much longer on the Win2K box. On Fred's faster Pentium box (I forget exactly how fast, >900MHz and <1GHz), using gcc, the sort tests take a lot less time than on my Win2K box, but my Win98SE box is still faster. Another Mystery (still with the current samplesort): on Win98SE, !sort is always a bit faster than *sort. On Win2K and on Fred's box, it's always a bit slower. I'm leaving that a mystery too. I haven't tried timsort on another box yet, and given that my home machine may be supernaturally fast, I'm never going to <wink>.
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