Sleepsort
Languages and libraries
sorting algorithm demo
SHOW HN2024
How HN took it
1 positive, 5 neutral or asking, 0 mixed, 2 critical, out of 8 comments about the project. Thread score -0.10.
Performance: 0 for, 2 againstIdea: 1 for, 0 against
The thread, comment by comment
Each row is a top-level comment and its replies, in HN's order. Select a cell to open that comment on HN.
positive neutral or mixed critical about another commenter or something else the maker
What HN said
What people liked
Liked the article and the use of async Python to show a problem
From 1 comment
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…
0x45696e6172 on HN
Objections
Not suitable for production; sleep timing is not precise and the algorithm is inefficient
From 3 comments
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)…
Charon77 on HNIt's a toy sorting algorithm and isn't meant for production use anyways as it isn't efficient and lacks predictability.
animeshchouhan on HNWell, 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.
animeshchouhan on HN
Sorting happens in the scheduler, so calling it sleep sort is misleading
From 3 comments
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.
datascienced on HNBingo. 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…
qsort on HNBut 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…
dspillett on HN
Requests
Use softmax or better scaling to handle outliers and negative numbers
From 2 comments
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…
0x45696e6172 on HNYeah 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…
animeshchouhan on HN
Preprocess data with an order-preserving hash to pre-sort
From 3 comments
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).
yobbo on HNYes, 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…
animeshchouhan on HNSleepsort 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…
yobbo on HN
Questions
What happens when the list is so large that processing takes longer than the largest value?
From 2 comments
What if the list is so large it takes more seconds to process than the highest value in the list?
personalityson on HNWell, 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.
animeshchouhan on HN
Alternatives named
Hash-based sorting with an order-preserving function
From 2 comments
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).
yobbo on HNSleepsort 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…
yobbo on HN
Scheduler-based sorting via niceness or process priorities
From 1 comment
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.…
delusional on HN