こんにちは。最近はRails(Ruby)とかばっかり書いてますが、久しぶりにC#ネタです。なぜならC# Advent Calendar に参加してしまった為です!(今年初めてしりましたが、昨年もあったのでしょうか)
最近、形態素解析(自然言語処理)をやる機会があり、入力の文字列が文字コード順に並んでいる辞書の中にあるか探索するコードを書きました。
線形探索は、以下のようなコードになります。this.dictionaryはList
public string[] LinerSearch( string input ) { foreach( string[] entry in this.dictionary ) { if( entry[0] == input ) { return entry; } } return null; }
これは特に問題ないと思います。ただ時間がかかります。*1
そこで二分探索をしてみます。二分探索は、簡単に言えば、「ソート済みのリストに対して、中間地点から探索対象が左側か右側かのどちらかに含まれるかを判定し、これを再帰的に繰り返して目的の値を探す手法」という感じでしょうか。詳しくは「二分探索 - Wikipedia」などを参照してください。*2
二分探索を用いると、以下のようなコードになります。
public string[] BinarySearch( string input ) { int head = 0; int half = 0; int tail = this.dictionary.Count - 1; while( head <= tail ) { half = ( head + tail ) / 2; int result = strcmp( input, this.dictionary[half][0] ); if( result == 0 ) { return this.dictionary[half]; } else if( result == 1 ) { head = half + 1; } else if( result == -1 ) { tail = half - 1;} } return null; }
しかし二分探索では文字列比較で、探索している文字列と候補の文字列が「等しい/異なる」の情報だけでなく、「どちらが(文字コード的に)前にある/後ろにある」という情報も必要です。
C言語では標準ライブラリに「strcmp」という関数があります。これを使えば「等しい/異なる」の他に、異なった場合の返り値が
- 第1引数が第2引数よりも大きければ正の値
- 第2引数が第1引数よりも大きければ負の値
という決まりに従って返ってくるので「どちらが(文字コード的に)前にある/後ろにある」ということも分かります。また結果は比較する文字列の長さに関係しない必要があります。「A」と「AA」を比較したときは「Aのほうが前である(返り値として「-1」)」が返ってきます。
しかしC#にはこのようなメソッドが見つかりませんでした。あったようです。MSDN Library力が足りませんね。精進します。
書いてみたところ、以下のようになりました。
private int strcmp( string input, string candidate ) { if( input == candidate ) { return 0; } else // input と candidate を byte ごとに見る { Encoding eucEncoding = Encoding.GetEncoding( "EUC-JP" ); byte[] byteInput = eucEncoding.GetBytes( input ); byte[] byteCandidate = eucEncoding.GetBytes( candidate ); // 長さの短い方を length とする int length = byteInput.Length <= byteCandidate.Length ? byteInput.Length : byteCandidate.Length; for( int i = 0; i < length; i++ ) { if( byteInput[i] < byteCandidate[i] ) { return -1; } else if( byteInput[i] > byteCandidate[i] ) { return 1; } } if( byteInput.Length == byteCandidate.Length ) { return 0; } else if( byteInput.Length < byteCandidate.Length ) { return -1; } else { return 1; } } }
これを使えば前述のコードで二分探索が可能になります。
本当にC#にこのようなメソッドが無いのか あったようです
「==」や「Equals」での比較では等しいかそうでないか(Boolean値)、しかわかりません。結局、strcmpのようなメソッドは見つかりませんでした。
しかし、「Microsoft.VisualBasic.CompilerServices名前空間」に「StringType.StrCmpメソッド 」というメソッドがありました。説明を読んでみると、C標準ライブラリのstrcmpと同じようなことをやるようです。
ただ、MSDN Libraryの記述によれば
この API は、.NET Framework インフラストラクチャをサポートします。独自に作成したコードから直接使用するためのものではありません。
とあります。これは結局「自分で書いたコードから、このメソッドを使わないでね。」ということだと思いますが、このようなメソッドがなぜpublicで宣言されているのでしょうか。internalで宣言すれば良かったのでは...。
理由をご存知の方は誰か教えてください。
一応ソースをおいておきます
*1:線形探索では、n個のデータから1つを探すときは「(最悪)O(n)」の計算時間が必要になります(最初から最後まで値を比較することになる可能性がある)。
*2:二分探索では「O(log2 n)」で探索することができます。計算時間量につていは「26.1.6.34 二分探索の計算量 - HWB」の比較表が分かり易いです