Show HN: Sleepsort – Sorting While Sleeping | Hacker News Reader

Show HN: Sleepsort – Sorting While Sleeping

animeshchouhan.com

My take on sleepsort.

I really liked this article. It's the first time I see async Python used to solve a problem.

Suggestion: I think it would make sense to use softmax as the scaling function. This way you don't need to worry about outliers and you get to decide the running time.

Yeah totally agree, it would need a better scaling function to tackle outliers. The basic scaling was just to give an idea of how this could be improved. We can always devise better scaling methods and negative number handling. Thanks for your feedback, will try to incorporate it!

The scheduler itself presumably uses an in memory tree to sort the values it is given so probably that is where the real sorting happens.

But it doesn't have to work that way. The scheduler could scan the whole (unsorted) list at each tick to see if anything is due. No scheduler worth a jot in production is going to do that, but it could.

Saying that sleep sort is really some better form of insertion sort for this reason seems wrong. You might as well say it is bogosort because the scheduler could be using that (and with 1s sleeps it would be faster than sleepsort most of the time despite being generally worse by normal analysis methods).

If a compiler unrolls a short loop to get an extra lick of speed from the tight outer loop, I don't claim I've been clever¹ and spotted the potential optimisation, I probably don't even know it had happened.

[1] At a stretch I could claim the opposite: to be clever because I've resisted the urge to over-optimise manually, potentially producing something less performant than a good compiler would on some/all architecture targets while making the code less maintainable too.

Well, this would depend totally on how the scheduler has been implemented. I will give you an analogy for a simple implementation:

Suppose we receive 10 numbers as inputs. We set up 10 cars around a race track with the numbers as their race numbers and set their speeds to the numbers we received as inputs respectively. Now the judge(scheduler) checks at a fixed small interval which car crossed the line and notes down the order. This list gives us the numbers in a sorted order.

This implementation would be very naive but as I said it totally depends on scheduler internals. Modern deadline schedulers would sort the tasks by their deadline times and that's totally correct. Just pointing this out.

Bingo. Whenever new coroutines are scheduled to be executed sometime in the future, something somewhere needs to keep them sorted so that the event loop knows how to dequeue them.

It's funny to show this to someone new to CS, but I wouldn't be surprised if you could look at the source for the asyncio implementation and figure out exactly what sorting algorithm you are "actually" using.

In case you're thinking of using this in production (please don't)

Keep in mind that there's a general limitation in most sleep implementation across languages.

sleep(x) typically waits for _at least x amount of time/second/millisecond

Therefore, there's a possibility that sleep(2) finishes after sleep(1) because the scheduler is lazy. The risk gets higher the closer the wait interval is to the scheduling rate (timer resolution).

So if you try running this with small amount of time, maybe in microseconds or nanoseconds, and you got items in the wrong order, this would be one explanation.

It's a toy sorting algorithm and isn't meant for production use anyways as it isn't efficient and lacks predictability.

Theoretically I'd think you could do the same with niceness. Start a bunch of processes, have them wait on some condition, set their niceness to the value and fire the condition. I'd assume the process with the highest niceness would run first, and as such would get to insert itself into some list first.

Yeah that's why I generalized the dependency on any scheduler. We can use various properties and methods to achieve the same results.

Also, if you know the distribution of the values, you can achieve sorting or pre-sorting by a letting an order-preserving "hash-function" fill a table, so O(N).

Yes, that is true for any sorting algorithm. We can always achieve better results if we preprocess the data on some parameters. Thanks for your feedback, will try to incorporate this in the later version!

Sleepsort is like a hash-based sort using sleep(x) instead of a hash function h(x).

You can see more here: https://pages.cs.wisc.edu/~siff/CS367/Notes/sorting.html

The function h(x) places the item ordered directly into a table, instead of waiting x timesteps.

The optimal choice of h(x), x ∈ X, is a bounded monotonic function that inverts the distribution of X, so that h(x) is uniformly distributed. It preserves the order and spreads h(x) evenly in the hash-space.

What if the list is so large it takes more seconds to process than the highest value in the list?

Well, the scheduler will process all tasks parallelly, but this too would have its limits. This technique has many pitfalls and is therefore not meant for any practical use.

Reply on news.ycombinator.com