ワイルドなワイルドカード処理

週末、仕事上の知人と酒を飲みました。プログラマの鉄板ネタとして「最近見たヒドいコード」という話題がありますが、そういえばとそこで話したネタをここにも書いておきます。

よくある社内業務のWebアプリを思い浮かべてください。自分が処理する事案を検索するために、例えば案件番号を入力できるとしましょう。そして、案件番号にはワイルドカードが使えるとします。例えば、「ABC*」と入力すると「ABCA90」と「ABCD70」が表示されるけど、「ABEF30」は表示されないとか、そういう奴です。よくありますよね。

で、この画面がすごく遅い。別段他に難しい処理をしているわけではなく、ワイルドカードを指定すると遅い。ちゃんとワイルドカード処理をすると結構大変なので、前方一致だけ（つまり、案件番号の先頭が何かということしかワイルドカードで指定できない）でいいよという話だったんですが、もしかしていろいろとやっちゃってるんでしょうか。

担当者に聞いてみると、「いや、タンバリンさん、いろいろとか無理です。前方一致で精一杯」という回答。えー？

前方一致の処理は単純です。入力された文字列をS1、比較対象の文字列をS2とすると

1. S1の末端から「*」を取り除く
2. S1の1文字目とS2の1文字目を比較する
3. S2の2文字目とS3の2文字目を比較する。これをS1の最後の文字まで繰り返す

JavaだとstartsWith()というようなメソッドがありますから、1文字ずつ比較する必要すらないです。んー、何がそんなに難しいのか。

というわけで、コードの中を見てびっくり。こんな処理になっていました。

1. 文字列の集合SGを用意する
2. SGに「*」を加える
3. S2の1文字目と「*」を連結してできた文字列をSGに加える
4. S2の1文字目と2文字目と「*」を連結してできた文字列をSGに加える。これをS2の最後の文字まで繰り返す
5. S1がSGに含まれるかチェックする

斬新です。そしてワイルドです。そして確かに前方一致だけじゃなかったらすごく難しそう。「『ABCDE』にマッチするワイルドカードの集合」を取得する・・・？えーっと、そもそも、その集合って有限かな。「*」が連続してはいけないというルールがあれば、有限になるか。うーん・・・

驚きに満ちた職場からお伝えしました。現場からは以上です。