Boost」など、さまざまなカンファレンスを企画・運営しています。BOOKS(コードジン・ブックス)は、CodeZineの連載からカットアップした、開発現場の課題解決に役立つ書籍シリーズです。自作した正規表現エンジンが遅い理由の一つに、DFAの遷移関数が重いと言うことが上げられます。この遷移関数はNFAの遷移関数をラップしただけなので、実際はNFA上で遷移を行っています。DFAの遷移関数は、本来は遷移先を一つ返すだけなので非常に単純で高速なはずです。そこで、この高速性をとりもどすためにmemoizeデコレータを実装し、nfa2dfa関数内で使ってみます。memoizeデコレータは、関数の計算結果をキャッシュし、2度目以降の呼び出しを高速化する機能を持ちます。memoized_funcこれをnfa2dfaで利用します。サンプルコードでは@memoizeはコメントにしてありますので、試したい場合はこの部分を有効にして下さい。)ベンチマークの結果は以下のようになります。stmt='reg.matches(ur"FoO")').timeit(number=1000)0.014580965042114258memoizeによって約8倍速くなりました。次は非常に特殊な正規表現をマッチングさせてみましょう。"X*X*X*X*X*X*X*X*X*X*XXXXXXXXXX"と言う、X*を10個とXを10個並べた正規表現を用意します。この正規表現は、10個以上のXからなる文字列に対してマッチします。これに対して、"XXXXXXXXXX"と言うXを10個並べた文字列をマッチさせてみましょう。さきほどと同じく1,000回マッチングさせていますが、今度はreモジュールがが17秒なのに対して、dfaregは2秒で終わっています。Pythonで最適化も一切していないdfaregモジュールが、reモジュールより8倍速い計算です。してこのようなことが起こるのでしょう?NFAエンジンこの速度の違いは、DFAエンジンとNFAエンジンの違いによるものです。第1回で述べた通り、今回の連載で作成した正規表現エンジンは、DFAエンジンと呼ばれるタイプの物でした。一方で、PythonやPerl、Java、Rubyなどで広く利用されている正規表現エンジンは、NFAエンジンと呼ばれるタイプです。先ほどのベンチマークでわかった通り、NFAエンジンはある種の正規表現に対して極端な性能劣化を示します。先ほどの正規表現は"XXXXXXXXXXX*"と書き直すことができ、この正規表現に対しては速度劣化が起きません。このように、NFAエンジンでは書き方によってマッチングの速度が大きく変わってしまうため、パフォーマンス悪化を起こさないためにはある程度の知識が必要です。これは、RDBMSにおいて、SQLやインデクスに十分な知識がないと速度劣化を起こしてしまうのと似ています。正規表現を自動生成するようなコードがある場合は、意図せずこのような正規表現が生成される可能性があるので十分に注意が必要です。著)が大変参考になります。連載の締めくくりとして、NFAエンジンの仕組みを簡単に説明しておきます。Spencerさんが書いたライブラリがNFAエンジンの実装として広まった、と解説されています。この正規表現エンジンを動かし、NFAエンジンがどのように動作するのかを見てみます。UNIX系のOSをお持ちの方であれば、実際に動作させることができます。Spencerさんのサイトにて公開されている、regexp.old.tar.Zをダウンロードし、以下のようにmakeして下さい。make実行にはtryコマンドを使います。第1引数に正規表現、第2引数に文字列を渡します。DEBUGモードでコンパイルしているのでデバッグ情報が表示され、出力の最後にマッチ結果が0か1で表示されます。頃、両親に買い与えられたMZ-2500でプログラミングを始めた。学生時代、CGIの自作に没頭し、それ以降WEB開発の魅力に憑かれる。社会人になっても数学好きは変わらず、専門書を買い集めるのが最近の趣味。NEW1DMM.comの施策から見る、事業をむしばむ「技術負債」への処方箋──リファクタリングの「言語化」でインシデントを予防2企業の7割超が「2025年の崖」を理解していないことが明らかに。NEW1DMM.comの施策から見る、事業をむしばむ「技術負債」への処方箋──リファクタリングの「言語化」でインシデントを予防2企業の7割超が「2025年の崖」を理解していないことが明らかに。NEW1DMM.comの施策から見る、事業をむしばむ「技術負債」への処方箋──リファクタリングの「言語化」でインシデントを予防2企業の7割超が「2025年の崖」を理解していないことが明らかに。12:00法務担当者、6割超が今後業務で「生成AIを使用したい」と回答。NEW新着記事一覧を見るイベント今後の予定を見るCodeZineは、株式会社翔泳社が運営するソフトウェア開発者向けのWebメディアです。「デベロッパーの成長と課題解決に貢献するメディア」をコンセプトに、現場で役立つ最新情報を日々お届けします。イラストの無断転載を禁じます。記載されているロゴ、システム名、製品名は各社及び商標権者の登録商標あるいは商標です。