Hatena::ブログ(Diary)

当面C#と.NETな記録 このページをアンテナに追加 RSSフィード

2007/5/9 (水)

[] FizzBuzz  FizzBuzzを含むブックマーク  FizzBuzzのブックマークコメント

コンピュータサイエンス学科卒業生の過半数は1から100までの数をプリントするプログラムを書けない

http://www.aoky.net/articles/jeff_atwood/why_cant_programmers_program.htm

via オレンジニュース

1から100までの数をプリントするプログラムを書け。ただし3の倍数のときは数の代わりに「Fizz」と、5の倍数のときは「Buzz」とプリントし、3と5両方の倍数の場合には「FizzBuzz」とプリントすること。

danさんとこ http://blog.livedoor.jp/dankogai/archives/50826507.html

あなごる FizzBuzz http://golf.shinh.org/p.rb?FizzBuzz

やべぇ、125byteから縮まらないんだけど。ってそういうことじゃないか。

それはそれとして、あなごるで遊ぶとプログラミング力が付く。縮める方向の力だけじゃなく。

はてブ http://b.hatena.ne.jp/entry/http://www.aoky.net/articles/jeff_atwood/why_cant_programmers_program.htm

[][] メタプログラミングと動的生成  メタプログラミングと動的生成を含むブックマーク  メタプログラミングと動的生成のブックマークコメント

