30

次の Python コードを検討してください。

import timeit
import re

def one():
        any(s in mystring for s in ('foo', 'bar', 'hello'))

r = re.compile('(foo|bar|hello)')
def two():
        r.search(mystring)


mystring="hello"*1000
print([timeit.timeit(k, number=10000) for k in (one, two)])
mystring="goodbye"*1000
print([timeit.timeit(k, number=10000) for k in (one, two)])

基本的に、大きな文字列内のいくつかの部分文字列のうちの 1 つの存在を確認する 2 つの方法をベンチマークしています。

ここで得られるもの (Python 3.2.3) は次の出力です。

[0.36678314208984375, 0.03450202941894531]
[0.6672089099884033, 3.7519450187683105]

最初のケースでは、正規表現は式を簡単に打ち負かしますany。正規表現は部分文字列をすぐに見つけますanyが、正しい部分文字列に到達する前に文字列全体を数回チェックする必要があります。

しかし、2 番目の例では何が起こっているのでしょうか。部分文字列が存在しない場合、正規表現は驚くほど遅くなります! 理論的には、正規表現は文字列を 1 回だけ通過する必要があるのに対し、any式は文字列を 3 回通過する必要があるため、これには驚かされます。ここで何が問題なのですか？私の正規表現に問題がありますか、それともこの場合 Python の正規表現が単に遅いのでしょうか?

4

4 に答える 4

27

今後の読者への注意

実際、正しい答えは、Python の文字列処理アルゴリズムがこの場合に最適化されており、モジュールが実際reには少し遅いということだと思います。以下に書いたことは真実ですが、おそらく質問にある単純な正規表現には関係ありません。

元の回答

どうやらこれはたまたまのまぐれではなく、Python のreモジュールは実際には低速です。DFA を構築してシミュレートするのではなく、一致が見つからない場合は、再帰的なバックトラッキング アプローチを使用しているようです。

正規表現に後方参照がない場合でも、バックトラッキング アプローチを使用します。

これが意味することは、最悪の場合、Python 正規表現は線形ではなく指数関数的に時間がかかるということです!

これは、問題を説明する非常に詳細な論文です: http://swtch.com/~rsc/regexp/regexp1.html

最後の近くにあるこのグラフは、それを簡潔に要約していると思います。 さまざまな正規表現の実装のパフォーマンスのグラフ、時間と文字列の長さ

于 2012-06-25T15:31:54.057 に答える
3

同僚が re2 ライブラリ ( https://code.google.com/p/re2/ ) を見つけましたか? Pythonラッパーがあります。一部のシステムにインストールするには少し時間がかかります。

私はいくつかの複雑な正規表現と長い文字列で同じ問題を抱えていました.re2は処理時間を大幅に短縮し、秒からミリ秒に短縮しました.

于 2014-10-07T17:11:38.103 に答える
2

正規表現が非常に遅い理由は、文字列全体を処理する必要があるだけでなく、すべての文字で複数の計算を行う必要があるためです。

最初のものは単にこれを行います：

Does f match h? No.
Does b match h? No.
Does h match h? Yes.
Does e match e? Yes.
Does l match l? Yes.
Does l match l? Yes.
Does o match o? Yes.
Done. Match found.

2番目のものはこれを行います：

Does f match g? No.
Does b match g? No.
Does h match g? No.
Does f match o? No.
Does b match o? No.
Does h match o? No.
Does f match o? No.
Does b match o? No.
Does h match o? No.
Does f match d? No.
Does b match d? No.
Does h match d? No.
Does f match b? No.
Does b match b? Yes.
Does a match y? No.
Does h match b? No.
Does f match y? No.
Does b match y? No.
Does h match y? No.
Does f match e? No.
Does b match e? No.
Does h match e? No.
... 999 more times ...
Done. No match found.

と正規表現の違いについては推測することしかできませんがany、正規表現は非常に複雑なエンジンで実行されるため遅く、ステート マシンなどすべてを使用すると、特定の実装ほど効率的ではないのではないかと推測しています。 ( in)。

最初の文字列では、正規表現はほぼ瞬時に一致を見つけますが、any何かを見つける前に文字列を 2 回ループする必要があります。

ただし、2 番目の文字列では、anyは基本的に正規表現と同じ手順を実行しますが、順序が異なります。これはany、おそらくより単純であるため、ソリューションがより高速であることを示しているようです。

特定のコードは、一般的なコードよりも効率的です。問題に関する知識は、ソリューションの最適化に利用できます。複雑なコードよりも単純なコードが好まれます。基本的に、正規表現は、パターンが文字列の先頭に近いin場合は高速ですが、パターンが文字列の末尾に近い場合、またはパターンがまったく見つからない場合は高速です。

免責事項: 私は Python を知りません。私はアルゴリズムを知っています。

于 2012-06-25T14:17:00.997 に答える
1

3 つの正規表現で構成される正規表現があります。正規表現がこれを3回チェックしないとしたら、それはどのように機能すると思いますか? :-) コンピューティングに魔法はありません。それでも 3 つのチェックを行う必要があります。

しかし、regexp は 3 つのテストをそれぞれ 1 文字ずつ実行しますが、"one()" メソッドは次のマッチに進む前に文字列全体をチェックして 1 つのマッチをチェックします。

最初のケースで正規表現がはるかに高速なのは、最後に一致する文字列をチェックするためです。つまりone()、最初に文字列全体から "foo" を探し、次に "bar" を探し、次に "hello" を探し、一致する場所を探す必要があります。最初に "hello" を移動すると、one() と two() はほぼ同じ速度になります。どちらの場合も最初の一致が成功するからです。

正規表現は「in」よりもはるかに複雑なテストなので、遅くなると思います。「|」を使用すると、この複雑さが大幅に増加すると思われますが、正規表現ライブラリのソースを読んでいないので、何を知っていますか. :-)

于 2012-06-25T14:22:39.110 に答える