10 ms·
Timsort is a sorting algorithm that is efficient for real-world data
- bluecalm 8y agoAre there benchmarks available for this kind of algorithm? If you come up with a fast sorting algorithm how would you go about making a case it's faster than currently used ones on real world data?
- gleenn 8y agoWell I think that ship has already sailed, Timsort is used in Java on Android and Python, so it's already seen massive adoption.
- repsilat 8y agoI'd hope people using it wouldn't have chosen it unless they had measured performance -- doubly so if the switched to it from something else. On the other hand, common third-party benchmarks may not be useful for measuring these sorts of improvements, which take advantage of common input distribution biases. "Real world workloads" is really too much of a simplification -- people sort all shapes and sizes of data. When JS engines started getting fast(er), every engine made their own preferred benchmark because they said existing ones didn't adequately show the real-world gains their engines were providing. We shouldn't be reflexively cynical about that. If they have made good-faith measurements, it is likely that old benchmarks were "unrepresentstive" in some way. Again, "real world benchmarking" is hard, and that applies just as much to yesterday's benchmarks as today's.
- hyperpape 8y agoYou can go back and read the mailing list archives to see the benchmarks that were used by Python devs to decide on using Timsort: https://mail.python.org/pipermail/python-dev/2002-July/thread.html#26837 https://mail.python.org/pipermail/python-dev/2002-July/threa... You can also read Tim Peter's notes about the sort: https://bugs.python.org/file4451/timsort.txt https://bugs.python.org/file4451/timsort.txt That was back in 2002, so there's certainly been a lot of scrutiny since then. In particular, I've never actually read about Java sorting benchmarks, but there are tremendously sophisticated benchmarking tools/benchmarking experts in the Java world, so I imagine that it got a lot of analysis there.
- BeeOnRope 8y agoIt's worth noting that Java doesnt exclusively use Timsort. Depeding on the data type and heuristics based mostly on the size of the input array, a simpler sort such as counting sort may be use. You can find a more detailed summary at: https://stackoverflow.com/a/41129231/149138 https://stackoverflow.com/a/41129231/149138
- hyperpape 8y agoCool find. I'd never actually realized that.
- bradleyjg 8y agoFrom the Rust link above there were these links to code for generating test patterns: https://github.com/notriddle/quickersort/blob/master/examples/perf_txt.rs#L63 https://github.com/notriddle/quickersort/blob/master/example... https://github.com/llvm-mirror/libcxx/blob/master/benchmarks/GenerateInput.hpp https://github.com/llvm-mirror/libcxx/blob/master/benchmarks... https://github.com/Morwenn/cpp-sort/blob/master/benchmarks/distributions.h https://github.com/Morwenn/cpp-sort/blob/master/benchmarks/d...
- bjourne 8y agoProbably more than you can shake a stick at: https://www.postgresql.org/message-id/CAEYLb_W%2B%2BUhrcWprzG9TyBVF7Sn-c1s9oLbABvAvPGdeP2DFSQ%40mail.gmail.com https://www.postgresql.org/message-id/CAEYLb_W%2B%2BUhrcWprz... :)
- strainer 8y agoI wrote a personal benchmark suite specifically to compare the Javascript port of Timsort to my own 'pet' Javascript sorting module 'Barsort.js' which was specialised to sorting Numbers, while Timsort also does strings quickly and takes custom comparators. I tested these distributions for arrays of 100 to 1000000 elements: descending ints ascending ints descending ints with maveric vals ascending ints with maveric vals equally distributed reals from -20 to 20 gaussian distribution -1 to 1 midspiked reals with duplicates -200 to 200 huge magnitude with gaps and duplicates and infinites equal-dist of ints 1 or 2 equal-dist of ints 1 2 3 equal-dist of ints 1 2 3 4 equal-dist of ints 1 2 3 4 5 Timsort seemed relatively a little slow with gaussian/normal and equal distributions, but still 10x faster or more than browsers native sort at the time. I was able to extend my pet sorting module to be quite competitive with Timsort's Javascript port. It was a captivating side project that I escaped from as soon as tests passed, its code not in a decent state, but is here - https://github.com/strainer/barsort https://github.com/strainer/barsort
- justinclift 8y ago> If you come up with a fast sorting algorithm how would you go about making a case it's faster than currently used ones on real world data? For analysing sorting algorithms - and related things which that leads into - there are established ways to determine their best, average, and worst case runtimes for input of a given size. If you're interested in learning this stuff, the video's here are useful and not math heavy: https://www.coursera.org/learn/algorithms-part1 https://www.coursera.org/learn/algorithms-part1 Technically it's explained using java. But it's mostly done using primitive data types (eg int, float, byte, ...). So it's very easy to follow along and copy the implementation, but translated to a different language (Go in my case, as I don't do java at all).
- bbno4 8y agoHey! Author here! Thank you so much for posting this here! If you have any questions feel free to ask me
- kbd 8y ago> Since the algorithm has been invented it has been used as the default sorting algorithm in Python, Java, the Android Platform, and in versions of GNU. I'm glad you mentioned how far the algorithm has spread to other languages since originating in Python. But, "versions of GNU" what?
- deleted 8y ago[deleted]
- LeoPanthera 8y agoI assume he means sort/gsort, from the coreutils.
- eesmith 8y agohttp://git.savannah.gnu.org/cgit/coreutils.git/tree/src/sort.c#n3175 http://git.savannah.gnu.org/cgit/coreutils.git/tree/src/sort... says: Use a recursive divide-and-conquer algorithm, in the style suggested by Knuth volume 3 (2nd edition), exercise 5.2.4-23. Use the optimization suggested by exercise 5.2.4-10; this requires room for only 1.5*N lines, rather than the usual 2*N lines. Knuth writes that this memory optimization was originally published by D. A. Bell, Comp J. 1 (1958), 75.
- seba_dos1 8y agoVersions of GNU. Although it's rare to see this term being used in this context these days, "GNU" was invented as a name of an operating system.
- copperx 8y agoThat raises the question, what does the Hurd kernel use timsort for?
- Cynddl 8y ago> Timsort is a sorting algorithm that is efficient for real-world data and not created in an academic laboratory. It's always a bit sad to see academia as an ivory tower where researchers generate unusable knowledge. Academia is not only about finding theoretical pure solutions but often also about finding solutions to real-world problems. For instance, machine learning, logic design, networking algorithms, cryptography, all deeply depend on work done in academia (and not just “theoretical” work).
- tomnipotent 8y ago> machine learning, logic design, networking algorithms, cryptography, all deeply depend on work done in academia (and not just “theoretical” work) All highly theoretical fields long before we found concrete applications. It often took one or more people an entire lifetime to convince others than these were valuable subjects to pursue. > Academia is not only about finding theoretical No, but it has to start there. Theoretical science is how we find new things to turn into applied science. It required 45+ years between the time Heinrich Hertz introduced contact mechanics and RADAR was put into use, 33 years from when Einstein published mass–energy equivalence (E=mc2) and Otto Hahn cracked nuclear fission but only a few more years until Robert Oppenheimer and the Manhattan project turned that into the first atom bomb.
- rs86 8y agoLet's add all the work on finding decision procedures for all of mathematics to that list
- barrkel 8y agoNo, but it has to start there. That's simply not true. There's a loop: sometimes, industry comes up with a specific innovation, and academia generalized it; other times, academia comes up with an idea, and it's implemented in industry (often a commercialisation effort by the inventors). And sometimes academics are employed by industry and there's a hybrid. There's no one true way.
- dfbrown 8y agoIn addition, in Tim's post on the python mailing list he says he developed the algorithm after reading through a number of papers on sorting[1]. So while the algorithm was developed with the goal of being practical, plenty of academic research was used to develop it. [1]: https://mail.python.org/pipermail/python-dev/2002-July/026837.html https://mail.python.org/pipermail/python-dev/2002-July/02683...
- ylmm 8y agoDon't forget: https://news.ycombinator.com/item?id=9100107 https://news.ycombinator.com/item?id=9100107
- dean177 8y agoFor those with a similar train of thought, this PR describes the standard sorting algorithm used in Rust: https://github.com/rust-lang/rust/pull/38192 https://github.com/rust-lang/rust/pull/38192
- karmakaze 8y agoThis is great. A simpler TimSort without galloping but keeping merging of runs. It needs a good name (or any name for that matter) so that it can get picked up and used elsewhere. I'll suggest Pacesort (because the pace gait has smaller steps than a gallop and doesn't have many search results).
- kzrdude 8y agoShould be Stjepan sort, didn't he invent this variant?
- gameswithgo 8y agoTimmaySort?
- karmakaze 8y agoTimmay!
- CogitoCogito 8y agoRecently I "made" [0] one of those visualized sorting videos for Timsort for real-world data. Point was to give an example of data that was already mostly sorted and show how fast it sorts it. It may be of interest here: https://www.youtube.com/watch?v=ZxLxf5xqqyE https://www.youtube.com/watch?v=ZxLxf5xqqyE [0] My use of "made" gives me way more credit than I'm due. Really I just hacked others' work to use another data source. See the description in the video for more info on how it was produced.
- jftuga 8y agoNice video, thanks for sharing this.
- WalterGR 8y agoI feel like this is important to note: My example of real world data is data in which the first 90% is already sorted and the next 10% is random. Whether this is real enough is questionable, but it does demonstrate how Timsort automatically takes advantage of runs of sorted data. It would be nice to see a comparison working on truly real-world data. Perhaps from an open dataset.
- CogitoCogito 8y agoYeah seeing more datasets would definitely be nice. I linked my GitHub repo where I made the changes necessary for this example in the YouTube video. Using the last commit (the only changes from upstream) as a guide, other datasets cold be supported similarly. That said, I don't think my choice of data is that bad actually. Apparently starting with a sorted dataset, appending some new items, and then sorting the result again is very commonly done by programmers. That is essentially what's represented in my example.
- cntlzw 8y agoI am experimenting with Lidar datasets lately. In lidar you work with huge point clouds. Millions to billions. For some algorithms - convex hull - you need to sort the points for example by x-cooridinate. I did some quick tests with quick sort, merge sort, and timsort. In my experiments quick sort was the slowest with 5.5 seconds on the chosen dataset. Mergesort was 5 seconds and timsort was around 4 seconds.
- bane 8y agoIt's a great piece of engineering and because of the tongue-in-cheek name might be confused with a joke sorting algorithm...my favorite of which is sleep sort. https://www.geeksforgeeks.org/sleep-sort-king-laziness-sorting-sleeping/ https://www.geeksforgeeks.org/sleep-sort-king-laziness-sorti...
- senatorobama 8y agoAny sorting algorithms that use deep learning?
- KMag 8y agoYou could of course write one. Presumably you're talking about using deep learning to decide the order in which to compare elements, but this would be difficult to ensure both always terminated and always gave correct results, to say nothing of likely being very inefficient. The difficulties in sorting algorithms aren't difficulties in recognizing patterns, so it's difficult to see what deep learning brings to the table. That being said, knock yourself out; surprise me!
- pouta 8y agoMaybe finding in the input data.
- KMag 8y ago"Finding" what in the input data as a part of sorting?
- neolefty 8y agoFor creating custom comparators? "Sort these web pages in order of quality."
- KMag 8y agoI've never seen a reference text that considers the comparator part of the sorting algorithm. Timsort, quicksort, mergesort, introsort, smoothsort, etc. don't include the comparator as part of the algorithm definition.
- jogjayr 8y agoYou mean like a search engine? :-) I believe ML is used in search engines nowadays.
- 8y ago
- nixpulvis 8y agoI'm not a fan of the anti-academic vibes in this post. Good technology can be born anywhere, but it's foolish to ignore the advantages of research.
- archgoon 8y agoWell, to be fair, I'm always concerned about those vat grown algorithms from a lab. I mean, are we sure they're safe?
- raymondh 8y agoIn Python 3.7, the Timsort was sped-up another 40 to 75% for homogenous lists (just some of the common cases). It works by replacing Python's slow generic PyObject_RichCompareBool() with a type-specialized comparison function. * https://docs.python.org/3/whatsnew/3.7.html#optimizations https://docs.python.org/3/whatsnew/3.7.html#optimizations * https://bugs.python.org/issue28685 https://bugs.python.org/issue28685
- linsomniac 8y agoIn the film _Heist_, Gene Hackman's character is asked how he pulled something off. "I tried to imagine someone smarter than myself and I then I thought: What would he do?" When I need to pull something off, I ask myself: What would Tim do?
- redcalx 8y agoI ported timsort to C#/dotnet recently. Available in this nuget: https://www.nuget.org/packages/Redzen/ https://www.nuget.org/packages/Redzen/ Source code here (there are three variants): https://github.com/colgreen/Redzen/tree/master/Redzen/Sorting https://github.com/colgreen/Redzen/tree/master/Redzen/Sortin... None of the standard framework sort methods perform a stable sort so it's handy for that, as well as being a lot faster for some data, i.e. with pre-sorted runs. Otherwise the framework now uses introsort which is pretty good, so you should definitely performance test with both. I use both sorts depending on the context and I usually end up using the built in introsort, with timsort used for a few special cases.
- anqurvanillapy 8y agoI ran the code and it gave me [2, 3, 5, 6, 7], missing the 1. Appending the_array[i] after clearing the new_run by `new_run = []` seems to fix this issue.