FastPropertyComparerはいろいろ試しているうちにぶくぶくと大きくなってしまい、ついでに.NETのライブラリを拡張するかのような大きな目標とあいまって、テスト項目が大変なことになってしまってます。MSの波村さんの苦労がちょっとわかりました(^^; 様々な型を考えるとすぐにテスト項目の組み合わせが爆発します…。なので、お披露目はもう少し先です。おそらく全部テストしきれず永遠のベータってことにw 連休も終わって時間もあれだし。FastPropertyComparerを書くメタプログラミングは.NET全般の知識を試されてるようで、気軽にはじめた割りに結構つらくなってきてたりもします(^^;

今回、メタプログラミング(ほぼ)初体験だったので様々な未知の技術に触れました。どうせすぐに忘れるので、解説を残しておきます。


PropertyComparerは何をする人?

大前提のあたりから順に振り返って見ていきます(って偉そうにスミマセン)。

PropertyComparerはList<T>などを、T型のあるプロパティ(型はU)の順にソートするために使う比較処理です。って文章だとややこしいですね。

class Employee
{
  private string _name;
  public string Name { get { return this._name; } }
...
}

このようなEmployee型が入ったList<Employee>を、プロパティNameの順でソートするために使います。

PropertyComparerはどんな型のどのプロパティでも比較して結果を返す汎用の処理です(正確にはpublicなgetアクセサ限定)。比較処理と言っても、getアクセサから値を読んで別の比較処理に値を渡すだけのアダプタです。

Employeeが定義済みであれば、

list.Sort( delegate( Employee x, Employee y )
  { return string.Compare( x.Name, y.Name ); } );

でName順にソートできます。

でも、PropertyComparerはどんな型のどのプロパティでも比較して結果を返す汎用の処理です。Employee型も、それがNameプロパティを持ってることも知らないけど、それでもPropertyComparerを書くにはどうするのか?これはリフレクションでできますね。MSDNコラムの記事では比較のたびにリフレクションでプロパティを読んでいました。

ところで、リフレクションは遅いという問題があります。structを書いたらEqualsをオーバーライドしろと言われるのもパフォーマンスの理由からです。

(といってもPropertyComparerは人間が気付くほど遅いわけではないので、普通は気にしません。今回は別の目論見もあって高速化しました)


どうやって高速化したの?

何千回とか呼ばれる比較処理のたびにリフレクションを使ってNameを読んだのでは遅いので、代わりにEmployee型のNameを直接読んで比較する処理を実行時に動的に生成してしまいます。*1 生成処理は速いのか遅いのかわかりませんが一度きりなので、何度も何度も呼ばれる比較処理が速いのならば高速化できます。

どんな型のどのプロパティを比較するのかわからないと言っても、PropertyComparerが呼ばれたときには既にどちらもわかっています。PropertyComparerを書く時点ではわからないだけです。PropertyComparerが呼ばれるときってのは、Employeeが並んだDataGridViewのNameのコラムヘッダをクリックしたときです。Employee型の、string型のNameで比較する処理を生成しろとコンストラクタに指示がきます。


動的生成って具体的には?

.NETは動的生成に特別な関心があるようで、バージョンアップのたびに新しい技術が追加され、徐々に使い易いものになってきています。IL生成、CodeDOMを使ったコード生成やコンパイル、そしてC#3.0ではExpression Treeが追加になります。それぞれについてはよく知らないので説明はなし。ジェネリックも親戚と言えるかも。すべての言語はLispに回帰するって言葉を地で行ってます。

今回はILをゴリゴリ書きました。CodeDOMが面倒そうだった、生成するコードがごく短いものだった、生成するコードのうち状況に応じて変わる部分がごく少なかったことからです。C#で書いてコンパイルしたものをILdasmで見て真似ただけです。それでもいろいろはまりましたが(^^;

生成したILはC#で書けば上で見たようにたった一行で書ける処理です。このうち、動的に変わるのは 1.比較する型(Employee型)、2.比較処理(string.Compare())、3.プロパティとその型(x.Name/y.NameのName) の3つです。これらを詳しく見ていきます。

「1.比較する型(Employee型)」はMSDNコラムのコードで既にPropertyComparer<T>のTとして、型パラメータになっています。

「2.比較処理(string.Compare())」はプロパティの型に応じた比較処理にします。Comparer<U>.Default.Compare( a, b ); が使える場面ですが、プロパティの型Uが型パラメータとして必要になります。id:siokoshou:20070504でプロパティの型を型パラメータに持ってきたのはこのためです。これについては後で詳細を書きます。

「3.プロパティとその型(x.Name/y.NameのName)」ってのはgetアクセサ、つまりメソッドです。id:siokoshou:20070505でILによるメソッドコールを生成しました。これにはgetアクセサのMethodInfoが必要です。メソッドがわからないと呼べません。


ILの生成ってどうやるの?

アセンブリを生成する大げさな方法と、DynamicMethodクラスで軽量のグローバルメソッドを作る方法があります。今回は小さなコード生成なのでDynamicMethodがピッタリです。

リフレクション出力による動的メソッドのシナリオにDynamicMethodの詳しい説明があります。このドキュメントには、どんなときに動的生成を使えば良いのかヒントが並んでます。夢が広がります。手順は方法 : 動的メソッドを定義および実行するが詳しいです。

DynamicMethodクラスは実行時にstaticメソッドを作ります。Dynamicなのかstaticなのか、ややこしいんですがわざとですか?w ここのstaticはインスタンスメソッドに対するクラスメソッドの方のstaticです。クラス名がCreateMethodとかだったらよかったのに。

生成されるのがstaticメソッドなのでインターフェイスのメソッドを持てません。PropertyComparer<T>がIComparer<T>だったのに、FastPropertyComparerがデリゲートのComparison<T>を使うのはこのためです。DynamicMethodは作ったstaticメソッドを最後にデリゲートにするので、これを利用しています。

ILの説明をだらだら書いてもつまらないので説明は省略します。命令セットがごく少ないので読むのは容易だと思います。書くのはちょっと、ね(^^;


動的にジェネリック型のインスタンスを構築する方法

プロパティの型Uは実行時までわかりません(しつこいですね)。しかし、FastPropertyComparer<T, U>型のTとUが決まった型のインスタンスが欲しいので、これを実行時に構築します。ちなみに型TはSortableBindingList<T>のTと同じ型です。this.bindingSource.DataSource = new SortableBindingList<Employee>( list ); のように使い、この場合型パラメータTの型引数はEmployeeです。

型パラメータと型引数って用語は大丈夫?仮引数(parameter)と実引数(argument)です。定義で使用されるFastPropertyComparer<T, U>のTとUは型パラメータ。実際に使用するときのFastPropertyComparer<Employee, string>のEmployeeとstringが型引数です。

ジェネリック型定義に実行時に型引数を与えて、インスタンスを生成するコードを見てみます。

// FastPropertyComparer<T, U> (Uはプロパティの型) を動的に生成
Type seed = typeof( FastPropertyComparer<,> );
Type[] typeArgs = { typeof( T ), propertyType }; // propertyTypeはプロパティの型のTypeインスタンス
Type pcType = seed.MakeGenericType( typeArgs );
IPropertyComparerFactory<T> factory =
  ( IPropertyComparerFactory<T> ) Activator.CreateInstance( pcType );

動的にジェネリック型のインスタンスを構築するってなんだか難しそうですがジェネリック型のインスタンスの構築に一行一行説明があって、DataGridViewを使いこなすより遥かに簡単です。

FastPropertyComparer<,>(見慣れない形です)のTypeに、型引数typeArgsを引数にしてMakeGenericTypeを呼べば具体的な型(pcType)のできあがりです。seedは型引数が決まっていない型(これを開いている型という)、pcTypeは型引数が決まった型(閉じている型)です。

Activator.CreateInstanceはpcTypeのインスタンスを作っています。こいつ、Remotingでも使いますね。CreateInstanceの戻り値はobjectなので、FastPropertyComparer<T, U>のメソッドを呼ぶにはキャストが必要です。FastPropertyComparer<T, U>にキャストしたいところですが、Uは実行時に決まるので ( FastPropertyComparer<T, U> ) とは書けません。卵と鶏問題ですw そこであらかじめ適当なインターフェイスを定義しておいてキャストして呼んであげます。


(おまけ) MSDNコラムのPropertyComparerはどこが気に入らない?

Equals( T xWord, T yWord ) をPropertyComparerクラスが持つってのはおかしい。何か勘違いしている。CompareAscending()とCompareDescending()をわざわざ持っているのも変だけど、Equals( T xWord, T yWord )に比べればどうでもいい。便利なクラスなだけに、おしい。

時間があれとか書いておいて、なげーw 以上!

[] 一方WPFは…  一方WPFは…を含むブックマーク  一方WPFは…のブックマークコメント

http://msdn2.microsoft.com/en-us/library/ms745786.aspx

えーっと…。FastPropertyComparerはいらない子? orz

*1Rubyのsort_byではNameが重い処理の場合のことを考えて、一度Nameを呼んでその値を溜め込み、溜めた値を比較するようです。

トラックバック - http://d.hatena.ne.jp/siokoshou/20070509
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 06 | 09 | 11 | 12 |
2007 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 08 | 09 | 10 | 12 |
2009 | 01 | 03 | 04 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 07 |
2011 | 04 | 07 | 10 |
2012 | 04 | 12 |
2013 | 08 |
2014 | 03 | 08 |