「同等の」一致しない正規表現のタイミングが大きく異なりますか？

Question

私は最近、質問 "A Regex that will never be matched by anything"（my answer here、詳細については、参照）のための正規表現の束を計時しました。

しかし、私のテストの後、正規表現'a^'と'x^'は、同一である必要がありますが、確認には大幅に異なる時間がかかりました。 （私はキャラクターを切り替えただけで偶然でした）これらのタイミングは以下の通りです。 Pythonは'a^'作ること、ここで何をしているのですhttps://regex101.com/r/AwaHmK/1

：（ちょうど最初の50行で）

In [1]: import re 

In [2]: with open('/tmp/longfile.txt') as f: 
    ...:  longfile = f.read() 
    ...:  

In [3]: len(re.findall('\n',longfile)) 
Out[3]: 275000 

In [4]: len(longfile) 
Out[4]: 24733175 

... 

In [45]: %timeit re.search('x^',longfile) 
6.89 ms ± 31.1 µs per loop (mean ± std. dev. of 7 runs, 100 loops each) 

In [46]: %timeit re.search('a^',longfile) 
37.2 ms ± 739 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 

In [47]: %timeit re.search(' ^',longfile) 
49.8 ms ± 844 µs per loop (mean ± std. dev. of 7 runs, 10 loops each) 

オンラインテストは（1441880のステップと〜710ms対のみ40858ステップと〜113ms）と同じ挙動を示しています'x^'よりもずっと時間がかかりますか？

---

だけtimeitやIPythonの内側で起こって何かがあった場合、私はシンプルなタイミング機能を自分で書いて、すべてがチェックアウトを確認する：

In [57]: import time 

In [59]: import numpy as np 

In [62]: def timing(regex,N=7,n=100): 
    ...:  tN = [] 
    ...:  for i in range(N): 
    ...:   t0 = time.time() 
    ...:   for j in range(n): 
    ...:    re.search(regex,longfile) 
    ...:   t1 = time.time() 
    ...:   tN.append((t1-t0)/n) 
    ...:  return np.mean(tN)*1000, np.std(tN)*1000 
    ...: 

In [63]: timing('a^') 
Out[63]: (37.414282049451558, 0.33898056279589844) 

In [64]: timing('x^') 
Out[64]: (7.2061508042471756, 0.22062989840321218) 

私もIPythonの外で私の結果を複製し標準の3.5.2シェルです。したがって、奇妙はIPythonまたはtimeitのいずれかに制約されません。

Answer 1

リンクされた質問に記載されているように、この正規表現はテキスト全体をスキャンします。

表示される不一致は、aが英語テキストのような一般的な文字であり、 "読み取り可能な"データを使用したことによるものです。したがって、正規表現エンジンの仕組みを調べると、a^を使用すると、最初のaで暫定的な一致が見つかったためにさらに多くの遅延が発生し、後で拒否されます。 xはコーパスでは一般的ではないため、時間が無駄になります。テキスト内のより多くの位置を直ちに拒否できます。あなたはe^など、あなたのパターンで英語で他の一般的な手紙を、使用している場合

• 、それは同じように遅くなります（eはおそらくaよりもさらに遅くなります）。
• 実際のテキストではなくランダムなバイトを使用する場合は、x^とa^パターンの両方が同様に機能します。

したがって、2つの「同等の」一致しない正規表現パターンは同等ではありません。エンジンには2つの "読み込みヘッド"があり、どちらも左から右に移動します。文字列内を移動し、正規表現パターンで移動します。a^パターンをデータの選択と組み合わせれば、正規表現エンジンはもっと多くの作業を行う必要があります。