5月24日

2011/5/24作成

lintプログラム12時間経過で2000件まで進んだ。全部で147万件あるから、単純計算で367.5日掛かることに。。。随分高速化したと思ったけど、それでも1年かかるのかよ。こりゃやってられんということで、とりあえず停止。

これまで出来上がったレポートを眺めてみたけど、1文字2文字の記事のリンク候補の検出が多いな。実質的にはこれはノイズなんで除外した方がよさそう。レポートが無駄に長くなっても読みにくいだけだし、処理速度も多少は速くなるだろう。

遅い根本原因は、リンク候補を探すために全てのテキストに対して全ての記事名を単純文字列検索を掛けているということだ。今更ながら、なんかいい方法はないかとアルゴリズム辞典を引っ張り出してきて眺めてみる。

文字列検索を高速化する方法として、KMP法、BM法が挙げられている。ただ、これらの方法はいずれも事前に表を作るもの。例題は英文テキストのみを対象にしているけど、ウィキペディアの文章はUNICODEなんだから、表もどんだけでかくなることか。って、今時のパソコンにとっては大したことはないかな。

この期に及んで、更にチェック項目を追加したりとか。いや、レポートを眺めていたり、編集したりしていると、ついつい思いついてしまうもんで。

最近、また腰痛がでるようになってきた。原因は多分椅子に長時間座っていることだろうな。しかも、姿勢悪いし。

根本的にはアルゴリズムを変更すべきだけど、小手先の手法として正規表現を使う方法を思いついた。今は記事名分だけループをまわしてindex() で検索しているけど、件数が多い場合は、|で繋いだ正規表現で一気にマッチングした方が速いというのは以前発見した。

ということで、記事名全部を繋げた凶悪に巨大な正規表現パターンを作ってみた。つまり、/記事1|記事2|記事3|...|記事n/みたいなのね。こんなのほんとに処理できるんだろうか。perlの信頼性を信じよう。

ということでやってみたら、凄い!テストデータで10分掛かってたのが1分半に短縮された!凄いぞ正規表現。バカでも速いプログラムが組めるようになってるんだ。いやぁ、車輪を発明してくれた人には感謝感謝だわ。

だいぶ高速化できたので、現時点でどれくらいの速度か計るために、再び本番データで実行。開始は18時半。さて、どれだけ速くなったか。

が、全然進まん。あれ?なんでだ?かなり高速化されたと思ったのに。って、正規表現パターンのサイズが大きすぎ?いくらなんでも詰め込みすぎたか。もしかしたらCPUキャッシュからはみ出してしまって遅くなってるのかもしれんな。

試しに正規表現パターンのデータをダンプしてみたら14MBもあったよ。こらあかん。ということは、パターンを細切れに作ってループをまわすとかそういう処理が必要になるということか。ああ、めんどくさい。つうか、CPUキャッシュサイズを考慮したプログラミングをしなきゃいかんことになるとは思わんかった。

めんどくさいとも言ってられないので、正規表現パターンを分割する処理を組み込む。テストデータで実行すると、当然ながら遅くなる。まあ、仕方が無いわな。午前1時に本番データで実行開始して就寝。明日の朝にどこまで進んでいることか。


あおやぎのさいと2.0 新人うぃきめでぃあん日記