9
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

C#でスリープソート書きました

スリープソートとは

海外掲示板4chanのユーザーにより発表された究極のソートアルゴリズム。
具体的な手順は以下のように超シンプルなもの。

  1. 配列から値を読み込み、その値だけの時間スリープする
  2. スリープし終わったらその値を出力する

これを配列の全ての値に対して並列処理してやると、値の小さい方から順に出力される。
比較回数0回、計算量ほぼ0という驚愕の事実に加え、安定ソートであるという優れもの。
(実行時間とメモリに目をつぶれば)

実装してみた

自分のようなひよっこ入門プログラマーにはちょうどいい練習だと思ったので、n番煎じを気にせずやってみた。

    public static class Extensions
    {
        public static IEnumerable<T> SleepSort<T>(this IEnumerable<T> source, Func<T, int> selector)
        {
            var list = new List<T>();
            var sync = new Object();
            var tasks = source.Select(async item =>
            {
                //System.Threading.Thread.Sleep(100); //これをつけると安定ソートとなる
                await Task.Delay(TimeSpan.FromSeconds(selector(item)));
                lock (sync) { list.Add(item); }
            }).ToArray();
            Task.WaitAll(tasks);
            return list;
        }

        public static IEnumerable<int> SleepSort(this IEnumerable<int> source)
        {
            return SleepSort(source, i => i);
        }
    }

LINQっぽくIEnumerable<T>の拡張メソッドに。また、引数にセレクタを使うことで汎用性を高めておく。(そのため、普通のint配列のソートを後でオーバーロードした)

実行

実行例
        static void Main(string[] args)
        {
            var list = new[] { "Alice", "Bob", "Cate", "David", "Eve" };
            foreach (var item in list.SleepSort(s => s.Length))
            {
                Console.WriteLine(item);
            }

            Console.ReadKey();
            return;
        }
結果
Bob
Eve
Cate
David
Alice

どうもC#で並列処理すると各タスクの実行順序がまちまちで、安定ソートにならない模様。
どうしても安定させたい場合は、Thread.Sleepを用いて各タスクの実行開始をわずかにずらすことで解決する。

まとめ

わかってはいたが、実行に時間がかかりすぎる。
実はこれが初めての並列処理で、自分にとってはとても素晴らしい練習問題になったと思う。
同じくらいの入門者の方は是非とも挑戦してほしい。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
9
Help us understand the problem. What are the problem?