Skip Navigation

Programmer Humor @programming.dev

cm0002 @lemmy.world

2mo ago

timeoutSort

Programmer Humor @lemmy.ml

timeoutSort

95 9

35 comments

finally, sorting in linear time /s
- It’s kind of linear, in the largest element of the array. Just not in the length of the array.
  
  it's in constant time then
- linear in size

I know this under the name sleepSort.

Can't wait for vibe coded programs to use timeoutSort.

Race condition
- Doesn't the tortoise always win that one, too?
  
  No

I'm dumb, can someone ELI5 please?
- The output is sorted due to the fact that for each number, a timer is started that prints out the number after waiting a number of milliseconds equal to said number.
  Therefore, 1 is printed first after delaying for 1 millisecond, 5 is printed second after 5 milliseconds etc.
  
  Perfectly explained, thank you!
  
  So all items in the array are launched simultaneuously and ran in parallel instead of sequentially?
- The program goes through the collection of numbers and prints each one after a delay of milliseconds equal to that number: "Print the number 20 after a 20 millisecond delay. Print the number 5 after a 5 millisecond delay. Print the number 100 after a 100 millisecond delay... etc..." effectively sorting the collection because the numbers will be printed in order from smallest to largest.
  This is a clever (but impractical) way to sort a collection, because it does not require comparing any of the elements of the collection.
  
  because it does not require comparing any of the elements of the collection
  Well, if you are comparing x + a to y and x + b to y and then both to y', then y'' and so on, then are you really not comparing a to b?

This is almost a bucket sort, which is practically O(n).
(I'll leave it to the other readers to state the trade-offs)

Wait till you find out how the runtime manages multiple concurrent timers
- it's
  undefined
  
  while (true) { let t = Date.now(); if (timeoutMap.has(t)) timeoutMap[t](); }
  of course. Clearly O(n).
  
  I found a way to optimize your code without affecting the result. By making it branchless, I was able to get my CPU to 100% utilization!
  
  Then don't complain once you get arrested...

For better usage: you don't need to write it into console. Just write it in an array!

Would this lead to problems if there are multiple identical and close by values? Like for example you have 100 elements each between 1 and 5
- To reduce the chance of errors, you can multiply all numbers by a factor of 10, 100, 1000, 10000, .... for the timeout. The higher the factor, the lower the chances of an incorrect result. And as no one asked about performance...
  
  As added benefit, you can then opyimise the code by dividing the number by 2, making it twice as fast. Think of the savings!
  
  Maybe not peak performance but heigh CPU efficency, it's load ist mostly 0.
- Yes.

 undefined

    
[-3, -1, 
main@desktop:~/Projects/TimeoutSort$ _

why is it doing it in ordinal order?

In a situation where performance isn't required but absolute zero overhead is paramount, this is a perfect sort. Depends on the data itself though. Lots of small numbers maybe multiply each by 10 or 20, lots of big numbers...well...bad luck.

Isn't this basically an implementation of spaghetti sort? I've seriously taken the delay approach before in distributed memory situations.

This algorithm takes K seconds where K is the value of the greatest element.
This means if you just multiply everything by -1 it will take negative time to sort.
Then you can simply unmultiply and read from end to beginning from now on.
This is faster than having it presorted.

35 comments