Gauche-SDLをWindowsで動かす
前回の記事で紹介したように、Gauche-SDLというGauche用SDL拡張ライブラリを作ってます。
そんなGauche-SDLをWindows環境でも手っ取り早く動かせるようにしたので、方法を記事としてまとめておきます。
今まではソースコード一式を取得して、MinGWを使って自前でコンパイルする必要があったのですが、
事前にコンパイル済みのバイナリをインストールすればいいだけにしました。
ただ、現状では試験的な導入なので、64bit版のWindowsには対応していません。64bit版の方はもうしばらくお待ちください。
必要なファイル一式はコチラ。
また、必要な環境はGaucheの0.9.2がインストール済みであることです。
インストール方法は、ダウンロードしたzipを解凍したフォルダ内にあるinstall.cmdを実行するだけです。
注意することとして、Windows Vistaや7の場合はinstall.cmdを管理者として実行する必要があります。
また、レジストリをいじっていないのでアンインストール情報などは登録されません。
アンインストールする時は同じフォルダ内にあるuninstall.cmdを実行してください。
次に、作成したプログラムを実行するためにはSDLやライブラリのDLLが必要です。
こちらはbinaryフォルダ内に全てあるので、パスの通ったフォルダに全てコピーしてください。
これでGauche-SDLをWindowsでも動かせるようになったはずです。
ただWindows環境での問題点として、
公式で配布されているGaucheのWindows用バイナリではThread機能がサポートされていないため、
Gauche-SDLでもその部分に依存している関数は実行できないというところです。
具体的には、sampleフォルダ内にあるsound.scm/thread.scm/timer.scmが実行できません。
これについては現状どうしようもないので、Gaucheのバージョンアップで公式にWindowsでもスレッドがサポートされることに期待します。
※追記 最近のGaucheのコミットを見てみるとWin32のスレッドをサポートするためのものがあったので、次期バージョンあたりでサポートされるのかな?と推測。公式にサポートされれば、こちらも修正して対応します。
今回のWindowsサポートは様々な環境化でのテストがほとんどできていないので、
何か問題があればコメントなどで報告をお願いします。
Gauche-SDLでライフゲーム
最近になってGauche用のSDLラッパーを作成しているので、ここで一つ宣伝をしておきます。
SDLの詳細に関しては本家とかウィキペディアとかで。
作成しているGauche-SDLはこちらのgithub上にあります。
インストール方法などもろもろは同じくgithub上のWikiにあるので参照してください。
Windows上での動作も確認できていますが、コンパイルにはMinGWが必要です。気が向いたらコンパイル済みのバイナリもどこかで配布するかも。
最後に一つサンプルを載せておきます。
こちらのサイトを参考にして、ライフゲームをGauche-SDLを利用して書いてみました。
(use sdl) (use sdl.gfx) (use math.mt-random) (use gauche.uvector) (define screen #f) (define-constant stride 100) (define world (make-u8vector (* stride stride) 0)) (define-macro (world-ref world y x) `(ref ,world (+ (* ,y ,stride) ,x))) (define-macro (world-set! world y x val) `(set! (ref ,world (+ (* ,y ,stride) ,x)) ,val)) (define (count-neighboring-individual y x world) (let ([next-y (if (eq? y (- stride 1)) 0 (+ y 1))] [prev-y (if (zero? y) (- stride 1) (- y 1))] [next-x (if (eq? x (- stride 1)) 0 (+ x 1))] [prev-x (if (zero? x) (- stride 1) (- x 1))]) (+ (world-ref world prev-y prev-x) (world-ref world prev-y x) (world-ref world prev-y next-x) (world-ref world y prev-x) (world-ref world y next-x) (world-ref world next-y prev-x) (world-ref world next-y x) (world-ref world next-y next-x)))) (define (update-next-generation world) (let ([w (u8vector-copy world)]) (dotimes [y stride #f] (dotimes [x stride #f] (let ([count (count-neighboring-individual y x world)]) (cond [(zero? (world-ref world y x)) (when (eq? count 3) (world-set! w y x 1))] [(or (>= count 4) (<= count 1)) (world-set! w y x 0)])))) w)) (define (initialize-world) (let ([m (make <mersenne-twister>)]) (dotimes [y stride #f] (dotimes [x stride #f] (world-set! world y x (if (< (mt-random-integer m 10) 1) 1 0)))))) (define update (let ([wait (/ 1000 3)] [next 0]) (lambda () (set! next (if (>= (sdl-get-ticks) next) (begin (set! world (update-next-generation world)) (+ next wait)) next))))) (define (draw) (let ([white (make-sdl-color 255 255 255)] [black (make-sdl-color 0 0 0)]) (dotimes [y stride #f] (dotimes [x stride #f] (gfx-box-color screen (* x 4) (* y 4) (+ (* x 4) 4) (+ (* y 4) 4) (if (zero? (world-ref world y x)) black white))))) (sdl-update-rect screen 0 0 0 0)) (define (initialize) (sdl-init SDL_INIT_VIDEO) (sdl-wm-set-caption "LifeGame -Gauche SDL-" #f) (set! screen (sdl-set-video-mode 400 400 32 SDL_SWSURFACE)) (initialize-world) ) (define-constant wait (/ 1000 60)) (define (main-loop) (let loop ([next-frame (sdl-get-ticks)]) (unless (let proc-event ([event (sdl-poll-event)]) (and event (or (eq? (ref event 'type) SDL_QUIT) (and (eq? (ref event 'type) SDL_KEYUP) (eq? (ref (ref event 'keysym) 'sym) SDLK_ESCAPE)) (proc-event (sdl-poll-event))))) (let ([next (if (>= (sdl-get-ticks) next-frame) (begin (update) (when (< (sdl-get-ticks) (+ next-frame wait)) (draw)) (+ next-frame wait)) next-frame)]) (sdl-delay 0) (loop next))))) (define (finalize) (sdl-quit)) (initialize) (main-loop) (finalize)
サンプルを作ってみて気付いたけど、薄いラッパーだけだとどうもSchemeっぽいコードにならない。
もうちょっと抽象度を上げたレイヤもつくりたいなぁ。
テキストテンプレートのアセンブリのロードと名前空間の宣言
つーわけで今回はテキストテンプレート中でアセンブリをロードする方法と使用する名前空間の宣言を行う方法です。
と、書いてもピンと来ないかもしれないのでいいかえると、
アセンブリのロード => VisualStudioで参照の設定にdllを追加する。
名前空間の宣言 => C#でのusing System; みたいなもの。
この二つをテキストテンプレートのコードで行う方法です。
さっそく例。
<#@ template language="C#" #> <#@ output extension=".txt" #> <#@ assembly name="System.Net" #> <#@ import namespace="System.Net" #> <#@ import namespace="System.IO" #> <#@ import namespace="System.Text" #> <# WebClient wc = new WebClient(); Stream st = wc.OpenRead("http://www.google.co.jp"); StreamReader reader = new StreamReader(st, Encoding.GetEncoding("Shift_JIS")); String html = reader.ReadToEnd(); reader.Close(); st.Close(); #> <#=html#>
実行結果
<html><head><meta http-equiv="content-type" content="text/html; charset=Shift_JIS"><title>Google</title> ...以下省略
長ったらしいので実行結果は省略で。
やっていることはというと、googleのトップページにアクセスし内容を取得してそのままテキストとして出力しているだけです。
ではさっそく解説。
コードの最初のほうでは<#@ #>タグで囲まれた行が続いています。
これをこのタグで囲まれたものをディレクティブといいます。
先頭2つは以前のテキストテンプレートの紹介で書いているのでわからない方はそちらを参照してください。
今回の目的であるアセンブリのロードと名前空間の宣言に関するコードはそれに続くコードです。
まずアセンブリをロードする時は<#@ assembly name="〜" #>のディレクティブを使用します。そしてname=の〜部分にロードしたいアセンブリ名を書きます。
例ではSystem.Netアセンブリをロードしています。
続いて名前空間の宣言方法は<#@ import namespace="〜" #>のディレクティブを使用します。ここでも同じようにnamespace=の〜部分に宣言したい名前空間を書きます。
例ではSystem.Net、System.IO、System.Textを宣言しています。
名前空間の宣言はアセンブリのロードと違い必須ではありません。
最初に書いたようにC#のusing〜の代わりなので無い場合はコード中で完全名を指定すればいいだけです。
今回はさりげなく例題のコードでネットワークアクセスを使用しました。
このようにテキストテンプレートではWebを利用したテキスト出力も可能です。
というより、.NETでできることすべてを利用してテキスト出力が可能なのです。
夢が広がりんぐですネ。
DynamicMethodで末尾再帰
唐突ですがC#にはDynamicMethodというクラスがあります。
このクラスではILを直接指定することによって、プログラム実行時に動的にメソッドを作成することができます。
さっそく例
DynamicMethod method = new DynamicMethod("DynamicMethod", typeof(void), Type.EmptyTypes); ILGenerator il = method.GetILGenerator(); il.Emit(OpCodes.Ldstr, "DynamicMethod!!"); il.Emit(OpCodes.Call, typeof(Console).GetMethod("WriteLine", BindingFlags.Static | BindingFlags.Public, null, new Type[] { typeof(String) }, null)); il.Emit(OpCodes.Ret); Action action = (Action)method.CreateDelegate(typeof(Action)); action();
実行結果はなんとなく予想がつくと思いますが一応、
DynamicMethod!!
と表示されます。当たり前ですね。
コードの詳細解説は省きます。理由はただ単に面倒くさいからです。
どうしても知りたいという方はmsdnのこの辺を読めばなんとなく感じは掴めるかと。
とまあこんな感じでプログラム実行中に動的にメソッドを作れるわけです。
しかもメソッドを作る際にILを直接使うことによってC#では実現できないこともできたりします。
そのひとつに末尾呼び出しの最適化があります。
まず例題。階乗を求めるどこにでもある関数とそれを呼び出すMainメソッド。
class Program { static void Main(string[] args) { Console.WriteLine(Fact(5, 1)); } public static int Fact(int num, int acc) { Console.WriteLine(new StackTrace().FrameCount); if (num == 0) return acc; else return Fact(num - 1, num * acc); } }
実行結果
2 3 4 5 6 7 120
このFactメソッド中の二つ目のreturn、
return Fact(num - 1, num * acc);
という部分が末尾呼び出し(今回は末尾再帰でもある)にあたります。
実行結果の120より前の2〜7の部分は現在のメソッド呼び出しでたまっているスタックフレーム数を表示しているものです。
末尾呼び出しの場合スタックを消費せずにメソッド呼び出しができるのですが、実行結果からわかるとおり一度呼び出すたびにスタックフレームがたまっているのが分かります。
これを最適化しスタック消費なしでメソッド呼び出しを行うのが末尾呼び出しの最適化になるのですが、これをしようと思ってもC#からは明示的に指定する方法がありません。
普通ならメソッド呼び出しで積まれていくスタックフレームはたかが知れているので問題がないのですが、今回の場合メソッドの再帰呼び出しを行っているので大きな数を指定してやった場合スタックのオーバーフローが起こってしまいます。(スタックのオーバーフローよりも先に数字のオーバーフローが起こるということを今は気にしない)
これは由々しき事態です。
さぁどうしましょう。
C#ではできません。
よろしい。ならばILだ。
はい。というわけでDynamicMethodを使い、直接ILを指定して前述のFactと同じ働きをするメソッドを作ってみます。
class Program { static Func<int, int,int> fact; static void Main(string[] args) { DynamicMethod method = new DynamicMethod( "factorial", typeof(int), new Type[] { typeof(Program), typeof(int), typeof(int) }, typeof(Program)); ILGenerator il = method.GetILGenerator(); Label label = il.DefineLabel(); il.Emit(OpCodes.Newobj, typeof(StackTrace).GetConstructor(Type.EmptyTypes)); il.Emit(OpCodes.Callvirt, typeof(StackTrace).GetProperty("FrameCount", BindingFlags.Instance | BindingFlags.Public).GetGetMethod()); il.Emit(OpCodes.Call, typeof(Console).GetMethod("WriteLine", BindingFlags.Public | BindingFlags.Static, null, new Type[] { typeof(int) }, null)); //引数のnumを読み込む il.Emit(OpCodes.Ldarg_1); //num != 0 なら再帰呼び出しの方へジャンプ il.Emit(OpCodes.Brtrue_S, label); //return acc; il.Emit(OpCodes.Ldarg_2); il.Emit(OpCodes.Ret); il.MarkLabel(label); //Programクラスの静的フィールドのfactを読み込み il.Emit(OpCodes.Ldsfld, typeof(Program).GetField("fact", BindingFlags.NonPublic | BindingFlags.Static)); //(num - 1) il.Emit(OpCodes.Ldarg_1); il.Emit(OpCodes.Ldc_I4_1); il.Emit(OpCodes.Sub); //(num * acc) il.Emit(OpCodes.Ldarg_1); il.Emit(OpCodes.Ldarg_2); il.Emit(OpCodes.Mul); //メソッド呼び出し il.Emit(OpCodes.Tailcall); il.Emit(OpCodes.Callvirt, typeof(Func<int,int,int>).GetMethod("Invoke", BindingFlags.Public | BindingFlags.Instance, null, new Type[] { typeof(int), typeof(int) }, null)); il.Emit(OpCodes.Ret); //DynamicMethodの生成 fact = (Func<int, int,int>)method.CreateDelegate(typeof(Func<int, int,int>), new Program()); //呼び出し Console.WriteLine(fact(5, 1)); } }
実行結果
2 2 2 2 2 2 120
前回の結果と見比べてわかるとおり、今回はスタックフレームを消費せずに再帰呼び出しがおこなえていることが分かります。
これを行うために重要なILの命令は、コードの中のメソッド呼び出しというコメントのすぐ下にあるTailcallという命令です。
この命令に続けてメソッド呼び出しを行う命令を指定すれば、そのメソッド呼び出しはスタックフレームを消費しません。
一応ですが注釈。
正確には呼び出しにスタックフレームを消費しないのではなく、現在のスタックフレームを破棄してから新しい呼び出し先のスタックフレームを積む。という作業が行われます。
さらに注釈。
Tailcallの命令はどんな状況でもとにかくメソッド呼び出し命令の前につければいいというわけではありません。Tailcall命令が不正な箇所にある場合は実行時に例外が投げられるので要注意。
今回の方法を使えばC#でも再帰関数を書くのが怖くないですね。
と、言いたいところだが。。。
メンドクせぇ。
それに階乗を求める関数をわざわざ実行時に動的に作る意味なんてない。
と、いうわけで結論。
今回の記事にたいした意義などない。
じゃオワリ。
T4
えー、更新がかなり久しぶりになってしまいました。
ちょうど2カ月ぶりですね。
なんかもう記事の書き方を忘れてしまいました。
そのようなどうでもいいことは置いておいて、さっそく今回のトピックスの紹介です。
その名も「T4」
何の略かというと「Text Template Transformation Toolkit」の略だそうです。
もちろんターミネーター4ではありません。
この名前の時点でどのようなことを行うものなのか想像がつくかもしれません。
はてなキーワードにも一応どのようなものかの解説があるようです。
が、この解説に対して一つツッコミたいところがあるのですがそれはおいおい別の記事で。
このT4の機能をごく簡単に説明してしまうと
「テキストを生成する」
ということです。
このテキストというのはメモ帳なので開ける普通のテキストを指します。
なのでもちろん拡張子が違うだけの各言語のソースコードやXMLファイルなども含まれます。
言葉で説明するより実物のソースコードを提示した方が速いと思うので早速T4のコードを示してみます。
<#@ template language="C#" #> <#@ output extension=".txt" encoding="Shift_JIS" #> Hello World!! <# for(int i = 0;i < 10;++i) { #> <#=i#>_<#=System.DateTime.Now#> <# } #>
このようにして作成し上記のコードをもとにファイル生成を行った結果を示します。
Hello World!! 1_09/07/2009 02:22:29 2_09/07/2009 02:22:29 3_09/07/2009 02:22:29 4_09/07/2009 02:22:29 5_09/07/2009 02:22:29 6_09/07/2009 02:22:29 7_09/07/2009 02:22:29 8_09/07/2009 02:22:29 9_09/07/2009 02:22:29 10_09/07/2009 02:22:29
コードと結果を示したのはいいですが、どうやってこれを実行すればいいのかをまだ書いていませんでした。
ので開発と実行の環境を解説します。
まず開発の環境ですが、僕はVisual Studio2008のProfessionalを使用しています。
このバージョンであれば特に追加で何かをインストールする必要はないはずです。
ほかのバージョンやvs2005については確認することができないので確かな情報ではないのですが、
各バージョンにあったVisual Stuido SDKというものをインストールすれば環境は整うと思います。
次にC++以外のプロジェクトを作成します。C++以外のプロジェクトというのはC#やVB.NETのことです。
プロジェクトが作成できれば、
「プロジェクト」メニューの「新しい項目の追加」もしくは
ソリューションエクスプローラでプロジェクト名を右クリックし「追加」→「新しい項目」とクリックしていくと新しい項目の追加ダイアログが出ます。
ここまではごく当たり前の手順です。
ですが次の手順は少し特殊(なのかな?)なので僕は最初少し戸惑いました。
どのような手順かというと、
- ダイアログ左側のカテゴリから全般を選択
- 右側のテンプレートの中からテキストファイルを選択
- ファイル名の拡張子を「txt」から「tt」に変更(ファイル名は任意でok)
T4には現状テンプレートがないようなので一旦テキストファイルを選択し拡張子をT4を表す「tt」に変更する必要があります。
次に実行環境ですが、こちらもVisual Studio上で行えます。
方法はソリューションエクスプローラ上の先ほど作成したT4のファイルを右クリックし『カスタムツールの実行」を選択するだけです。
編集途中の場合であれば、そのファイルを保存するだけで自動的にカスタムツールは実行されテキスト生成が行われます。
環境を説明したところでコードに戻ります。
<#@ template language="C#" #> <#@ output extension=".txt" encoding="Shift_JIS"#> Hello World!! <# for(int i = 0;i < 10;++i) { #> <#=i + 1#>_<#=System.DateTime.Now#> <# } #>
Hello World!! 1_09/07/2009 02:22:29 2_09/07/2009 02:22:29 3_09/07/2009 02:22:29 4_09/07/2009 02:22:29 5_09/07/2009 02:22:29 6_09/07/2009 02:22:29 7_09/07/2009 02:22:29 8_09/07/2009 02:22:29 9_09/07/2009 02:22:29 10_09/07/2009 02:22:29
コードにはC#のような部分とT4特有の部分が含まれています。
このコードを上から順に解説していきます。
まず1行目と2行めはそれぞれ<#@ #>で囲まれています。このタグで囲まれたものを『ディレクティブ』と呼びます。
CやC++が分かる方であれば、#defineのようなプリプロセッサみたいなものと思ってもらえると理解しやすいかもしれません。(実際はかなり別物ですが)
このディレクティブにはさまざまな種類があるので、今回は書いてある二つだけを説明します。
templateディレクティブはこのコードそのものの情報やオプションを指定します。
今回は記述する言語にC#を利用しているということを表す「language="C#"」というものを指定しています。ほかに指定できる言語に「VB」がありこれを指定した場合は次の部分にあるfor文をVBの構文で書くことができます。
templateディレクティブにはまだほかにも指定できるオプションがありますがそれらについて今回は触れません。
次にoutputディレクティブです。これは理解しやすいと思います。
extensionで出力するファイルの拡張子を指定し、encodingで保存する文字コードを指定します。
次に続くのはHello World!!の文字と空行です。
そしてこの二行はそのまま生成されたファイルに反映されています。
このようにどのタグにも囲まれていない部分に書かれている文字(改行だけの行を含む)はそのままファイルへ出力されます。
次の行からは慣れないとなかなか見にくい部分に入るのですが、真ん中の部分を省いてみると
<# for(int i = 0;i < 10;++i) { } #>
このように<# #>で囲まれたC#のfor文であることが分かります。<# #>で囲まれた部分を標準制御ブロックと呼び、上のlanguageで指定した言語を利用して制御文を書くことができます。
そしてもう一度全体を見ます。
<# for(int i = 0;i < 10;++i) { #> <#=i + 1#>_<#= System.DateTime.Now#> <# } #>
注目してほしいのはforループ開始直後と終了直前の部分に制御ブロックの終了タグと開始タグがあるということです。
こうすることで真ん中の<#=i + 1#>_<#=System.DateTime.Now #>と書かれている行がHello World!!のようにそのままファイルに出力される行になります。
ですが結果の出力を見てわかるとおりそのままの形で出力はされません。
ここで今回利用した最後のタグである<#= #>が威力を発揮します。
これは式制御ブロックと呼ばれ、その名の通り<#= #>の中にある式(変数やプロパティ、メソッド呼び出しなど)を評価し、結果を文字列に変換して(ToStringメソッドが利用される)その文字列をファイルに出力します。
なので最初の式制御ブロックでforループの制御変数であるiを含んだ i + 1 が評価されて出力、次に単純に_が出力、最後にもう一つの式制御ブロックの中でDateTimeクラスの静的プロパティであるNowが評価され実行したタイミングの時間が10回出力されるという結果になります。
これで今回提示したコードの解説はすべて終わりです。
正直今回説明したレベルではT4に大した使い道はありません。
思いつくのは数値計算などを高速化するためあらかじめ計算済みな静的なテーブルを用意するとき、そのテーブルの自動生成をするというようなことです。
このような場合.NetのMathクラスの関数を利用することができます。
MathクラスやDateTimeクラスが使えたようにT4では.Netの豊富なライブラリを利用することができます。
次回はライブラリを使う方法について解説しようと思います。
LINQの遅延評価とキャッシング
C#3.0からLINQという機能が加わったのはいまさらですが、まだ知らない部分があったので今回はそれを紹介します。
ちなみにLINQの基礎的な部分はここでは解説しないので別サイトを参照してください。
まずLINQでは遅延評価というものが行われます。lazy listと言ったりもします。
遅延評価を超簡単に説明すると、値が実際に必要とされるまで実行を先延ばしして処理にかかる時間を分散させることができる仕組みです。
この辺も詳しく説明されているサイトが別にあるので、詳しく知りたい方は頑張って探してね。
遅延評価が行われる構造の場合、二度同じ部分の値が必要になったとき、
一度目は実行して値を求めるのですが二度目は一度目の値を保存しておきそれをすぐに返すということをします。
これをキャッシングと言ったりするのですが、実はLINQの遅延評価の構造ではキャッシングが行われません。
つまり二度同じ部分の値を参照した場合、二度とも実行されます。
System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); IEnumerable<int> list = Enumerable.Range(0, 100).Where((num) => { System.Threading.Thread.Sleep(10); return num % 2 == 0; }); sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds.ToString()); sw.Reset(); sw.Start(); foreach (int i in list) i.ToString(); sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds.ToString()); sw.Reset(); sw.Start(); foreach (int i in list) i.ToString(); sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds.ToString());
これの実行結果は
1
1074
1074
となりました(僕の環境では)。
この結果から、一つ目の出力のWhereを使って0〜100までの偶数のリストを作っているようにみえる部分では実はまだ実行はされていないことがわかります。
そして、二つ目の出力で実際に必要になったときに実際に実行が行われていることがわかります。
最後に、三つ目の出力から一度行った実行をキャッシングしているのではなく再実行をしていることがわかります。
これでは単なる二度手間なのでこれを回避する方法ももちろんあります。
System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); IEnumerable<int> list = Enumerable.Range(0, 100).Where((num) => { System.Threading.Thread.Sleep(10); return num % 2 == 0; }).ToList();//ここでリストに変換 sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds.ToString()); sw.Reset(); sw.Start(); foreach (int i in list) i.ToString(); sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds.ToString()); sw.Reset(); sw.Start(); foreach (int i in list) i.ToString(); sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds.ToString());
最初の例からの変更点は、コメントでも書いているようにWhereの結果をそのままものすのではなくリストに変換して戻してやります。
これの実行結果は、
1075
0
0
のようになりました。
この実行結果からToList() (ToArray()などでもいい)で変換したタイミングで一度実行が行われ、
それ以降実際に値を利用するときは実行が行われていないことがわかります。
このような結果から、複数回値を利用する場合は一度ToList()などで変換してそれを使った方がいいでしょう。
で、ここまででLINQの遅延評価とキャッシングについては終わりです。
終りなのですが、もう少し書きたいことがあるので続けます。
まずはコードを示します。(あくまでも例なのでやっていることに大した意味はありません)
int count = 0; Action<IEnumerable<int>> action = null; action = (list) => { if (count++ > 1000) return; else { System.Diagnostics.Stopwatch sw = System.Diagnostics.Stopwatch.StartNew(); int num = list.Count(); sw.Stop(); writer.WriteLine(num.ToString() + "," + sw.ElapsedMilliseconds.ToString()); //csvファイルとして保存している //再帰呼び出しを行っている action(list.Skip(0));//list.Skip(0)がLINQのメソッド } }; action(Enumerable.Range(0, 10000));
この結果を図にして示します。
list.Count()で得られる数は変更を行っていないので常に一定です。
ですが回数を重ねるごとに(再帰が深くなるほどに)list.Count()の処理にかかる時間が増えています。
かなり上下にぶれはありますがだいたい線形で増加しています。
これについてちゃんとした検証をしていないのであくまで推測なのですが、
Count()でlistの要素の数えるためにはlistがちゃんとした実態を持っていないといけません。
つまりLINQで生成したlistの場合まだ評価が行われていないので、いったんLINQを実行してそのあとCount()で数を数えます。
ですが今回の例は再帰を使っています。
つまりLINQを実行する元になるIEnumerable型のlistも遅延評価のためにまだLINQの実行が行われていない可能性があります。
その場合その元になるlistももちろんLINQを実行しなければなりません。ですがさらにその元になるlistも遅延評価のためまだ実行が行われていない可能性が...以下略。
このように再帰が深くなっていくにつれ、未実行のlistも増えていきます。
なので図のように線形に計測にかかる時間が増えていったと予想されます(本当にあくまで予想です)。
これでは使いにくいので修正しましょう。
action(list.Skip(0).ToList());//LINQを実行したものを再帰の引数として渡す
修正したのは再帰呼び出しをしている一か所だけです。
コメントとして書いているように、変更内容は再帰の引数として渡すlistにToList()をすることによってLINQが実行済みの形に変更するだけです。
結果は乗せるまでもないですが一応、
すべて0です。
この図から、どんなに再帰が深くなったとしても処理が定数時間で終わっていることがわかります。
以上で今回の内容はすべて終了です。
結論は、
LINQを使うときは遅延評価であることを忘れずにさらにキャッシングが行われないということにも気をつけよう。
という感じですね。
それでは最後にこれに気づくことになったプログラムを乗っけて終わります。
内容はエラトステネスの篩をLINQを使ってうまいこと実装できないだろうかというような感じですが、結局満足のいくコードはできませんでした。
ちなみに高速化とか省メモリとか一切考えてないのでその辺の突っ込みはナシで。
Func<int, IList<int>> sieveOfEratoshtenes = (max) => { List<int> acc = new List<int>(); if (max > 1) { Action<IEnumerable<int>> sieve = null; sieve = (list) => { if (list.Count() == 0) return; int head = list.First(); acc.Add(head); sieve(list.Skip(1).Where((num) => num % head != 0).ToList()); }; sieve(Enumerable.Range(2, max - 1)); } return acc; }; IList<int> primes = sieveOfEratoshtenes(100); foreach (int num in primes) Console.WriteLine(num.ToString());