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-03-30 16:47

THIS IS A MESSAGE FROM THE SUSSIX DEV TEAM (ME)

/*
 * Inspired by the valiant /prog/lodtyes
 * one of my personalities wrote an OMP
 * implementation.
 *
 * Since we are currently training SCC
 * (SCC Compiles C) we currently have to
 * use GCC to compile it.
 */

/*
 * @file sleepsort.c
 * @brief sorts numbers
 *
 * @compile gcc sleepsort.c -fopenmp -o sleepsort
 *
 * @author Gerald Jay Sussman (Massachvsetts Institvte of Technology)
 *
 * Copyright (C) 2011 Gerald Jay Sussman and the Massachvsetts
 * Institvte of Technology. All rights reserved.
 *
 * The new BSD License is applied to this software, see LICENSE.txt
 */

#include <stdio.h>
#include <stdlib.h>
#include <omp.h>

int main(int argc, char **argv) {
  int i;

  omp_set_num_threads(argc);

#pragma omp parallel for
  for (i = 0; i < argc - 1; i++) {
    long int this = atol(argv[i+1]);

    sleep(this);

    printf("%ld\n", this);
    fflush(stdout);
  }

  return 0;
}

THIS HAS BEEN A MESSAGE FROM THE SUSSIX DEV TEAM (ME)

Name: Anonymous 2011-03-30 17:26

Is Quantum Sleepsort O(1)?

Name: Anonymous 2011-03-30 18:07

My shitty attempt in Haskell... first time I ever used Control.Concurrent

import Control.Concurrent
import System.Posix.Unistd (sleep)

sleepFunc :: MVar [Int] -> Int -> IO ()
sleepFunc arr n = do
    sleep n
    xs <- takeMVar arr
    putMVar arr (n:xs)
   
sleepSort_ :: [Int] -> IO [Int]
sleepSort_ xs = do
    res <- newMVar []
    let ts = map (sleepFunc res) xs
    mapM_ forkIO ts
    waitForIt res (length xs)
   
   
waitForIt m n = do
    arr <- takeMVar m
    if length arr == n
       then return $ reverse arr
       else do
           putMVar m arr
           sleep 1
           waitForIt m n

Name: Anonymous 2011-03-30 18:17

>>82
It's still O(n), but without the race condition problems.

Name: Anonymous 2011-03-30 22:22

>>48
wat, the function should return a BOOL

Name: Anonymous 2011-03-31 1:35

Just run an insertion sort over the output if you're worried about race conditions. This ensures that the numbers are relatively close to their ending points.

Name: Anonymous 2011-03-31 6:01

>>81
Is threading in C really this simple?

Name: Anonymous 2011-03-31 8:10

>>87
Only with that OMP thing

Name: Anonymous 2011-03-31 8:37

>>87
Only with #pragma omp everyline

Name: Anonymous 2011-03-31 9:00

Perl Legacy:

map {sleep $_; print "$_\n"} @ARGV;

Name: Anonymous 2011-03-31 9:01

>>90
Shorter than ``in Lisp'' DSL.

Name: Anonymous 2011-03-31 9:06

>>91
YHBT

Name: Anonymous 2011-03-31 9:08

>>90
Perl's map is parallel?

Name: Anonymous 2011-03-31 10:48

Actual Perl implementation. Forking in Perl is awkward to say the least.


#!/usr/bin/perl                                                                
sub f {
  sleep $_[0];
  print "$_[0]\n";
}

for (0..$#ARGV) {
  $pid = fork();
  if ($pid) {
    # parent                                                                   
  push(@childs, $pid);
}
  if ($pid == 0) {
    # child                                                                    
    &f(@ARGV[$_]);
    exit(0);
  }
}
foreach (@childs) {
waitpid($_, 0);
}


time perl sleepsort.pl 3 1 8 2 9 5 4
1
2
3
4
5
8
9

real    0m9.007s
user    0m0.008s
sys    0m0.000s

Terribly inaccurate with anything other than integers, but you can give arguments like 0.003 "sqrt(2)" 10e-3, for what it's worth.

Name: Anonymous 2011-03-31 20:49

Name: Anonymous 2011-03-31 20:58

way to ruin a good python thread

Name: Anonymous 2011-03-31 22:44

If you're sorting very large groups of numbers, unless your CPU can spawn the necessary number of threads, the accuracy will be compromised by shit like thread quantums.

Name: Anonymous 2011-03-31 22:50

svn checkout my://dubs

Name: Anonymous 2011-03-31 22:50

At revision 99.

Name: Anonymous 2011-03-31 22:51

one hundubs

Name: Anonymous 2011-03-31 23:22

>>98,99
That might surprise you, but your gay.

Name: Anonymous 2011-03-31 23:35

>>101
what about my gay?

