Sleep Sort
dis.4chan.org
dis.4chan.org
Basically if you transform set L into the time domain, when collecting it back you get it back sorted.
Its a fun result, and as an exercise in systems analysis it can be enlightening to look at the impact of timer resolution, thread creation, and ordering, but ultimately the 'trick' is that you've exploited the 'insertion sort' that the kernel does on sleep events. You could try its close cousin "priority sort" where you create threads where you set the priority of each to be related to the value 'n' of the element, and all fractionally lower than the parent thread (most UNIXes are not that flexible but some realtime OSes are) then as the last step you 'yield' and the threads print out their contents in priority order and poof they are sorted. But again, the sorting happened in the kernel when they got inserted into the runq in priority order.
Also, the Perl 6 one-liner is sort of laughably cute . I'm not sure I believe it would actually work, but if it does, the conciseness of Perl 6 is even higher than I'd realized; dropping about 9 words from the Perl 5 one-liner (which is already very small). But, I learned about the hyper operators in Perl 6, which is also cool: http://perl6advent.wordpress.com/2009/12/06/day-6-going-into...
In short, that was awesome reading over my morning tea.
I don't think any current implementation supports auto-parallelization of hyperops. Regardless, hyper is really only spec'd to remove the result-ordering requirements so that it may optimize it (I wouldn't be surprised if was executed in chunks in slightly more sophisticated implementations.)
So, I think that tiny little implementation is bunk. I'd be curious to see what the actual smallest Perl 6 implementation would look like, or if it would be the smallest Perl 5 version except using "say" to shave off two characters.
That's pretty much what I said.
I'd be curious to see what the actual smallest Perl 6 implementation would look like
If you want to guarantee it will work, then it will be about as long as a Perl 5 version. Every brief way to parallelize leaves a lot of the semantics up to the implementation. There's a good reason for that: this is a concurrent problem, but the hyperops are meant for parallelizable problems.
The side benefit is that it caused me to download a Perl 6 implementation for the first time since pugs many years ago. I probably won't be using it for anything other than tinkering, of course, but nothing wrong with playing with new things. And, YAPC is coming up, so I can hang out with the cool kids who are talking about Perl 6 and Rakudo.
Perl 6 has been making strides lately. There's a bit of a refactor in the wings which should make it much more processor and memory efficient.
If it had the performance (and a package in Debian sources), I would be using it in production right now. Between grammars and the (clean!) syntax support for high order programming, it solves a lot of my headaches.
There are less verbose (but also less well-formed) solutions in these languages. Here's a working, hacky but still readable, 3-line one I just banged out for Erlang: http://pastebin.com/eZckJp9p
HN cut out the middle man. Instead of linking to something on Reddit about 4chan, we finally just linked straight to 4chan.
e: Dang, maybe I should have used a snark mark.
So here's the thing: the chan culture in general can be refreshingly great and diverse in many ways. It has cool, talented, and funny people, including fellow HN members (check out the society meta-boards sometime). I've been there for years, and am even friends with someone who admins a relatively popular subchan.
This is not some ignorant hate-based butthurt religious rant here - and I will gladly eat the signed integers to prove it... my problem with this submission is that part of the chan-sub-culture that 4chan represents and helped popularize, the part that resides at 4chan.org is a culture of desensitivity and inaction with regards to the posting of child porn. It's continually posted and often stays up for hours. It's been this way for years. I go back every once in a while hoping it's changed, but as of last week, it hasn't.
We can argue all day about about moot's level of involvement (maybe pg has a comment regarding founders setting the expectations and social norms of a community?), moderation strategy, it's associated seemingly "positive" effects on society at large (memes, hacktivism, etc.), but those are not the issue. The issue is that by posting this to HN, we are both indirectly via the network effect, and directly via advertising revenue, supporting a community with less than ideal standards relating to the sharing of pictures of sexually abused children. And yes, ad-free text boards count too due to spillover.
Next time just post the story/example or something in a Tell thread, and have the discussion here.
my 0.02$
also, here's an archive img of the linked discussion for those still at work:
From http://imgur.com/faq
Is there a maximum file size I can upload?
The maximum non-animated file size you can upload is 10MB. However, if the image is over 1MB then it will automatically be compressed or resized to 1MB, for better viewing on the net. The maximum animated file size (both GIF and PNG) is 2MB.
edit: formatting
Try using a png optimizer on it first.
I downvoted your whinge about getting downvoted for the following reasons:
(1) meta discussions must die
(2) pretending that upvotes/karma matter is just deluding yourself. Go watch the Southpark episode about internet dollars until you get it
Both mentions were probably more part social commentary than complaint. I mean it was already completely grey, and isn't the whole point of fading out comments so that other people aren't bothered by them? If so then fading out does not work because that comment was downvoted 20+ times. So after the first -4, we had 16 other people highlight the comment, read it, and downvote it. That's a broken system.
And notice I derisively referred to it as a signed integer - that was deliberate because in the great wide universe that is my life, an integer stored in database somewhere is something I care eternally less about than the content of my comments and the realization I hoped to spur...
The link is on HN because of the interesting thread and has nothing to do with what you are talking about.
And it's interesting you asked if we should censor Craigslist, Ebay, and Usenet because NONE of those sites/networks receive any meaningful traffic here.
It would even be easy to imagine ebay and craigslist being blacklisted.
http://news.ycombinator.com/item?id=499044
edit: my team's last startup was an anonymous social network, ala 4chan + Facebook, so please understand that my current position was formed even after spending years of my life in the chans.
Here's the original, but again the links are broke: http://news.ycombinator.com/item?id=707294
E.g. 5,3,2,1,10 makes five threads, one sleeps for one second and prints 1, one sleeps for two seconds and prints 2, one sleeps for three seconds and prints 3, one sleeps for five seconds and prints 5 and the last one sleeps for 10 seconds and prints 10.
Unlike other 4chan boards, posts on /prog/ never die, and there are never any images attached to posts. So not-safe-for-work isn't usually an issue, though it is blocked for a lot of people, including me.
I don't like to wait 218382 seconds to sort '(0 218382)
If you slept exp(n) instead of n it could easily include
negative integers too*!*
Oh shit, we're busted, there's a REALISTICALLY THINKING
PERSON in this thread!The mailto:sage links in some of the posts are essentially public downvotes; from the Japanese "下げ", meaning "down", and pronounced "sah ge".
I always wondered if there was a chan for hackers...now I realize there is. And oh boy, what a chan it is.
Shii personally runs a pretty nice chan called 4-ch[2] with a large and decent DQN[3] textboard. (S)he founded this chan after being banned from 4chan and SomethingAwful. I don't know whether shii still frequents 2ch or Futaba.
I don't consider the English chans online for programming to be all that great. Most (if not all) are textboards with few postings and lots of trolling over the last 3 years. I don't know the state of the huge Japanese ones however, as I do not frequent them or read the language.
[3] 4-ch.net/dqn/
edit:
also, shii doesn't run overchan either--Mohey Pori does
from what I remember, someone DDoS'd it in their war against all imageboards (can't remember who) and shii ended up hosting it
However, here's a different perspective to look at this from: What if this were implemented on an FPGA?
Let's ignore for a moment that the number of gates needed would increase linearly with the size of the input. I'll also simplify the math by assuming that a list of n numbers contains only values in the range [0 .. n] .
Let's further assume that we're only sorting positive integers, and that each job sleeps for x clock cycles (where x in the input number). We could sort a list in O(n) time.
Digging even deeper: Quicksort performs an integer comparison followed by a branch O(n lg n) times. Even if your processor can compare two integers in one clock cycle, a branch is probably going to screw up your processor's pipelining and take quite a few clock cycles to execute. So, we're possibly looking at a significant speed increase even before we consider the difference in order of growth.
So, assuming a predefined upper bound on the number of items in a list, this just might be a great way to perform hardware-assisted sorts.
Thoughts?
Furthermore, the polling circuit would have to poll each of the n tasks n times, leading us finally back to a running time of O(n^2).
Still a fun thought experiment, though.
The problem is that sorting networks need to be designed for each input size, and designing efficient sorting networks is an open problem. There has been some work in the evolutionary computing community on sorting networks, and some of the best known networks for various sizes were found by EAs, but large networks are still a challenge.
I think on Linux the granularity thing is true for e.g. nanosleep(), but there is also the POSIX clock_*() functions, which I think guarantee higher resolution.
Even if you did that perfectly, it is still only a probabilistic sorting algorithm, with potential for error.
The OS is told to wake up your thread after x time has elapsed. It puts this request into some data structure which it does something like poll from time to time so it knows what thread to wake up at what time. You are offloading your sort to the OS, which is probably then doing something like putting it into a linked list of timeouts that have been registered (maybe a heap?). After approximately the allotted time, some mechanism akin to a signal is used to tell your thread to wake up.
Also, usually the thread will just sleep AT LEAST as long as you tell it to sleep, but if the system is busy it could sleep a long time more. Threads can be woken up at the same time or slightly out of order, or 'woken up' only to find that all the cpu's are working on something else, and thus waiting for a time slice, getting one, then waiting again, and not getting to use stdout for weeks. It's uncommon to see machines with really high load these days, but a 1 core computer with 25000 processes all competing for CPU time, and which is swapping heavily, will potentially run each process millions of times slower than running one process.
TLDR; This is curious, but will fail much of the time, has huge memory overhead. Lots of good sorts are in place, this one requires something like 8mb per thread on linux due to the stack allocated for the thread. At best this takes millions of years potentially, and just does some other sort anyway.
Of course, the kernel isn't going to support more than 64 bits of sleep times any time soon, so it's okay if you want to say it's constant. ;-)
However, if you're using a shared address space and kernel-level threads, you could easily run out of virtual addresses.
We were often quite sad that we couldn't publish some of these gems, they were brilliant.
Usually I get a blank stare. Sometimes I get a great answer.
I guess it's a mix of optimal and pessimistic. Pessimistically optimal ("This may be optimal, but I doubt it") or Optimally pessimistic ("This is absolutely the worst possibly outcome ever") :)
https://secure.wikimedia.org/wiktionary/en/wiki/pessimal
The other time I've seen a similar derivation used is in "The Story of Mel"
'Mel called the maximum time-delay locations the "most pessimum". '
1. Check if list ordered. If it is, we're done!
2. Randomize order of list. Go back to step 1.
N!
Given a uniform distribution over k discrete values (in this case permutations of the list), the expected probability of the next permutation is 1/k. This is not the same as saying that if you take k samples from the distribution, you are guaranteed to receive exactly one of each value. For any finite number n of samples, no matter how large, the probability of getting a given value tends towards 1 as n grows, but it only approaches it asymptotically. While the probability of not seeing any one value from the domain grows vanishingly small as n gets much larger than the number of possible values, it never hits zero. So even with a stochastically random source of list permutations, we cannot place a finite upper bound on a time in which bogosort is guaranteed to terminate.
It gets even worse with pseudorandom number generators — these display cyclical behavior over time (any good one will take quite a while to show it, but they all will), and you might have picked a seed for your PRNG that generates a cycle that never includes the sorted permutation.
So no, bogosort is not guaranteed to terminate. In practice, it has a reasonable chance of terminating for most inputs, and it will do so with an expected (not guaranteed!) runtime in O(n!) for a list of length n.
Now of course, there's infinitely many conceivable scenarios where bogosort never completes, but it doesn't matter. The theoretical foundation (Lebesgue measure theory) to make this mathematically rigid is a bit complex. An example to illustrate:
Assume you have're looking at a 2-dimensional space (over the real numbers) and you want to measure the area of subsets of it. E.g. the area of a square defined as:
{ (x,y) \in \R | 0 <= x <= 1 and 0 <= y <=1 }
Now the area of that is 1. Then carve out the y-axis like this:
{ (x,y) \in \R | 0 < x <= 1 and 0 <= y <=1 }
It's obviously a smaller set than the square above, but the set that's missing doesn't have any area (it's a line with no width). So it's sane to assume that the area of the new subset is still 1.
[btw: Lebesgue measure theory throws in a few more simple assumption and then derives a very nice theory for computing areas, and in extension integration of functions.]
Now probabilities are the same: Instead of points in the plane you have different runs of bogosort and the measure of the "area" for all events is defined to be 1. But you still can carve out complete "lines" (i.e. sets with even infinte many different runs of bogosort) that don't have any influence on the value of your total "area", i.e. probability.
To conclude, your in /pratice/ actually holds up in theory, too ;-)
Edit: Lebesgue measure is actually only the application onto real spaces, the fundamental thing that also applies to probabilities is just called measure theory. Mixed that up a bit.
If I understand that correctly, we're dealing with a case analogous to the coin-flipping scenario.
And since, as you admit, there are infinitely many scenarios where a bogosort never completes, we cannot place a finite upper bound on its running time for all cases, which is what complexity theory's big-O notation is all about. As I stated, the average-case complexity for bogosort is in O(n!), but the worst-case complexity isn't bound by any function.
Funny thing, it can theoretically be O(1) on quantum computers, assuming the multiple-universe interpretation of quantum mechanics: http://en.wikipedia.org/wiki/Bogosort#Quantum_bogosort ;).
1. Randomize the list. 2. If the list is not sorted, destroy the universe.
There are many ways to enumerate permutations, and we could probably pick a terrible one there, too, especially if we use a really naive implementation without any memoization or anything like that we could probably waste all sorts of time.
Bonus points for freshly generating the whole list of permutations fresh for each isSorted(applyPermutation(i,list)) test.
I think to do much worse you'd probably have to start cheating, throwing in garbage calculations that are merely used to waste time, not steps that anyone would actually think of using to progress towards the solution (i.e. I could certainly dream up a nasty brute-force problem to solve for the index integers used in the inner loop, but that's in the category of deliberate time wasting) - the nice thing about this solution is that it's 100% conceivable that someone that wasn't thinking straight could come up with it and implement it just like this. Hell, a poorly written Prolog would probably come close to implementing this algorithm if the sorting problem was specified in the right (wrong?) way...
There's also always SlowSort: http://c2.com/cgi/wiki?SlowSort, which works by finding the maximum element, then recursively sorting the rest of the list. That wouldn't be so terrible if it weren't for the twist: SlowSort finds each maximum element is by splitting the list into half, sorting both lists (using SlowSort, of course) to read off the maxima, and then picking the bigger one. I think this still runs faster than N!, but its runtime is guaranteed, whereas when generating permutations you might accidentally hit the right one in the first step (could always work around that by calculating all the lists first and then checking them, but again, that seems like cheating).
[One guy, no foolin', told a cow-orker that a byte, on an Intel platform, contained four bits. Wow.]
http://web.cs.wpi.edu/~dd/2223/broder_pessimal_algorithms.pd...
Absolute worst non-probabilistic for large inputs? Enumerate all possible lists given the keyspace, check if it contains the same values as the input, check if it's sorted. This is O((k^n)n!) worst-case (and I think average as well), where k is the size of the keyspace and n is the size of the input. Even if you take the obvious optimizations (enumerate only sorted lists, enumerate only lists of the correct length, etc) it's still terrible. The former improves it substantially, but not enough to finish before the heat-death of the universe on a substantial input size. The latter has no effect on the complexity.
edit: Corrected the complexity. It's even worse.
for i = 0 to ackerman(list.length, list.length)
pass
return quicksort(list);There's no way I'm clicking a 4chan link from here at work.
Unless you have small numbers, or negative numbers, or very closely grouped numbers, or...
It was a joke, I think. (I hope)
But, the post that started it all is:
Man, am I a genius. Check out this sorting algorithm I just invented.
#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1" &
shift
done
wait
example usage:
./sleepsort.bash 5 3 6 3 6 3 1 4 7/prog/ is a text-only board.
So...probably not very useful, after all. But, a fun thought experiment, regardless. I feel awake after reading the whole thread. Honestly, I wish there were more posts like this on HN.
Mostly just for fun but its neat to see an Erlang solution since this should be right up its alley.
-module(sleepsort).
-export([sort/2, spawn_waiters/3, wait/4]).
sort(Xs, Conv) ->
spawn(?MODULE, spawn_waiters, [Xs, Conv, self()]),
receive
{spawned, N} -> queue(N)
end.
queue(N) -> queue(N, []).
queue(0, Xs) ->
lists:reverse(Xs);
queue(N, Xs) ->
receive
{item, X} ->
queue(N - 1, [X|Xs])
end.
spawn_waiters(Xs, Conv, P) -> spawn_waiters(P, Conv, Xs, 0).
spawn_waiters(P, _, [], N) ->
P ! {spawned, N};
spawn_waiters(P, Conv, [X|Xs], N) ->
spawn(?MODULE, wait, [X, Conv(X), P, self()]),
receive
monitored -> ok
end,
spawn_waiters(P, Conv, Xs, N + 1).
wait(X, T, Q, P) ->
Ref = erlang:monitor(process, P),
P ! monitored,
receive
{'DOWN', Ref, process, P, _} -> ok
end,
timer:sleep(T),
Q ! {item, X}.
var numbers = process.argv.slice(2)
, output = []
, negative = []
for (var i=0, ln=numbers.length; i<ln; i++){
var n = +numbers[i]
setTimeout((function(n){ return function(){
if (n<0) negative.unshift(n)
else output.push(n)
if (output.length + negative.length === numbers.length) {
return console.log(negative.concat(output))
}
}})(n), Math.abs(n)/1000)
}
$ node sleepsort -2 1 0.1 4 -1 7 -3 9
[ -3, -2, -1, 0.1, 1, 4, 7, 9 ] function sleep_sort (inputs) {
function child (number) {
setTimeout(function () {console.log(number)}, Math.pow(2,number))
}
for (var i = 0; i < inputs.length; ++i)
child(inputs[i])
}
sleep_sort(process.argv.slice(2));Maybe on a quantum computer...
For example Radix Sort (http://en.wikipedia.org/wiki/Radix_sort) is not a comparison based sort and its complexity is O(k.n) where k is the max size of elements.
and output was
1
1.01
1.02
1.01
Clever hack, nonetheless.