7 ms·
Need Something Sorted? Sleep on It
- klyrs 5y ago> Sleep sort is an O(N) sorting algorithm for non-negative integers. No, it is not. It's O(N+M) where M is the largest value in the list. And, notably, it can fail if the time to schedule the jobs takes longer than the smallest difference between elements in the list
- raymondh 5y agoAlso, sleep() just delegates the sorting responsibility to a scheduler which likely uses on O(log n) heap algorithm to identify the next scheduled event.
- rileymat2 5y agoThis is taking it too seriously. It is just something different. To quote the article > Bonkers, brilliant and definitely NSFW.
- EquallyJust 5y agoHashed hierarchical timing wheels is a cool very specialized data structure to make this efficient. The paper claims it's O(1) to start, stop and maintain timers which is much more efficient than O(log n). Given there's n timers and O(1) operations I'm not sure where the O(n log n) fits in here. Possible in the minimum number of ticks? http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing... Production implementation: https://github.com/facebook/folly/blob/master/folly/io/async/HHWheelTimer.h https://github.com/facebook/folly/blob/master/folly/io/async...
- klyrs 5y agoProbably this bit from section 5 > If we can guarantee that all timers are set for periods less than MaxInterval, this modified algorithm takes O(1) latency for START_TIMER, STOP_TIMER, and PER_TICK_BOOKKEEPING. I think that puts this in the same class as counting sort.
- sly010 5y agoThe paper says it's essentially bucket sort. Which was also my thirst thought when I heard about sleep sort.
- deleted 5y ago[deleted]
- BearsAreCool 5y agoWith a linear time O(N) first pass you can identify the minimum element in the list. This reduces M from being the largest element to being the difference between the largest and the smallest element.
- rileymat2 5y agoIf we are playing with this, why not take one pass to find the largest element, then another pass to divide each element in the list by that number, leaving it 3N+M/M. Edit: Why divide by m, when you can divide by M*C. Where C will speed this portion up by a factor!
- david_allison 5y agoLet's do better. You can find the largest element in a list in O(1) time with n^2 processors[0]*. Division of the list by that number is O(1) with n processors Therefore the operation is O(1) [0]* on a CRCW PRAM https://www.cpp.edu/~gsyoung/CS535/CS535Notes/Part2PRAM.pdf#page=1 https://www.cpp.edu/~gsyoung/CS535/CS535Notes/Part2PRAM.pdf#...
- lupire 5y agoYou're ignoring communication overhead.
- smitty1e 5y agoGiven the title, I expected praise for the nap as a problem-solving tool. Seriously. How many times have you crashed out on a knotty problem and awakened with a clear solution? Glad that my superpower remains secret.
- lostlogin 5y agoOr the opposite - you wake up and the massive problem is just not that big of an issue and isn’t yours to solve. Leave it alone.
- koolba 5y agoIf you sleep long enough and the problem is important enough, someone else will solve it.
- perl4ever 5y ago"The Fastest And Shortest Algorithm For All Well-Defined Problems ... An algorithm M is described that solves any well-defined problem p as quickly a the fastest algorithm computing a solution to p, save for a factor of 5 and low-order additive terms." https://www.researchgate.net/publication/220180215_The_Fastest_and_Shortest_Algorithm_for_All_Well-Defined_Problems https://www.researchgate.net/publication/220180215_The_Faste...
- YeGoblynQueenne 5y agoOne day, the Ancients will awake, very concerned. "Have you still not migrated to the stars? What's blocking you?".
- glial 5y agoOr the opposite of that - you conveniently forget about a dilemma, only to wake in the middle of night in a cold sweat thinking about it.
- scsilver 5y ago
- girvo 5y agoThere is a class of programming languages or execution environments that the name escapes me at the moment, where the "time" variable/dimension is explicitly woven into it as a first-class (and _really_ first class, it drives the rest of the system) element. But I cannot remember what it is, and I'm likely explaining it badly. It had some neat algorithmic or type-level properties too, I believe, and I remember seeing it in context to modelling truly real-time systems. Does anyone know what I'm talking about? Or is my memory finally deciding to make things up, whole-cloth! Edit; found it with the help of the commenters below! https://en.m.wikipedia.org/wiki/Synchronous_programming_language https://en.m.wikipedia.org/wiki/Synchronous_programming_lang...
- Shoop 5y agoFunctional reactive programming?
- girvo 5y agoNot quite but was close enough to get me on the right path! https://en.m.wikipedia.org/wiki/Synchronous_programming_language https://en.m.wikipedia.org/wiki/Synchronous_programming_lang... Synchronous programming was the term I was thinking of: the concept of logical ticks being first-class in the programming language itself is what SleepSort reminded me of :)
- garmaine 5y agoHard real-time operating systems?
- dls2016 5y agoErlang?
- sabalaba 5y agohttp://chuck.stanford.edu/ http://chuck.stanford.edu/ Another interesting one is Chuck, a strongly-timed language. :) Useful for making musical programs.
- 5y ago
- kumarvvr 5y agoMy superpower is to take a good long walk. No music, No phone, no distractions. Walking helps my brain juices flow.
- beebeepka 5y agoThis also works for me. It helps if there aren't m/any people on my wall path. We humans are very loud in groups On a personal note, these days I find listening to music outside off-putting and potentially rude and/or dangerous in a city environment. All that said, a good night's sleep works wonders for both body and mind
- scbrg 5y agoThat's great for your... uh... juices, I suppose, but what about the list of unsorted integers? ;)
- rflrob 5y agoMy first CS teacher talked about what he called Bang Sort, which is also O(n): 1. For each entry in your list, cut a straw of length proportional to the value to be sorted 2. Take all your straws in a bundle 3. Bang them gently on a flat table 4. Draw out the straws in order of length, each operation of which can be done in O(1) time
- solipsism 5y agoThe energy and space required are O(n) though.
- hibbelig 5y agoGiven that storing n items in an array or a similar structure requires O(n) space, the space requirement of bang sort seems normal. Perhaps by making use of the Oracle of Delphi, you could do away with the array. Also, the energy requirements... Wouldn't they be proportional to the number of operations required, i.e. the time complexity?
- deleted 5y ago[deleted]
- tsimionescu 5y agoThe more straws you have, the harder it becomes to discover the largest one, and to actually pick all of them up and bang them. At some point you will likely end up foul of fundamental limits related to mass and energy and the speed of light, and that limit will probably come well before 2^32 elements. Edit: This is usually the problem with analog algorithms: you can easily tell apart 100 items, but scale it up and you find you need so much energy to differentiate that you'd collapse into a black hole before successfully measuring the differences.
- MrLeap 5y agoThis reminds me of generating signed distance fields from bitmaps by rendering a cone at every target pixel with a vertex color of white at the point and black at the base. I like the method because not only is it silly, it's also very easy to do on GPU and good enough so I actually have used it in real products.
- dhotson 5y agoThis reminds me of a clever hack I learned for finding bottlenecks when using a debugger or in cases where you're able to get a backtrace from a running program. If you run the program and then just randomly trigger the debugger with CTRL-C.. the probability is that you're likely to have landed on a slow code path because that's where the program is spending most of its time.
- MauranKilom 5y ago...which is exactly how stack-sampling profilers work. They just automate doing this thing (and recording the stack trace) every x milliseconds.
- KMag 5y agoOr, if you have a semi-locked down production box and a process that's already gone unusably slow, a quick shell loop that calls pstack on the slow process 10 times will get you a good idea where the process is spending its wall clock time. (I've seen locked-down environments where pstack can be run, but gdb can't.) Note that pstack will probably take a bit for each stack snapshot it prints. It has to attach as a debugger, walk the stacks, and read the symbol tables each time. It's easy for the whole process to freeze for a second or two, so you probably don't want to do this on a production process that is limping along okay-ish.
- deleted 5y ago[deleted]
- halayli 5y agoit's creative, and funny indeed. From a technical point of view, it's simply handing the problem over to the cpu scheduler. Kind of like touching empty files and naming them in a particular way and doing an ls to get them back sorted. Similar to rc scripts.
- Zababa 5y ago> Possibly the only good thing to ever come out of 4chan, sleep sort was created by an anonymous user in 2011. Another good thing that came out of 4chan in the same year: https://en.wikipedia.org/wiki/Superpermutation https://en.wikipedia.org/wiki/Superpermutation
- intricatedetail 5y agoWhen I have a problem I cannot find a way to fix by the desk, I take a walk, do something else, watch a movie etc. And then at least one solution suddenly come up. It's difficult to maintain this workflow in the office as people think you are lazy and procrastinating. In the office setting, taking the problem to bed and show solution next day is one of ways to go around that.