Name: BLACK HITLER 2011-04-01 1:52


    ░░░░░░░░░░░░░░░▄░░░░░░░░░░░░░░░
    ░░░░░░░░░░░░░▄▀█░░░░░░░░░░░░░░░
    ░░░░░░░░░░░▄▀░░█░░░░░░░░░░░░░░░
    ░░░░░░░░░▄▀░░▄▀░░░░░░░░░░░░░░░░
    ░░░░░░░░█▄░▄▀░░░░░░░░▄█▄░░░░░░░
    ░░░░░░░░█░▀▄░░░░░░░▄▀░█░▀▄░░░░░
    ░░░░░░░░▀▄░░▀▄░░░▄▀░░▄▀▄░░▀▄░░░
    ░▄░░░░░░░░▀▄░░▀▄▀░░▄▀░░░▀▄░░▀▄░
    ░█▀▄░░░░░░░░▀▄▀█▀▄▀░░░░░░░▀▄░█░
    ░█░░▀▄░░░░░▄▀░░█░░▀▄░░░░░░░░▀█░
    ░░▀▄░░▀▄░▄▀░░▄▀░▀▄░░▀▄░░░░░░░░░
    ░░░░▀▄░░█░░▄▀░░░░░▀▄░▄█░░░░░░░░
    ░░░░░░▀▄█▄▀░░░░░░░░▄▀░█░░░░░░░░
    ░░░░░░░░▀░░░░░░░░▄▀░░▄▀░░░░░░░░
    ░░░░░░░░░░░░░░░▄▀░░▄▀░░░░░░░░░░
    ░░░░░░░░░░░░░░░█░▄▀░░░░░░░░░░░░
    ░░░░░░░░░░░░░░░█▀░░░░░░░░░░░░░░
    ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
    ░█▄░█░█░▄▀▀▄░░█░░█░█▀▀░▀█▀░█░░░
    ░█░█▄░█░█░▄▄░░█▄▄█░█▄▄░░█░░█░░░
    ░█░░█░█░▀▄▄▀░░█░░█░█▄▄░▄█▄░█▄▄░
    ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░

glory BLACK AFRIKA
HEIL NIGGERS.
HEIL BLACK AFRIKA.
NIG HEIL BLACK HITLER!

Name: Anonymous 2011-04-01 2:13


int main(int argc, char **argv)
{
  int i, j, n = 0;

  for (i = 0; n < argc; i++)
    for (j = 0; j < argc; j++)
      if (atoi(argv[j]) == i)
      {
        printf(argv[j]);
        n++;
      }

  return 0;
}

Name: Anonymous 2011-04-01 2:18

Name: Anonymous 2011-04-01 5:57

>>104

So you managed to make a failed O(n²) version which usually won't even work whilst failing to even include the correct headers?

Congratulations.

Name: Anonymous 2011-05-17 19:31

This is a GOOD sorting algorhythm and /prog/ should be proud of it.

Name: anonymous 2011-05-17 19:51

http://www.facebook.com/pages/Life-As-We-Knew-It/109940742427550#!/pages/Life-As-We-Knew-It/109940742427550

Name: Anonymous 2011-05-17 20:08

Woah this thread is still going?   OP here, and I've given up on prog the last few months after it went downhill  (possibly partly my fault as I brought check my dubs ^__^ here.  But now I'm back as I'm very bored this evening.

Recently I've been worked on a delicious object system for C with smalltalk style messaging. Actaully it's pointless but sort of fun. It could be used as the basis of ruby-style language intepreter or something.

Name: Anonymous 2011-05-17 21:29

You totally fucked up /prog/ whith the checkdubs thing. And when copycats appeared you left...

Anyway this thread and the sleep sort algorithm were fun.

Name: Anonymous 2011-05-18 0:00

>>94,96

See >>26,30 for notes on getting more accuracy, and reduced time requirements when large values are involved.

Bonus Perl 6 version: @foo = @foo>>.&sleep;
Sadly in situ and hyper are incompatible: @foo>>.=&sleep($n); # fails

Name: >>111 2011-05-18 0:01

Shite. Disregard the $n.

Name: Anonymous 2011-05-18 20:03

>>1
Funny. I am impressed.
I copyed 1's script to "UNIX Shell Script Overall" in 2ch.
http://hibari.2ch.net/test/read.cgi/unix/1290209379/754

754 at http://hibari.2ch.net/test/read.cgi/unix/1290209379

I hope U don't mind it.

Name: Anonymous 2011-05-19 1:05

>>113
Wow, they actually praised us.
Bump great thread.

Name: Anonymous 2011-05-19 16:03

>>94
what?
perl -E 'fork and sleep $_ and say $_ and exit for @ARGV'

Name: Anonymous 2011-05-19 18:17

>>115
That's kinda useless. You need to capture the output, hence waitpid.

Not that I find forking in Perl any more awkward than forking in C. But for Perl I suppose it's fair to call it awkward since there's no DWIM involved.

Name: Anonymous 2011-05-19 18:41

>>116
fork and sleep $_, say, last for @ARGV; 1 while 1 <=> -wait

Name: Anonymous 2011-05-19 20:06

This has a best case O(n) and an infinity high worst case. (because its 0(n * Constant) and the constant could be much greater than n)

Name: Anonymous 2011-05-19 20:44

>>118
It's not a constant, it's an argument, it's O(n*k).

Name: Anonymous 2011-05-19 22:06

And I thought my shuffle sort was genius:

#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <iostream>

template<typename T>
void f (T i) {
        std::cout << i << " ";
}

int main(int argc, char **argv) {
        bool good;
        std::vector<int> v;

        for (int i = 1; i < argc; i++)
                v.push_back(atoi(argv[i]));

        do {
                good = true;
                std::random_shuffle(v.begin(), v.end());
                for (int i = 0; i < argc - 2 && good; i++)
                        good = v[i] <= v[i+1];
        } while (!good);

        std::for_each(v.begin(), v.end(), f<int>);
        std::cout << std::endl;

        return 0;
}


$ g++ -o shuffle_sort shuffle_sort.cc && ./shuffle_sort 6 4 2 1 3 5
1 2 3 4 5 6
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 -