3 ms·
This reminds me of my favorite joke algorithm, sleepsort[0]. A trivial implementation looks like this: #!/bin/bash for int in $@; do # input must be
by bashinator 7y ago
This reminds me of my favorite joke algorithm, sleepsort[0]. A trivial implementation looks like this:
#!/bin/bash
for int in $@; do # input must be a list of positive integers
(sleep $int; echo $int) &
done; wait
I'm not quite sure how to describe it in terms of big O notation.
[0] https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort
- lann 7y agoIf the sleep is some kind of busy wait then I think it is something like O(m*n) where m=max number. If it is scheduled by the kernel then the complexity is hidden in the scheduling algorithm.
- anonytrary 7y agoIt should remind you of sleep sort, because spaghetti sort is the spatial version of sleep sort. For sleep sort, the time taken is a constant function of the size of the list; it only depends on the value of the maximum element of the list. T = max(list) + smaller terms associated with scheduling timeouts. So, it's O(max(list)). Although, the "smaller terms" I'm ignoring blow up when the size of the list exceeds your computer's resources. I'd guess that spaghetti-sort is O(sum(list)).
- bashinator 7y agoAha so a sleep sort is translating the operation into the time domain In essentially the same way that spaghetti sort translates into the spatial domain! Thank you.
- saagarjha 7y agoIt's psuedo-polynomial: https://en.wikipedia.org/wiki/Pseudo-polynomial_time https://en.wikipedia.org/wiki/Pseudo-polynomial_time. The Linux scheduler is O(n log(n)) if I remember correctly.
- s_gourichon 7y agoAccording to https://en.wikipedia.org/wiki/O(1)_scheduler https://en.wikipedia.org/wiki/O(1)_scheduler > The O(1) scheduler was used in Linux releases 2.6.0 thru 2.6.22 (2003-2007), at which point it was superseded by the Completely Fair Scheduler. https://en.wikipedia.org/wiki/Completely_Fair_Scheduler https://en.wikipedia.org/wiki/Completely_Fair_Scheduler > The fair queuing CFS scheduler has a scheduling complexity of O(log N), where N is the number of tasks in the runqueue. Choosing a task can be done in constant time, but reinserting a task after it has run requires O(log N) operations, because the runqueue is implemented as a red-black tree.
- piterdevries 7y agoSimple optimization sleep $int / $maxIntInList