2

次の2ブロックのコードがあります：

def replace_re(text):
    start = time.time()
    new_text = re.compile(r'(\n|\s{4})').sub('', text)
    finish = time.time()
    return finish - start

def replace_builtin(text):
    start = time.time()
    new_text = text.replace('\n', '').replace('    ', '')
    finish = time.time()
    return finish - start

テキストパラメータ（1つのWebページのソースコードの〜500kb）を使用して両方の関数を呼び出すよりも。replace_re()私ははるかに速くなると思いましたが、結果は次のとおりです。

  1. replace_builtin()〜0.008秒
  2. replace_re()〜0.035秒（約4.5倍遅い!!!）

何故ですか？

4

4 に答える 4

7

正規表現は、固定文字列の置換よりも4.5倍以上複雑だからです。

于 2012-06-29T08:35:35.857 に答える
5

reは FSM を生成する必要があるためです。次に、それを使用して文字列を処理します。置換では、lib/OS レベルに近い基になる文字列処理関数を使用できます。

于 2012-06-29T08:39:32.953 に答える
3

経験則

固定文字列の一致は、正規表現の一致よりも常に高速である必要があります。さまざまなベンチマークをGoogleで検索することも、自分で行ったことを実行して自分で実行することもできますが、一般的には、（おそらく）いくつかの異常なエッジケースを除いて、これが当てはまると想定できます。

正規表現が遅い理由

これが当てはまる理由は、固定文字列の一致には、バックトラック、コンパイルステップ、範囲、文字クラス、または正規表現エンジンの速度を低下させるその他の多くの機能がないという事実と関係があります。正規表現の一致を最適化する方法は確かにありますが、一般的なケースでは、文字列へのインデックス作成に勝るものはないと思います。

ソースを使用する

より良い説明が必要な場合は、関連するモジュールのソースコードをいつでも調べて、それらがどのように機能するかを確認できます。それは確かに、特定の実装がそのように実行される理由についてのより多くの情報を提供します。

于 2012-06-29T08:47:03.217 に答える
3

1 つのスペース文字ごとにソース文字列で何が起こるかを考えてみてください。正規表現エンジンは、次の 3 つの文字を調べて、それらがスペースでもあるかどうかを確認する必要があります。したがって、すべてのスペースには、本質的に、次の文字も見ることが含まれます。ほとんどのREエンジンはそれほど書かれていません...率直に言って...しかし、それは本質的に、エンジンが開始状態に戻り、構築していた以前の一致状態で構築されたデータを破棄する可能性があることを意味します.

ただし、固定パターン (4 つのスペース) の文字列の検索は、実際にはサブリニア時間で実行できます。Python がこのように実装されているかどうかはわかりませんがreplace()、彼らが自由に使えるツールをうまく使っていることを願っています。

于 2012-06-29T08:43:16.087 に答える