可能な限り長い正規表現は多項式時間で何ですか？

Question

質問Complexity of Regex substitutionが質問に近づいていますが、それは同じではありません。 thepriseによって返信によれば、（DFAエンジンの）複雑さがある：

O（2^M + N）[mは正規表現の長さであり、nは文字列の長さである]

15-16ページの「アルゴリズム設計マニュアル」の赤い帳では、さまざまなアルゴリズムの時間について説明しています。それによれば、アルゴリズムの長さが1,000,000を超える場合、O（m^2）のアルゴリズムは絶望的です。 1ナノ秒の動作時間を仮定すると、処理には16.7分かかります。

本の声明は私の関心を高めました。あなたは1,000,000文字の正規表現を16.7分の処理時間で実行できますか？あなたは致命的な正規表現を行い、処理時間はまだかかりますか？私は本当にそれを疑う。

多項式時間で1ナノ秒の動作時間を持つ可能な最長のRegexは何ですか？

Answer 1

これは意味のない質問です。正規表現はアルゴリズムではなく、言語です。この言語には多くの実装があり、すべて独自のパフォーマンス特性を持ち、個々の正規表現には独自のコストがあります。たとえば、代替語句/(a|b|c)/は並列化可能な問題です。したがって、並列で式を実行するエンジンでは、そうでないものよりも優れたパフォーマンスが得られます。

これは、ソートに最適なケースを尋ねるのと同じです。一部の人々はあなたにO(n log n)と言うでしょうが、間違っているでしょう。答えは、使用されるアルゴリズムに依存します。 O(n)という最悪の場合があります（radix sortなど）があります。

Answer 2

実際の複雑さはおそらく特定の正規表現に依存します。 1000000のための簡単な試合「のは、約10秒かかる：この場合には

import re 

expr = 'a' * 1000000 
re.match(expr, expr) 

複雑さをO（メートル）程度のようですが、より複雑な式は確かに長い時間がかかるでしょう。