Show HN: Sleepsort – Sorting While Sleeping
https://animeshchouhan.com/posts/sleepsort/By animeshchouhan at
My take on sleepsort.0x45696e6172 | 1 comment | 3 weeks ago
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.
animeshchouhan | 0 comments | 2 weeks ago
datascienced | 3 comments | 3 weeks ago
dspillett | 0 comments | 3 weeks ago
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.
animeshchouhan | 0 comments | 2 weeks ago
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.
qsort | 0 comments | 3 weeks ago
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.
Charon77 | 1 comment | 3 weeks ago
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.
animeshchouhan | 0 comments | 2 weeks ago
delusional | 1 comment | 3 weeks ago
animeshchouhan | 0 comments | 2 weeks ago
yobbo | 1 comment | 3 weeks ago
animeshchouhan | 1 comment | 2 weeks ago
yobbo | 0 comments | 2 weeks ago
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.