++C++; // 未確認飛行 C ブログ

http://ufcpp.net/

常識を覆すソート アルゴリズムに大人げなく食いついてみる!

with one comment

うわさのスリープ ソートを Rx で実装してみたり。

要するに、値に比例して Sleep → 値を enqueue すればソートできるよねというアルゴリズム。値の最大値に比例してソートに時間がかかるというネタ ソート。

追記: MVP for LINQ (ほんとは C#。LINQ カテゴリーないので)な neuecc さんがちゃんと Rx らしい書き方で作ってれました。

http://ideone.com/GjeOU

IEnumerable と Observable.Delay を連携される方法が分からなくて上記のコードみたいな書き方にしたんですよねぇ。SelectMany 使って Return 挟めばよかったのか。ちなみにこのコードは、スレッドの挙動的には僕のと同じくスレッド プール利用になるはずだそうです。

以下、ネタにマジレス的説明w

書いたコード

以下のようなコードになりました。Reactive Extensions を利用しています。

/// <summary>
///
 うわさのスリープ ソート。

///
 </summary>
///
 <typeparam name="T">ソート対象の要素の型。
</typeparam>
///
 <param name="data">ソート対象。
</param>
///
 <param name="toOrder">T 型から順序を表す整数に変換。
</param>
///
 <returns>結果受け取り用の Observable
</returns>
static IObservable<T> Sort<T>(IEnumerable<T> data, Func<T, int
> toOrder)
{
   
const int
Weight = 50;
 
   
var results = new Subject
<T>();
   
var maxTime = int
.MinValue;
 
   
foreach (var x in
data)
    {
       
var
local = x;
       
var
time = toOrder(x) * Weight;
        maxTime =
Math
.Max(maxTime, time);
 
       
TaskEx
.Delay(time).ContinueWith(t => { results.OnNext(local); });
    }
 
   
TaskEx
.Delay(maxTime + Weight).ContinueWith(t => results.OnCompleted());
 
   
return
results;
}

ポイントとしては、

  • マニュアル スレッドじゃなくてスレッド プールを使う
  • ソート結果の受け取りに IEnumerable じゃなくて IObservable を使う

.NET でスレッドを直接立てたら負けかなと思っている

元ネタの 4chan では C# 実装している人もいるわけですが、Thread クラス直接使ってる・・・

このアルゴリズムで、Thread クラスを直接使ってしまうと、ソート対象の要素の数だけスレッドが立ってしまうわけで・・・ 何千個も何万個もスレッド立てるの?

何それ怖い。

TaskEx.Delay(今回は自作しています。将来的には、標準ライブラリに同様のメソッドが入るようです)を使えば、スレッド プールを使ってくれて、スレッド リソースは浪費しません。

※スレッド プールはスレッドよりも実行順序が緩めなんで、ひょっとしたらときどき結果狂うかもなぁ。何回か試しに実行した結果はうまくいっているものの。

全要素のソートが完了するまで Wait したら負けかなと思っている

非同期に結果が返ってくるものを、全要素待つのももったいないというか。1要素ずつ、push 型で受け取るべきじゃないかと。

実行してみればわかりますが、全要素のソートが完了してから一気に表示されるのではなく、1要素ずつ、ソートが終わった部分から表示されるようになっています。

雑感、というか脱線

しかし、このネタで始めて 4chan の実物を見たんですけども、ほんとに 2ch の英語版なんですねぇ、見た目からして。

あと、4chan って、コードの syntax highlight できるんだ。ちょっとすごい。

Written by ufcpp

2011年5月20日 @ 02:36

カテゴリー: C#

Tagged with

コメント / トラックバック1件

Subscribe to comments with RSS.

  1. 4chanはふたば型の掲示板と、2ちゃんねる型の掲示板両方があります。

    白帽子

    2011年5月24日 at 16:32


コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

%d人のブロガーが「いいね」をつけました。