Go 言語と D 言語でスリープソートを実装してみた

スリープソートは 2011 年に考案された新進気鋭のソートアルゴリズムです。
そのあまりの斬新さに感動してしまったちかです
ということで自分でも実装してみました。

Go 言語と D 言語の比較記事ではありません。あしからず。
Go 言語や D 言語の解説記事でもありません。あしからず。

Go 言語

package main
 
import "time"
 
func sleepsort(values []uint) <-chan uint {
    sortedChannel := make(chan uint)
    for _, value := range values {
        go func(value uint) {
            time.Sleep(time.Duration(value) * time.Second)
            sortedChannel <- value
        }(value)
    }
    return sortedChannel
}
 
func main() {
    values := []uint{ 5, 2, 19, 11, 7, 13, 3, 17 }
    sortedChannel := sleepsort(values)
    for range values {
        println(<-sortedChannel)
    }
}

D 言語

import std.stdio;
import std.parallelism;
import core.thread;
 
unittest
{
    uint[] result;
    sleepsort!(x => result ~= x)([2, 1, 4, 0, 2]);
    assert(result == [0, 1, 2, 2, 4]);
}
void sleepsort(alias callback)(uint[] values)
{
    auto pool = new TaskPool(values.length);
    foreach (value; pool.parallel(values))
    {
        Thread.sleep(value.seconds);
        callback(value);
    }
    pool.finish(true);
}
 
void main()
{
    sleepsort!writeln([5, 2, 19, 11, 7, 13, 3, 17]);
}

アルゴリズム

スリープソートのアルゴリズムは非常にシンプルです。
「値に比例する時間だけスリープしたあと値を出力する」という処理を全要素で一斉に行います。

私は「その発想はなかった！」と感動したのですが、いかがでしょうか。

Go 言語の実装では、要素数分の goroutine (軽量スレッド) を立ち上げて、
各 goroutine で要素値 [秒] だけスリープしたあとチャネルに値を渡しています。

D 言語の実装では、要素数分のタスクプールを作って、
各タスクで要素値 [秒] だけスリープしたあとコールバック関数に値を渡しています。

参考

パークのソフトウエア開発者ブログ｜ICT技術（Java・Android・iPhone・C・Ruby）なら株式会社パークにお任せください

開発の解決方法や新しい手法の情報を、パークのエンジニアが提供します。パークのエンジニアが必要な場合は、ぜひお気軽にお問い合わせ下さい。株式会社パーク：http://www.pa-rk.co.jp/

Go 言語と D 言語でスリープソートを実装してみた