読者です 読者をやめる 読者になる 読者になる
ようこそ。睡眠不足なプログラマのチラ裏です。

IEnumerableをシャッフル!

プログラミング アルゴリズム C#3.0

ネタ元:id:kawatanさんのエントリより
http://d.hatena.ne.jp/kawatan/20081210


IEnumerableを実装していれば何でもシャッフルって、素敵ですね〜。
カードゲームなんか作るときにサクッと利用できちゃいますね。
よいものは盗んじゃおう!ということで、さっそく自分専用俺俺フレームワークに拡張メソッドを追加しました。
あ、Fisher-Yatesアルゴリズムみたいなアルゴリズムって、ラスベガス法とかなんとか言うんですよね確か。


あと、重箱の隅をつつくようで大変恐縮なんですが・・、
Listをnewするよりも、ToArray()メソッドを利用した方が若干早いのかなと思いました*1
加えて、yield returnするようにしてみたり、無駄にクロージャで覆い被せてディレイしてみました。
yieldキーワードはラムダ式の中に直接記述できませんが、イテレータブロックはラムダ式内に記述可能なので、
yield returnしているイテレータブロックをラムダ式内に記述することで、
実質的にyield returnをラムダ式内に書いているかのような振る舞いを表現することができますね。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApplication1
{
    public static class IEnumerableExtentions
    {
        public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> self)
        {
            // Fisher-Yates
            var r = new Random(DateTime.Now.Millisecond);
            var array = self.ToArray();

            int i = self.Count();
            while (i > 1)
            {
                int j = r.Next(i--);
                T temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
            foreach (var item in array) yield return item;
        }

        public static Func<IEnumerable<T>> DelayShuffle<T>(this IEnumerable<T> self)
        {
            return () => { return self.Shuffle() ; }; 
        }
    }

    public class Program
    {
        private static void Main()
        {
            var numberList = Enumerable.Range(0, 10000);

            var sw = new Stopwatch();
            for (var i = 1; i <= 10; i++)
            {
                Console.WriteLine("---{0}回目---", i);
                sw.Reset();
                sw.Start();
                numberList.Shuffle();
                sw.Stop();
                Console.WriteLine("(1):{0}", sw.Elapsed);

                sw.Reset();
                sw.Start();
                numberList.DelayShuffle();
                sw.Stop();
                Console.WriteLine("(2):{0}", sw.Elapsed);
            }
            Console.ReadLine();
        }
    }
}

シャッフル結果はあえて出力していません(・ω・)


DelayShuffleの方がクロージャにしてある分、評価が若干早いっぽいです。
でも、偶にDelayShuffleの方が遅いこともあったり早いこともあったりラジバンダリ・・。
もしかすると、このDelayShuffleは意味ないかも・・。意味なかったらごめんなさい(笑)

*1:目くそ鼻くそ程度の差ですが・・。

広告を非表示にする