Sleep Sort |
Hello CoRecursive newsletter subscriber, It’s Jan Sloot claimed to have invented revolutionary data compression that could fit a full movie into a tiny smart card chip. Top executives and investors witnessed his demos and became true believers, ready to bankroll this company into the stratosphere. But was it all an elaborate illusion? Check out the episode and let me know your thoughts. Pi Compression and Sleep SortThis month’s episode mentions my idea for a compression algorithm that wouldn’t work. My idea – it turns out - wasn’t original ( a joke implementation exists ). Here is another magical seeming solution: Sleep sort. !/bin/bash
function f() {
sleep “$1” echo “$1”
}
while [ -n “$1” ]
do
f “$1” &
shift
done
wait
What this is doing, if you don’t love bash like I do, is just starting a new process for each element and having it sleep until it’s time to print its number. The downside here is clearly that sorting a list will take as many seconds as the total number of elements in the list. But the potential upside is how little absolute work needs to be done. To sort a list like [5,3,6,3,6,3,1,4,7] with a standard sort method like merge sort would take 21 comparisons ( I counted), but sleep sort never compares anything and only needs to call sleep nine times to sort this list. How can this be? Sleep sort was not the output of Computer Science research, like QuickSort or MergeSort, but instead published on 4Chan. Sleep sort is different from Pi Compression in that it does work. If your list is short enough, and you aren’t afraid to wait max N seconds, sleep sort will work. The trick is its supposed efficiency. With our [5,3,6,3,6,3,1,4,7] example, sleep sort only performs nine sleeps, but how are those sleeps implemented? Well, it depends on the operating system, but it’s certainly not free. If we pretend the operating system scheduler is a priority queue, then removals are 0(n log n), meaning it would take about 28 comparisons for our list of 9. This is in the range of what merge sort would do. But in practice, things are far worse than this. The Linux scheduler is quite complex, concerning itself with process priority and fairness. Because of this, it could take more like 81 comparisons ( n^2), and that doesn’t count the overhead of context switching and process creation. So, sleepsort is not efficient. It just hides the overhead in a place we aren’t used to looking. But it’s an excellent curiosity because its seemingly absurd assertion gives a lens for digging into how things on computers work. Thank you, 4chan. Take a look at pingfs for another example. Thanks AgainThis month’s podcast episode is an exploration of a similar mysterious tech claim, but it’s combined with a start-up story and a mysterious death. I hope you like it, and I’d love to hear your thoughts. Adam |
Get a monthly update on my podcast, writing and whatever else I'm up to.
Adam Gordon Bell Oct 2nd Hey! It's October, and new podcast episode is out: https://corecursive.com/from-everest-to-startups-with-yoshio-goto/ This episode is about your life. It's about accepting that life is short and using that to structure how you live. Yoshio Goto shares his story of finding what matters by throwing himself at challenges like climbing Everest and joining early-stage start-ups in Silicon Valley. Then, where he finds meaning is totally somewhere else. It feels like I’m...
Adam Gordon Bell July 4th Hey! It's July, and happy July 4th to my American readers. A new podcast episode is out: https://corecursive.com/building-powershell-with-jeffrey-snover/ It's a detailed peek into the internals of Microsoft and the development of Powershell. My guest is Jeffrey Snover and he has a story to share. It's about one man's vision for a better way to manage Windows Servers and the battles that were fought to bring that vision to completion. Overcoming Microsoft's GUI bias —...
Adam Gordon Bell June 4th Hey, It's June now, and I have a new episode out here: Hedy https://corecursive.com/hedy-with-felienne-hermans/ I've been telling friends and colleagues about this episode for several weeks. Whenever someone asks me how the podcast is going, I jump into it: Ok, Imagine this: A burned-out academic seeks renewal by teaching underprivileged 12-year-olds to program. In doing so, she risks her career and builds a programming language that spreads around the world and...