パスワードを忘れた? アカウント作成
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

「無印良品」公式サイト、年末から続くメンテナンスが終わらず。再稼働は1月下旬予定」記事へのコメント

  • unixのコマンド内蔵正規表現ライブラリ、単独の正規表現ライブラリなんかでも、
    同じ処理で、一瞬で処理が済んだり、フリーズしたかとおもうくらい時間がかかったりする

    商用UNIXの正規表現ライブラリがクソ遅くて、
    Linux(GNUのコマンド類)じゃ一瞬で動くものが、
    商用UNIXではフリーズしたかの如く時間がかかるパターンとかにあったことがある

    • それはたぶん、ライブラリが使ってるアルゴリズムの問題。

      「正規表現のマッチング問題」は、そのまま素直に実装した場合、「*」などの繰り返しは割り当てを変えて繰り返す(バックトラック)ことになります。
      そのため、パターンによってはものすごく時間がかかることになり、最悪値だと、長さnに対して O(2n) の時間が必要。

      ところで、「正規表現のマッチング問題」はそのまま「非決定性有限オートマトン受理問題」に一対一対応するのですが、「非決定性有限オートマトン」は「決定性有限オートマトン」への変換が可能です。決定性の場合、バックトラック不要で、一回読み進めるだけで判定可能。処理時間はO(n)です。
      そのかわり、「非決定性から決定性への変換」という事前処理が必要ですし、決定性有限オートマトンはメモリ消費がすごく大きくなります。こっちがO(2n)になる。

      どちらも利点欠点がありますが、最近はメモリに困ることはないので、決定性のデメリットは薄いですね。

      UNIX古来のツールでいうと、grepは非決定性で、egrepは決定性変換してる。
      egrepは検索はものすごく速いけど、(オートマトンの変換で)検索開始までちょっと待たされるので、
      昔は検索内容と検索量でgrepとegrepを使い分けてたりしましたが、
      今は何も考えずにegrepですね。ていうかGNUはgrepもegrepも実体は同じ(オプション違い)だし。

      親コメント
    • by Anonymous Coward

      それはIBMのlocaleライブラリがglibcに取り込まれる前の話ではないだろうか?

Stableって古いって意味だっけ? -- Debian初級

処理中...