4 ms·
Recently 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 sorte
by CogitoCogito 8y ago
Recently 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.
- justinclift 8y agoMaybe the UK Postcode lookup database? It's about 650MB (CSV): https://data.gov.uk/dataset/7ec10db7-c8f4-4a40-8d82-8921935b4865/national-statistics-postcode-lookup-uk https://data.gov.uk/dataset/7ec10db7-c8f4-4a40-8d82-8921935b... In theory, it's supposed to be updated every now and then, but doesn't seem to have happened since 2015. :( For a direct SQLite version of it, we have it on DBHub: https://dbhub.io/justinclift/National%20Statistics%20Postcode%20Lookup%20UK.sqlite https://dbhub.io/justinclift/National%20Statistics%20Postcod... That site is still in (slow) development though. YMMV. :)
- LordViper128 8y agoCool video, thanks for the visualization!
- mehrdadn 8y agoHere's an idea: if you're on Linux, use this to sort the list of all paths on your file system (find / -xdev). It's a nice dataset since it's (a) a large list, (b) comparisons are nontrivial, and (c) it's a realistic mix of somewhat-sorted-but-not-completely. (Note: If the file system already sorts everything this won't do the job, so it won't work on e.g. WSL.)