Hatena::ブログ(Diary)

Islands in the byte stream

2011-05-19

常識を覆すソートアルゴリズム!その名も"sleep sort"!

TwitterのTLで知ったのだが、少し前に海外の掲示板で"sleep sort"というソートアルゴリズムが発明され、公開されたようだ。このアルゴリズムが面白かったので紹介してみる。

Genius sorting algorithm: Sleep sort

1 Name: Anonymous : 2011-01-20 12:22
諸君!オレは天才かもしれない。このソートアルゴリズムをみてくれ。こいつをどう思う?

#!/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

2 Name: Anonymous : 2011-01-20 12:27
>>1
なん…だと…。こいつ、動くぞ!

っておい!0..218382のリストのソートに218382秒も待たされるのかよ!

3 Name: Anonymous : 2011-01-20 12:31
>>2
まあ、最悪のケースだとそうなるな。

4 Name: Anonymous : 2011-01-20 12:45
これの計算量はどんなもんだろう?

5 Name: Anonymous : 2011-01-20 12:56
#!/bin/bash
function f() {
    sleep $(echo "$1 / 10" |bc -l)
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

最適化に成功したぞ!
ただしsleepが浮動小数点数を受け付けるシステムじゃないと動かないので注意な。

6 Name: Anonymous : 2011-01-20 13:10
>>4
そうだな…正直よくわからんが、O(入力値の中の最大値)なんじゃないか。

7 Name: Anonymous : 2011-01-20 14:16
O(入力値の中の最大値 + n)じゃないかな。スレッドの生成に比例した時間が余計に掛かるだろ。
しかしこれはすばらしい。

...

これは面白い!まさかsleepを利用してソートができるとは!実行してみると確かに値がソートされていることがわかる。スレッドはこのあともしばらく続き、C#ErlangLisp・C・Perlなどの言語でも実装されたようだ。

せっかくなので私もPerlで実装してみた。上記掲示板でのオリジナル実装とは異なり、サブルーチンとして独立させているので汎用的に使える。

#!perl
use strict;
use warnings;
use Time::HiRes qw(sleep);
use IO::Select;

use Data::Dumper;

sub sleep_sort {
    my @input = @_;
    my @output;
    my $watcher = IO::Select->new();
    my @children;

    foreach my $value(@input) {
        my $pid = open my $io, '-|';
        defined($pid) or die $!;

        if($pid == 0) {
            sleep $value / 10;
            print $value;
            exit;
        }
        else {
            $watcher->add($io);
            push @children, $pid;
        }
    }

    while($watcher->count > 0) {
        foreach my $io( $watcher->can_read(0) ) {
            $watcher->remove($io);
            push @output, <$io>;
            close $io;
        }
    }

    waitpid $_, 0 for @children;

    return @output;
}

print Dumper([ sleep_sort @ARGV ]);
__END__
$ perl sleep-sort.pl 1 3 5 2 4
$VAR1 = [
          '1',
          '2',
          '3',
          '4',
          '5'
        ];

スレッドやファイバを使っても実装できるだろうが、今回はopen()によるforkとIO::Selectを使ってみた。

4798114618
翔泳社 (株)アンク
購入: 3人 クリック: 48回

h-kageyuh-kageyu 2011/05/21 16:06 すげー!天才。

lolicsystemlolicsystem 2011/05/21 23:45 complexity はこの場合「複雑さ」ではなく「計算量」と訳した方がわかりやすいかも。

gfxgfx 2011/05/24 22:23 >lolicsystem
確かに!「複雑さ」に違和感はあったんですが、計算量という訳語をド忘れしてました。修正しました。ありがとうございます。

maxuramaxura 2011/05/30 10:44 こりゃすげぇわ

すーさんすーさん 2011/05/31 21:39 素直にすげーって言いたいが自分にはチンプンカンプンです。

バケツソートバケツソート 2011/06/02 13:08 こいつはバケツソートと同じなのではないかな。
http://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88

OgachaOgacha 2011/06/04 07:34 ですね。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/gfx/20110519/1305810786