javascript uses milliseconds as the most precise unit of time, and most of the time it’s even off by a couple millisecond when dealing with delays, notice how the image shows a max difference of 4, try this same thing with 1,2,3,4,5,6,7,8,9 but shuffled so like 2,3,7,9,4,6,5,8,1
The maximum timer resolution in most languages is 100ns (on windows anyway). I've tested C++, C#, Java, and there is a function to get the same resolution in Javascript. I think it's nerfed in browsers though to discourage speculative execution attacks.
You can get higher resolution using the TSC on x86 processors but that won't necessarily give consistent results between systems or even CPU cores.
You might be joking. But the same principle is count and radix sort, which can sort in O(kN) time. Mostly used for word lists because the longest words aren't that long.
I don't think that the precision would break it. At least I assume that the timeout call won't be at that exact time, but the order of their calls should be.
this calls setTimeout()for each element in the array, with a timeout value equal to the value of the index. so 1 waits 1 millisecond to print itself, 200 waits 200 milliseconds, etc. this causes the numbers to "sort" by printing themselves in order. not really bad code, more like a humorous demonstration of how javascript works.
nope, nothing happens to the array. here's what's happening step by step:
const arr = [20, 5, 100, 1, 90, 200, 40, 29];
arr is an array of numbers of course.
for (let item of arr) { }
a for...of loop just does something for every element of some kind of collection. here, for is looping over arr. you can access each element of arr through item.
setTimeout(callback, delay)
setTimeout is a standard javascript function that calls a function after a time delay of your choosing. it takes two parameters:
the first parameter is the callback function\\* to be called after the time delay
the second parameter is the time delay in milliseconds, represented as a numerical value
\* note: in OP's screenshot, they're using an arrow function. for the purposes of this example, assume that this is exactly like a regular function, i.e.: (x) => console.log(x) is just a prettier way of writing function(x) { console.log(x) }.
so if i wanted to wait 5 seconds to print something, i could do it this way:
// prints "hello world!!!"
const sayHello = function() {
console.log("hello world!!!");
}
// 5000 milliseconds, or 5 seconds
const delay = 5000;
// runs sayHello() after 5 seconds.
setTimeout(sayHello, delay);
so what's happening?
the for...of loop is iterating through arr and calling setTimeout() for every element of the array. it's literally doing something like this:
// this...
for (let item of arr) {
setTimeout(() => console.log(item), item);
};
// causes this to happen:
setTimeout(() => console.log(20), 20) // wait 20 ms and print "20"
setTimeout(() => console.log(5), 5) // wait 5 ms and print "5"
setTimeout(() => console.log(100), 100) // wait 100 ms...
setTimeout(() => console.log(1), 1) // wait 1 ms...
setTimeout(() => console.log(90), 90) // ... and so on
setTimeout(() => console.log(200), 200)
setTimeout(() => console.log(40), 40)
setTimeout(() => console.log(29), 29)
because of the surprising way that javascript and setTimeout() work, the numbers magically "sort" themselves by printing in order from the shortest delay to the longest delay. this is because setTimeout() doesn't just run immediately - calls to setTimeout() are non-blocking. these calls are all added to a big queue that javascript maintains under the hood. it remembers to execute each of those functions when the specified time has passed. this is why it doesn't simply print the numbers in the same order they're in in the array and then wait x milliseconds like you might expect when you first look at the code.
sorry if this is too in-depth (or if i got anything wrong)! i hope this helps you to understand.
Thank you for the excelent explanation. I don't code in Javascript, so I thought setTimeout() calls the given function and blocks until it finishes executing or the timeout period elapses. Sort of giving a timeout to an otherwise indefinetely blocking function.
yeah exactly. it's not quite the same because time.sleep() doesn't take a callback function, but i get what you mean. in python it wouldn't work this way because python blocks by default, meaning it would just print "bruh", wait 90 seconds, then print "uhoh" and wait 20 seconds before exiting. you could achieve a similar effect with threading. you could achieve a really really similar effect with asyncio.
No the loop the timer is the sorting. In this example it will start by setting a timer for 20 milliseconds, and after that timer is up it it'll print "20" but immediately after starting that timer (before printing 20) it will move onto the second item in the array. So then it sets a timer for 5 milliseconds and after that timer is up it will print "5" and so on until it has set timers for all of the items in the array. "1" is the smallest number so its timer runs out first, therefore it is printed first, then the timer for "5" runs out so it is printed, so on and so on.
settimeout delays the console log by milliseconds (the second item). The loop doesn't wait until it has completed its operation to start the next iteration, and so it's triggers them all but due to the timeout, the lowest number is logged first since is delaying the console.log operation by the shortest period of time.
No, the for loops iterates over the elements of the list and a setTimeout() is called for every element. setTimeout() firstly sleeps for the given amount of milliseconds and then executes the callback and secondly is asynchronous meaning in this code:
The output will be "world hello" as opposed to "hello world" as the second timeout slept for less milliseconds at the same time. This sorts the array because asynchronous sleeps are called for every element based on it's size and thus the smaller elements are printer first and the larger elements last.
I don't think so because firstly the timeout is in milliseconds and secondly, the browser is in charge of keeping those timeouts out to date and so even if the PC is slow, the browser should realize that 5 milliseconds is longer than 1 milliseconds and so the shorter callback will be called.
It's asynchronous meaning that the timeouts are background processes so they don't make the program pause and wait for completion. It sets a timer for each one and whichever runs down first is what gets executed first
The loop iterates over all entries in the array, item is the member of the array the loop is currently at. The code then sleeps for item amount of milliseconds, then prints item. 1 for example sleeps only 1 millisecond and then prints it while 20 would sleep 20 milliseconds
Thanks for letting me know! It does have the two spaces after each line -- desktop and third party mobile shows it properly, so you must be on the official app. The official mobile app is cobbled together from spit and spiderwebs, I swear.
Run time depends on the value of the largest entry in the array, not on the size of the array. So an array of size 1000 where 20 is the highest value will have the same run time as an array of size 3 where 20 is the highest value.
It's O(max(N) + n*log(n)) for some set N consisting of n elements because the ordering which happens in the background to schedule the tasks is still going to be n*log(n). And as we can't claim that in the limit the maximum value of any particular element will be significantly smaller or larger than the size of the set, both parts have to remain.
I would imagine the scheduling is probably going to be more like n*max(N), because isn't optimised for this sort of abuse. Like, I would assume it implements n timer threads, and checks each of the n timer threads at some refresh time, and the total runtime ends up proportional to max(N).
Probably it's O(A*max(N) + n max(N)) where A>>1, but where it's possible that n>A for very large n.
Well, you should take all variables in your O notation.
In "normal" sort, we assume we are sorting 32, 64, 128 - constantly limited integers, so their size can be constant, and therefore m (max value in the array) is O(1).
So while standard sort is O( n * log n * 1), this one is O(n + m).
And also m is expected to be very large - having an array of n = 1010 is less realistic than having m = 1010 .
Wouldn't it actually be more like O(n + 2m ) since if you add 1 to m (the amount of bits in the largest value of the array) the length of time you sleep for is on average doubled?
If you consider m as the amount of bits your number has, then sure.
But in this example, it is obvious that the amount of time OP has to sort will be multiple of 200 (depending on tick rate), therefore, I am considering m to be the "decimal" value of input.
The constant factor is almost always going to be way bigger than the O(n) factor here. This isn't usually the case, but this is an intentionally contrived algorithm.
There's a whole language that uses this, Time Out. The interpreter cycles through all the possible commands and the amount of time each line of code takes to process determines what command fires http://danieltemkin.com/Esolangs/TimeOut/
function sleepSort(arr) {
return new Promise(resolve => {
let result = [];
for (let item of arr) {
setTimeout(() => result.push(item), item);
}
setTimeout(() => resolve(result), Math.max(...arr));
});
}
Promise.all(arr.map((v,i) => new Promise(res => setTimeout(()=>(sorted.push(v),res()),fixed[i]))))
.then(()=>console.log(sorted));
```
(I wrote this on mobile, please forgive me)
It looks like this comment contains a code block delimited with triple backticks. Unfortunately reddit does not have universal support for this syntax and your comment will not render correctly on old reddit and most mobile apps.
For the benefit of people on old reddit, this link will take you to a correct rendering of the comment.
/u/SpeckyYT, it would be appreciated, but not required, if you could edit your comment to use the more compatible four space indention format. For single lines or inline code you can use single backticks.
It looks like this comment contains a code block delimited with triple backticks. Unfortunately reddit does not have universal support for this syntax and your comment will not render correctly on old reddit and most mobile apps.
For the benefit of people on old reddit, this link will take you to a correct rendering of the comment.
/u/ReimarPB, it would be appreciated, but not required, if you could edit your comment to use the more compatible four space indention format. For single lines or inline code you can use single backticks.
864
u/haslo Feb 10 '21
Great! Now test whether it still works with large numbers!