Onigmoのインタプリタをdirect threaded codeに置き換えてCRubyを8%高速化した話 - 開発日記

2021/10/18 5 users インタプリタ CRuby switc 技法 Ruby言語

Ruby言語の正規表現エンジンとしても使われているOnigmo(鬼雲)を高速化したのでその話をします。 Onigmoでは、正規表現のマッチにはバイトコードインタプリタを用いてNFAの実行をしています。バイトコードインタプリタの高速化には古くから知られている技法として、direct threaded codeがあり、この技法を用いればswitc... 続きを読む

Island Life - O(n^2)正規表現

2011/10/20 24 users Island Life 正規表現 n^2 マッチ エンジン

O(n^2)正規表現 Javaで、 /[-_.0-9A-Za-z]+@[-_0-9A-Za-z]+[-_.0-9A-Za-z]+/ という正規表現のマッチが 入力文字列長nに対してO(n^2)かかるのはエンジンがNFAのせいって話なんだけれど、 これNFA関係無くないかな。 メールアドレスの正規表現がめちゃめちゃ遅くなることがある件について - Mi manca qualche giovedi? ... 続きを読む

きまぐれ日記: はてなキーワードを高速に付与

2005/09/18 186 users 付与 きまぐれ日記 はてなキーワード 人づて perl

人づてに聞いた話なのですが、はてなキーワードを実際の blog に付与する処理は、巨大な正規表現で行っているそうです。実際に調べてみると、以下のサイトからキーワード付与API と正規表現が入手できます。 http://d.hatena.ne.jp/hatenadiary/20040205 本当にはてな内部では正規表現を使っているのでしょうか? perl の 正規表現エンジンは NFA なので、単純... 続きを読む