Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Genius sorting algorithm: Sleep sort

Name: Anonymous 2011-01-20 12:22

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

Name: Anonymous 2011-06-15 18:12

This thread is way too popular. Front page of Reddit and Hacker News. I fear this may be the end for /prog/

Name: the dude 2011-06-15 18:18

it ends right here right now!

NULL

Name: Anonymous 2011-06-15 18:37

http://www.reddit.com/r/programming/comments/i0dcx/4chan_sleep_sort/c1zudzw

God fucking damn it. What sort of community awards points for being a fucking moron?

Name: Anonymous 2011-06-15 19:05

Today is a terrible day for /prog/. Fucking Paul Graham bimbos and groupies all over *my* /prog/ ?

Name: Rena 2011-06-15 19:11

#!/usr/bin/env lua
function sleepsort(arr)
    local res, thread = {}, {}
    local nthreads = #arr
   
    for i = 1, #arr do
        thread[i] = coroutine.create(function()
            for n=arr[i], 0, -1 do coroutine.yield() end
            nthreads = nthreads - 1
            thread[i] = nil
            res[#res+1] = arr[i]
        end)
    end
    while nthreads > 0 do
        for i = 1, #arr do
            if thread[i] then coroutine.resume(thread[i]) end
        end
    end
    return res
end

math.randomseed(os.time())
local arr = {}
for i = 1,10 do arr[i] = math.random(1,99) end
print(unpack(sleepsort(arr)))

This version also works much faster than the original script. (And faster still with LuaJIT!)

Name: Rena 2011-06-15 19:15

Oh yeah, and no race conditions either :)

Name: Anonymous 2011-06-15 19:44

>>133

If your scheduler is not at least O(log n) you should kill yourself.

It only took linux 9 years to get a O(1) one... and then threw it out for a O(log n) one because someone was butthurt about their porn skipping in mplayer because of f@h.

Name: Anonymous 2011-06-15 19:56

it is vulnerable to race conditions

Name: Anonymous 2011-06-15 20:06

GOD DAMN REDDIT

Name: Anonymous 2011-06-15 20:07

>>153
Let's play some golf! Here's a simplified version of yours that accepts any inputs and doesn't require any functions:

#!/usr/bin/env ruby
ARGV.each { |e| fork { sleep(e.to_f/1000); puts e } }

Also, it's much faster, since it's sleeping milliseconds instead of seconds now. You could probably toss more zeroes in, but I'm not sure if that would actually make a difference past what I've got.

Name: bowsersenior 2011-06-15 20:33

>>170

Very nice! I put it in a gist for posterity:
* https://gist.github.com/1028467

Name: Anonymous 2011-06-15 20:55

Hey /prog/lodytes. I propose a game: guess which of new posters are from reddit and which are from HN based on the contents of their posts.

My guess is all this torrid Ruby code is coming from reddit.

Name: Anonymous 2011-06-15 21:14

>>141

fork

Name: Anonymous 2011-06-15 21:15

>>141

Y?????

Name: Anonymous 2011-06-15 22:35

>>163
Reddit upvotes aren't rewards, they're indicators that a comment is "relevant to the discussion"

In this case, others are wondering how it works. I read this whole thread and can see half of you don't know the answer to that either, so the question is relevant.

Name: Anonymous 2011-06-15 22:42

I read this whole thread and can see half of you don't know the answer to that either, so the question is relevant.
I read your whole post and can see that either you're a liar or have terrible reading comprehension skills.

Name: Anonymous 2011-06-15 22:54

>>172
If the post is a fucking idiot, they are from reddit.

Name: Anonymous 2011-06-15 22:57

I don't get it

Name: Q 2011-06-15 23:00

This works as long as the time dimension of spacetime is strictly following a linear ordering of events. So your plebeian Newtonian algorithm may fail miserably, depending.

Name: Anonymous 2011-06-15 23:15

brainfuck implementation:

,>,>++++++++[<------<------>>-]
 <<[>[>+>+<<-]>>[<<+,>,>++++++++[<------<------>>-]
 <<[ ----------[++++++++++>----------]++++++++++
>[>+>+<<-]>>[<<+>>-]<<<-]
 >>>++++++[<++++++++>-]<.>.>>-]<<<-]
  ,----------[----------------------.,----------]
 ,---<<<+>>>-------[----------------------.,----------]
