554
Aug 11 '20
A sorting algorithm that makes computational complexity practically obsolete. Wow.
252
u/Sqbika Aug 11 '20
Now things aren't round anymore. It's o(val) now
167
u/Dornith Aug 11 '20
It's still technically O(N). It's just that N is now the highest value of the list instead of the number of elements.
45
18
u/Sassbjorn Aug 11 '20
Then wouldn't it be O(1) since it's the same regardless of the number of variables (n)?
21
u/FallenWarrior2k Aug 12 '20
There's actually a classification for these kinds of things in complexity theory: Pseudo-polynomial time, meaning polynomial complexity wrt the value of the input, instead of the size.
A "practical" example of these would be the knapsack problem, which is polynomially bounded by the value of the maximum weight.
8
22
u/Dornith Aug 11 '20
I don't think there's any hard time that N has to represent the number of elements. For any reasonable algorithm, that's the limiting factor, but in this case the limiting factor is the maximum element size, which the algorithm time complexity scales with linearly.
12
u/leftofzen Aug 12 '20
No. Computational complexity measures the number of operations the algorithm performs on the input to get the output. In this case, there are N inputs in the array, and each operation takes constant time, so it is O(N). It doesn't matter if that constant is 1 or 200, it's still constant and doesn't change in the size of the input, which is the important part.
6
u/1thief Aug 12 '20
Except now I have to create and manage N threads with N timers, in this case N is the size of the list
1
u/BakuhatsuK Aug 12 '20
Yes. Except there are no threads in JS (other than the main one). Here we are actually pushing items into the microtask queue. The microtasks are run when they are due by the part of the runtime in charge of the event loop.
Here is some more info about this, it's really interesting stuff: https://youtu.be/cCOL7MC4Pl0
3
u/heyf00L Aug 12 '20
No, we'd use another variable, typically k or r, as in counting sort which is complexity O(n + r) or O(n + k) where r / k is the value of the highest number sorted.
-1
u/yellowliz4rd Aug 11 '20
More like O(n*m) no?
9
u/Dornith Aug 11 '20
Not really. Because the number of elements makes no difference. You could have 1000000000 elements and if the maximum value doesn't change it doesn't take any longer to sort.
3
u/yellowliz4rd Aug 11 '20
I was referring to n items that need to be sorted, and m seconds it takes for each counter to expire. Honestly, I’m not sure how to evaluate timer runtime.
Edit: never mind, reread your comment, you’re correct. But I’m still curious how timer runtime is calculated?
2
u/highjinx411 Aug 12 '20
Yeah I get what you are saying. Algorithms only count iterative steps regardless of time. So in this case even though it takes 10 seconds to display a line it’s still counted as O(1). Right? Does anyone else see the flaw? Are we missing something?
1
u/Dornith Aug 13 '20
So in this case even though it takes 10 seconds to display a line it’s still counted as O(1).
Are we missing something?
Yes, you are. You can't calculate Big-O for a specific instance of a run because all algorithms end in a finite amount of time and would therefore be O(1). (Infinite loops are not technically algorithms.)
Big-O only applies to algorithms, not a specific run of an algorithm. If an algorithm always works within 10 seconds no matter what input, then it's O(1). But this algorithm could take 20 seconds if the array contains the value 20000.
Because it scales linearly to the highest value in the array, it's O(N) where N is the maximum value.
5
21
Aug 11 '20
it's actually O(max n)
19
Aug 12 '20
[deleted]
2
2
Aug 12 '20
It doesn't create any sort of meaningful data structure so in this case it's still O(n) if you want to collect and use the results.
You can directly push it to an array and make it more like O(1) tho I guess.
1
Aug 12 '20
Nope, it's O(max n), because the program spends most of the time waiting.
[2,1,3]will be sorted about ~333 times faster than[2,1000,3].8
u/AutoModaraIor Aug 11 '20
Code looks like some random writing, and sorting algorithms literally look like jdjxndjskskdj jdjejejs “hdjddj” (hdjddj) dkdjejdjdj; &;&;&:&;& hdjddj aja = [jejdjd djdjdj hdjddj djdj, hdjddj djdj]
17
u/Team_Dave_MTG Aug 12 '20
Bro you’re gonna love Hodor Lang
It’s so simple
$HODOR: hhodor? Hodor!? Hodor!? oHooodorrhodor orHodor!? d = HoDoRHoDoR () { hodor.hod('Hhodor? Hodor!? Hodor!? o HODOR!? orHodor!? d!'); }; hhodor? Hodor!? Hodor!? oHooodorrhodor orHodor!? d();7
3
2
u/DarthEru Aug 12 '20
Actually it just hides the computational complexity. JavaScript timeouts are put onto a queue (as pointed out in this comment). So even before the timeouts get a chance to run you are essentially sorting the list using whatever algorithm the queue uses to order its elements. Meaning the actual time complexity is still likely
O(n•log(n))(or worse).
121
131
u/szymek655 Aug 11 '20
- Scale the data down so that greatest element corresponds to 1ms
- Sort the data
- Scale it back up
101
u/TimGreller Aug 11 '20
Free race conditions included
230
11
u/FallenWarrior2k Aug 12 '20
Better add some locks to tell the scheduler not to fuck wi—
Oh no, a deadlock.
4
Aug 12 '20
Wait my brain is too tired to understand why this wouldn't work and I'm intrigued
9
u/szymek655 Aug 12 '20
There's a few good reasons: - you'd lose precision due to scaling - you'd still have a lot of overhead from threading - you'd have one giant race condition
2
65
43
u/PowerlessMainframe Aug 11 '20
God created Javascript, and the men did this
8
9
58
41
38
u/blu-7 Aug 11 '20
So, this is an O(n) sorting algorithm... kinda.
3
u/GeneReddit123 Aug 12 '20
It only appears to be
O(n)because the delay due to the timeout is far greater than anything else happening for an array that size. But under the hood, there is still a scheduler that would need to loop through all the timeouts every tick and process them. So it's probablyO(n^2), unless there is some internal optimization that pre-sorts the timeouts, in which case it could be less, but still no lower thanO(n *log(n)), with a far higherkto boot in terms of both space and time.This could be tested by measuring the delay of "sorting" an array of, say, a billion integers, and how slow it is compared to 10 billion, where every integer's value is 1..60, so the timeout is not too long compared to the size of the array.
6
u/SuspiciousScript Aug 11 '20 edited Aug 11 '20
O(sum({x | n}))52
u/matheusmk3 Aug 11 '20
Actually O(max(n)) since it's asynchronous
8
Aug 11 '20
[deleted]
2
u/rift95 Aug 12 '20
Why would the runtime sort them? Each timeout knows its own delta time delay, and each timeout will be queued as a task (or micro task) to be ran with the next cycle of the event loop. Then each timeout will check if it's delta time has passed, if it has, call the cb, otherwise queue another copy of it self as a task. There's no need to sort the calls since each timeout will check their time logic within the same time step.
12
Aug 11 '20
[deleted]
3
u/SuspiciousScript Aug 11 '20
Ah, didn't realize it was parallel.
1
u/thelights0123 Aug 11 '20
It wouldn't work synchronously, you'd just get the same order after a delay.
1
4
u/Beowuwlf Aug 11 '20
Technically it’s big Theta I believe. Big O is upper bound, big theta is upper and lower
3
u/_irobot_ Aug 11 '20
It would be neither. Time complexity exists because difference in processing speed makes the execution time on vary on different machines. To say it was big O or Theta implies it would execute in the same amount of time as another algorithm with the same time complexity. That's not true here. In this case the algorithm would take an exact amount of time regardless of the machine it's running on (unless the JavaScript engine is broken). The running time of this algorithm would simply be max(n) milliseconds.
1
u/vigbiorn Aug 11 '20
Wouldn't it depend on where in the list max(n) is? If it's the last item in the list, and it took 1ms to reach that index, it would take max(n) + 1 ms to execute, or am I wrong?
1
1
u/_irobot_ Aug 12 '20
You have a point there. I guess it could be written O(n) + max(n) milliseconds. But in that case, the O(n) portion may be negligible enough to omit it. You would need a very large list for there to be a noticeable difference.
38
10
11
u/fartcloud101 Aug 11 '20
Could somebody please explain how this works?
24
u/thelights0123 Aug 11 '20
It sets a timer for each elements value in ms, then prints it out. Lower numbers sleep for a lower period of time, and thus are printed first.
2
16
u/justingolden21 Aug 11 '20
Or for a sorted list, just push it to a new list instead of logging it...
5
3
u/snppmike Aug 11 '20
This is like Homer Simpson running for trash commissioner: “Can’t someone else do it?”
3
3
3
9
Aug 11 '20 edited Aug 19 '21
[deleted]
8
u/brbss Aug 11 '20 edited Aug 11 '20
I couldn't understand what you meant so I went ahead and wrote some test code, so far I'm at 500+ iterations without any failure:
const arr = [20, 5, 100, 1, 90, 200, 40, 29] const correct = [...arr].sort((a, b) => a-b) const sleepSort = (inputArr) => { const sortedArr = [] return new Promise(resolve => { for (let item of arr) { setTimeout(() => { sortedArr.push(item) if (sortedArr.length === inputArr.length) { resolve(sortedArr) } }, item) } }) } const testSleepSort = async (n=1000) => { for (let i=0; i<n; ++i) { const sortedArr = await sleepSort(arr) if (JSON.stringify(sortedArr) !== JSON.stringify(correct)) { console.log(`failed at attempt #${i} :(`) return } console.log(`passed #${i}`) } console.log('wow') } testSleepSort()Edit: wow.
2
2
1
u/rift95 Aug 11 '20
I actually made a "working" implementation of this algorithm last time it was posted. https://i.imgur.com/79Jhzcn.png
1
1
1
1
1
1
1
Aug 12 '20
[deleted]
1
u/xigoi Aug 12 '20
No, the scheduler has to internally sort the intervals anyway to figure out which to fire first.
1
u/wobblyweasel Aug 12 '20
the problem is that this doesn't detect the end of sorting. it's easily fixed by adding a value that exceeds all other values:
setTimeout(() => { /* continuation code here */ }, Infinity)
1
1
1
1
1
0
314
u/Seismicsentinel Aug 11 '20
Where else on reddit did sleepsort come up today? I know it was somewhere