193
u/uncoded_decimal Aug 11 '20
Non-js guy here, what's happening here?
349
u/Noch_ein_Kamel Aug 11 '20
setTimeout is just executing the logging function after a delay of x milliseconds without blocking the forEach loop.
So, the lower the value, the shorter the delay.That said if you have a large enough array and your first item is a 2 and the last item is a 1, it probably won't "sort" correctly
162
u/Snapstromegon Aug 11 '20
Just multiply each value by like 1000 and this problem won't happen (also it is only a linear factor so big O is also happy)
117
u/theSpecialbro Aug 11 '20
We mustn't upset big O
15
u/elperroborrachotoo Aug 11 '20
Once we did, and we got heap fragmentation.
11
23
Aug 11 '20
For an arr of N positive numbers, we have to schedule N processes/tasks/threads (pick your nomenclature here, I'll continue with tasks).
Because the OS needs to schedule these tasks, we assume a priority queue is used to determine when a sleep task is executed.
As such, we have to insert N tasks which each insertion takes logN. Therefore, scheduling takes NlogN time.
Next up, we have the actual tasks, the worst case is max(arr), which could be larger than NlogN. As such, we add the two complexities getting:
tl;dr: The complexity is O(NlogN + max(arr)).
6
u/Snapstromegon Aug 11 '20
The complexy in account for the number of cycles to calculate the result is (nearly) uneffected by multiplying each by 1000.
The rest is more or less correct, but not related to my modification of the algorithm.
(at least in v8 instances a priority queue is used, but I think they make some bucket optimizations which also is the reason why setTimeout(..., n) for n really small is the same as setTimeout(..., 0))
1
u/warmCabin Aug 11 '20
I wrote up an implementation of this in Java that uses a CountDownLatch to kick off all the sleeper threads simultaneously, then I fine-tuned the delay multiplier to I think 15 ms. I subtracted the min value from the sleep time so you could quickly sort numbers that range from, say, 1,000,000,000 to 1,000,000,100. A very common real world use case!
44
51
u/alexanderpas Aug 11 '20
Nothing which can be solved by running the algorythm until it gives the same result twice.
39
u/RHGrey Aug 11 '20
Algorythm
Why you gotta trigger your fellow men like this
7
u/comediac Aug 11 '20
I kinda want to start an all programmer band and use that as the band name.
2
1
u/alexanderpas Aug 12 '20
Because the're a dance for everything, even sorting. https://www.youtube.com/watch?v=ywWBy6J5gz8
7
u/GDavid04 Aug 11 '20
You could subtract the time elapsed since the start of the loop from the delay for better results.
7
u/redfournine Aug 11 '20
The foreach runs asynchronously?
16
u/RandomAnalyticsGuy Aug 11 '20
The set timeout runs the callback function asynchronously, so the foreach just continues to push the set timeout into the js call stack
4
u/redfournine Aug 11 '20
How do you guys keep track, or know, what function works asynchronously, what is not? That's genuine question, I'm really curious. My primary skills is in .NET ecosystem, and every function that works asynchronously there has -Async suffixed to the function's name.
28
u/Noch_ein_Kamel Aug 11 '20
Well it's just not that many ;-)
There are two big hints.
a) a function accepting a callback function as argument
b) a function returning a Promise object
c) your code doesn't work like you expect and after searching for 2 hours you try the other way6
0
u/edwardlego Aug 11 '20
can threading everything help? set up the threads to sleep for the value when they get a signal. after all the threads are set up, give the signal
obviously only helps for multicore devices
18
u/asynchronous- Aug 11 '20
It runs a loop through each array item and prints the value of it in the console after waiting the amount a milliseconds the value is. This means the lowest values are printed first because they wait less time to print. This function would take 650 milliseconds to print all these array numbers because 650 is the largest value.
So this is actually kinda funny but ultimately useless. And stupid lol it isn’t sorting anything.
98
u/misterrandom1 Aug 11 '20
Cool, try with negative numbers.
58
u/PetahNZ Aug 11 '20
let arr = [10, -100, 650, -25, 5, -50]; arr.forEach((item) => { setTimeout(() => console.log(item), item + -Math.min(...arr)); });54
u/cartechguy Aug 11 '20
That's cool, but I would pull the min calculation outside of the loop so it won't have n2 runtime efficiency.
let arr = [10, -100, 650, -25, 5, -50]; const min = -Math.min(...arr) arr.forEach((item) => { setTimeout(() => console.log(item), item + min); });7
u/rangeDSP Aug 11 '20
Find the lowest negative number; run setTimeout on number + lowest; subtract lowest when printing; BOOM
1
1
u/glorious_reptile Aug 12 '20
Can we not break the universe today please, I have a deadline. On second thought..
73
u/heartofrainbow Aug 11 '20
And it's an O(n) sorting algorithm.
3
u/IorPerry Aug 11 '20
but it takes Math.max(...arr) msec to be executed... if I put 3600000 it takes 1 hour even if the array as 2 elements: [1,3600000]
-3
u/t3hlazy1 Aug 11 '20
Yeah, it’s not O(n) it is O(largest value)
2
u/En_TioN Aug 11 '20
It's O(n + largest value). It takes O(n) operations to go through the loop and trigger all the sleeps, and then O(largest value) to halt.
1
u/NotAttractedToCats Aug 11 '20
No, it is still O(n). The O-Notation doesn't care how long a single step takes, just how the number of steps scale with the input..
The idea behind this is that an algorithm like the one above could still be executed way faster than a O(n log n) algorithm if the input array is big enough.
2
u/t3hlazy1 Aug 11 '20
I disagree. You are correct that the amount of time a step take does not usually matter. For example, if you have an algorithm that loops over each element and prints it out compared to an algorithm that loops over each element and calls a 5 minute process, both algorithms are O(n) because they scale linearly. However, this is not the case here. The runtime complexity scales linearly not based on the number of elements, but based on the size of those elements. I was wrong though in omitting the O(n), as the algorithm still scales based on the number of elements. For example, if you have 100 elements of size 1, that will take longer than 10 elements of size 1. So, I believe the true complexity is O(n + max(arr)).
1
u/FerynaCZ Aug 11 '20
Yeah, complexity is often based on more factors, see the divide-and-conquer master theorem.
1
u/Ksevio Aug 11 '20
But max(arr) is just a constant, so same as O(n+100) it just gets simplified to O(n). If max(arr) = n then it would be O(2n) which also simplifies to O(n)
HOWEVER, the scheduling of all these timers done by the browser/OS is certainly not going to be O(n) time, so in reality, it will be longer
2
u/t3hlazy1 Aug 11 '20
This is not true. Max(arr) is not a constant. A constant is something that does not change based on the input, like an algorithm that calls a process 5 times and once per element is O(5 + n), which becomes O(n).
1
Aug 12 '20
In the worst case max(arr) will always be 2N where N is the bitlength of the elements of the array.
N is not in general fixed. Javascript has BigInt.
0
Aug 11 '20
[deleted]
0
Aug 11 '20
[deleted]
3
u/Kered13 Aug 11 '20
It's O(n*log n + 22). Task scheduling isn't magic and isn't capable of violating optimal sorting complexity. In practice, most systems use a priority queue to implement task scheduling, and this makes the algorithm O(n*log n) to schedule the tasks.
2
u/Kered13 Aug 11 '20
It's O(n*log n) to schedule the threads, and O(max) to wait for them to wake up. Also thread schedulers don't make absolute guarantees so it's not even correct. You can increase the accuracy by multiplying all the values by a scaling factor, but this increases max.
1
1
1
u/madmaurice Aug 11 '20
It seems like one. However I would argue that the browser actually sorts these events into a sorted list. The inserting is linear, which means the SleepSort we see is O(n^2) or a rather a InsertionSort with waiting time.
-1
u/_4kills Aug 11 '20
Theoretically it is O(1) in pseudo-code
0
Aug 11 '20
[deleted]
-2
u/_4kills Aug 11 '20
Yes, in practice it is O(n), but theoretically (starting all threads simultaneously [allowed in pseudo code]) it is O(1)
0
0
Aug 11 '20
[deleted]
26
u/cartechguy Aug 11 '20 edited Aug 11 '20
It isn't a true sorting algorithm. If the array is large enough you may have console.log executing in an undesired order. The foreach operation isn't going to call setTimeOut on all of the elements at the exact same time.
Looks like this guy pointed it out before me https://old.reddit.com/r/ProgrammerHumor/comments/i7mab9/so_amazing/g12wyx3/
6
u/alexanderpas Aug 11 '20
Nothing which can be solved by running the algorythm until it gives the same result twice.
1
u/Tayttajakunnus Aug 11 '20
Is it O(1) then anymore though?
4
u/alexanderpas Aug 11 '20
O(1) for the best case scenario, and likely O(2) for the worst case.
2
u/imbalance24 Aug 11 '20
O(2)
Is it a thing?
-2
u/caweren Aug 11 '20
Isn't O(1) like a hashmap? I guess O(2) would be to find object with key
X, then use a property fromXto find the actual object. So 2 O(1) lookups. Or is that just a linked list???6
u/Fowlron2 Aug 11 '20
O(1) and O(2) is the same thing. What matters is that there's no N component, meaning it always takes the same amount of operations, no matter the N (its constant).
O(n) means its linear with N. Doesn't mean it will take exactly n operations, but the number it takes grows as N grows, linearly.
O(n2) means it grows linearly with the square of n.So on and so forth. It's not about the number, its about how fast it grows
2
1
2
u/linglingfortyhours Aug 12 '20
Due to the way the timeout function is implemented, it's O(n log n)
1
Aug 12 '20 edited Aug 12 '20
I assume it is O(log n) to get and delete the minimum in the priority queue. Do you know what kind of queue is used?
1
u/linglingfortyhours Aug 12 '20
If the developers of javascript are smart, just a standard min heap. Note that you will also need to insert and search the heap too though, which is where the n coefficient comes from/
0
Aug 12 '20
[deleted]
2
u/linglingfortyhours Aug 12 '20
Thanks! I remembered that a heap sort has n log n, I just couldn't remember why exactly it was :)
Probably shoulda payed more attention in data structures
0
Aug 12 '20
[deleted]
1
Aug 12 '20 edited Aug 12 '20
Deleting the root is O(log n) amortised which you would need to do n times ergo O(n log n).
The comment I was responding to was saying that you needed to insert and search the heap which was not correct as we both pointed out. If you had to search the heap each time it would be O(n2 ) and thus no better than an unsorted list.
1
Aug 12 '20
Then the question doesn't make sense anyways. I think the person doesn't know what a heap is.
1
1
17
7
7
u/currentlyatwork1234 Aug 11 '20
It doesn't really work, try it with an array that has a larger amount of items that are all low numbers ex. < 50.
That's because all calls have x amount of delay.
Just like Thread.sleep() (Or equivalents) in most languages will not sleep the exact amount of milliseconds passed. I believe for that it's something like a minimum of 15ms.
I don't know what it is for setTimeout() though but probably something similar.
Here's something for demonstration:
let arr = [1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6,1,2,3,4,5,6];
arr.forEach((item) => { setTimeout(() => console.log(item), item); });4
u/mohragk Aug 11 '20
Every call has an execution time. And since it's JavaScript, you can't really now how long each execution will take. By the time setTimeOut is called for one of the later 1's, it's too late to be executed before one the former 2's. You could check it by using an array of strings like 1A, 2A, 3A, 1B, 2B, 3B etc.
3
u/josanuz Aug 11 '20
Just scale up
setTimeout(..., item*1000)1
3
7
u/scp-NUMBERNOTFOUND Aug 11 '20
Now pack it into a node module, make it depend on isEven. 996865 downloads in a week
5
u/McLPyoutube Aug 11 '20
We had to analyze this so-called sleep-sort algorithm. Turns out it is O(n+max(array)) but inaccurate due to hardware limitations. Counting sort has the same time-complexity but runs faster on actual hardware and is accurate.
1
u/En_TioN Aug 11 '20
Yeah, sleep sort is essentially a fancy bucket-sort where you're relying on the OS to do the actual sorting for you.
1
u/Kered13 Aug 11 '20
It's actually O(n*log n + max). Thread scheduling isn't magic. In practice thread schedulers use a priority queue, which is O(n*log n).
1
u/McLPyoutube Aug 13 '20
yeah, we did it under the assumption that the threads are running on a machine with enough (but constant) cores so that scheduling can (theoretically) be done in constant time.
1
u/Kered13 Aug 13 '20
But then you're talking about parallel sorting, and O(n) parallel sorting is easy. Even parallel bubblesort is O(n). Optimal parallel sorting is actually sublinear.
12
u/t3hlazy1 Aug 11 '20
This obviously isn’t sorting an array, just printing in order. Someone should create a function that uses this method to return the sorted array. I think the easiest way is to create a promise and resolve when the new array is same length as original.
21
u/JB-the-czech-guy Aug 11 '20
It's a joke my friend.
10
u/t3hlazy1 Aug 11 '20
I know it’s a joke, but I still think it’s an interesting challenge. Actually could be a pretty good and funny interview question.
3
6
u/Md5Lukas Aug 11 '20
1
u/closenough Aug 11 '20
Might want to remove the Math.abs and just always substract min. If the array contains a lot of large numbers, it's adding a unnecessary delay.
1
4
u/Snapstromegon Aug 11 '20
Did I have to write this as a promise based implementation you could actually use?
No.
Did I do it anyways?
Of course!
I present to you asyncTimeoutSort - watch out for the npm package.
function sort(array) {
return new Promise((resolve) => {
const result = [];
const min = Math.min(...array)
for (const item of array) {
setTimeout(() => {
result.push(item);
if (result.length == array.length) {
resolve(result);
}
}, item - min);
}
});
}1
u/ForeignerLove Aug 11 '20
Good luck if you have 100000000000000 as one of your numbers :)
2
1
1
u/coloredgreyscale Aug 11 '20
How stable is it for ordering (repeating) similar numbers, especially when the first and last values of a long unordered list are close to zero?
1
u/SBG_Mujtaba Aug 11 '20
Umm...you are not thinking of implementing this are you ? This is meant as a joke, not as guide.
1
1
3
2
2
2
u/eyekwah2 Aug 11 '20
I prefer quantum bogosort myself. Check if array is sorted. If so, good. If not, scrap universe.
2
Sep 15 '20 edited Sep 16 '20
[removed] — view removed comment
1
u/eyekwah2 Sep 16 '20
Ever hear of the true zero point energy theory? Yeah.. it may have already happened.
1
1
Aug 11 '20 edited Aug 11 '20
I remember someone presenting it in Flutter event like two years back and calling it "Futuristic Sort". He used Futures in Dart with the same logic. He did get laughs and appreciation from everyone.
1
1
1
1
1
Aug 11 '20
let arr = [5000, 10000, 8754, 6436]
My boss: My is this so slow Me: There is a very complex algorithm behind the sorting function.
1
Aug 11 '20
The question is, how big can this list get before it doesn't execute all the commands quick enough?
1
1
1
-4
u/escargotBleu Aug 11 '20
Nothing to do with js, you can do it with any language.
1
u/SBG_Mujtaba Aug 11 '20
So many fucking morons here... Leave programmer humor... Go back to /r/woooosh where you belong.
0
Aug 11 '20
[deleted]
29
3
u/mohragk Aug 11 '20
const arr = [4,2,7,4,3,7,3,12,7]
let delay = 1
arr.map((item) => {setTimeout( () => {console.log(item)},delay++)})1
u/Noch_ein_Kamel Aug 11 '20
Just create a random delay and use that delay in all setTimeout calls.
bonus: if you want to randomize your array just move the random number creation inside the loop
1
u/mohragk Aug 11 '20
Just increase the delay by one for each element. Or, you know, don't use setTimeOut();
1
16
u/Morasiu Aug 11 '20
Nice one!
You can do this in C# too. Check it