>> ----------[++++++++++>----------]++++++++++
>++++++[<++++++++>-]< ----------[++++++++++>----------]++++++++++
.>. ----------[++++++++++>----------]++++++++++
>++>+<<-]>>[<<+>>-]<<<-]
 >>[>[>+>+<<-]>>[<<----------[++++++++++>----------]++++++++++
>++,>,>++++++++[<------<------>>-]
 <<

Name: Anonymous 2011-06-15 23:39

Linux scheduler was O(n) before 2.6

Name: Anonymous 2011-06-15 23:44

>>181
The kernel still has to take n cycles to execute each scheduled event. Ergo, time usage is O(n2) no matter how you (slur here)s want to frame it.

Name: Anonymous 2011-06-15 23:53

Access my anus in linear time.

Name: Anonymous 2011-06-15 23:59

>>183
But it will take exponential space!

Name: Anonymous 2011-06-16 0:13

>>179
Can it or I'll be forced to write a sort algorithm with imaginary complexity.

>>182
Why are you counting n twice? I see no sage, so I suspect you're from reddit rather than actually trolling.

Name: Anonymous 2011-06-16 0:29

>>185
Redditors can't BBCode.

Name: Anonymous 2011-06-16 1:00

>>186
Aw shit. I didn't think any /prog/lodyte was genuinely that stupid.

Name: Anonymous 2011-06-16 1:09

>>179
Oh shit!

Name: Anonymous 2011-06-16 1:10

>>185
182 here. It was a thinking error, based on the absurd assumption that the scheduler doesn't sort. And yes, I can BBCode till your heart stops.

My remaining point is that, whatever algorithm the scheduler uses, all sleepsort does is pop items off it in slow motion (or not-so-slow motion if you can get a precise enough timing signal.) There's no good reason to not simply implement the scheduler's algorithm directly, instead.

Name: Anonymous 2011-06-16 1:53

>>189
There's no good reason to not simply implement the scheduler's algorithm directly, instead.
Are you one of those people who get pissed off when they see others having fun?

Sleepsort isn't genius because it's a great sorting algorithm, it's genius because it's a subtle joke, a play on the fact that we tend to measure only in-process time complexity.

Name: Anonymous 2011-06-16 1:55

i just joined in on a piece of history.

congrats OP

Name: Anonymous 2011-06-16 2:06

>>175
stfu faggot

Name: Anonymous 2011-06-16 2:09

>>192
Heh. If you want to get angry about something, check out the post in the HN thread where buddy is comparing sage to downvotes.

Name: Anonymous 2011-06-16 2:14

>>193
Every EXPERT PROGRAMMER knows that HN is for cockmonglers who dont read SICP

Name: Anonymous 2011-06-16 2:41

Is it web scale?

I mean, can I replicate it, then shard?

And one more thing: when you plan your IPO?

Name: Anonymous 2011-06-16 2:46

Comment->next = NULL;

now stop it...

Name: Anonymous 2011-06-16 2:53

>>1-196

                                                
                        _,-%/%|                 
                    _,-'    \//%\               
                _,-'        \%/|%               
              / / )    __,--  /%\               
              \__/_,-'%(%  ;  %)%               
                      %\%,   %\                 
                        '--%'                   
                                                
                                                .

Name: Anonymous 2011-06-16 3:39

<?php
$pids = array();
for ($i=1; $i<$argc; $i++)
{
        if (($pid = pcntl_fork()) == 0)
        {
                $sleep = intval($argv[$i]);
                sleep($sleep);
                echo $sleep."\n";
                exit();
        }
        else if ($pid == -1)
        {
                die();
        }
        else
        {
                $pids[] = $pid;
        }
}

foreach($pids as $pid)
        pcntl_waitpid($pid, $status);
?>

php sleepsort.php 1 3 5 6 2

php version ^ ^

Name: Anonymous 2011-06-16 3:43

This is already covered in SICP chapter 1.2.4 Exponentiation[1], in which they implement sleep sort with continuation-based coroutines.

[1]: Sorting integrals: http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.4

Name: Anonymous 2011-06-16 3:48

>>198
Take your toy language and kindly take your coat and go fuck yourself.
Newer Posts
All trademarks and copyrights on this site are owned by their respective parties. All comments and posts are the responsibility of their own posters.
- Tinychan + 2ch Mode -