正則表達式花費很長的時間

Question

我有以下腳本，它抓取的網頁，然後做一個正則表達式來尋找項目我在尋找：

use warnings; 
use strict; 
use LWP::Simple; 

my $content=get('http://mytempscripts.com/2011/09/temporary-post.html') or die $!; 
$content=~s/\n//g; 
$content=~s/ / /g; 
$content=~/<b>this is a temp post<\/b><br \/><br \/>(.*?)<div style='clear: both;'><\/div>/; 
my $temp=$1; 


while($temp=~/((.*?)([0-9]{1,})(.*?)\s+(.*?)([0-9]{1,})(.*?)\s+(.*?)([0-9] {1,})(.*?)\s+)/g){ 
print "found a match\n"; 
} 

這工作，但需要很長很長的時間。當我將正則表達式縮短到下面的時候，我得到的結果不到一秒鐘。爲什麼我的原始正則表達式需要這麼長時間？我如何糾正它？

while($temp=~/((.*?)([0-9]{1,})(.*?)\s+(.*?)([0-9]{1,})(.*?)\s+(.*?)([0-9] {1,})(.*?)\s+)/g){ 
print "found a match\n"; 
} 

Answer 1

正則表達式就像Perl中的sort函數。你認爲這很簡單，因爲這只是一個單一的命令，但最終，它使用大量的處理能力來完成這項工作。

有一些事情可以做，以助陣：

1. 保持你的語法簡單越好。
2. 如果您在循環中使用正則表達式，請使用qr預編譯您的正則表達式模式。這將防止Perl必須編譯您的每個循環的正則表達式。
3. 儘量避免必須執行的正則表達式語法backtracking。這通常最終成爲最一般的匹配模式（例如.*）。

可憐的事實是，經過幾十年的Perl寫作，我從來沒有掌握正規表達式解析深奧的祕密。我已經嘗試過很多次瞭解它，但這通常意味着要在Web上進行研究，並且......呃...我被Web上的所有其他內容分散注意力。

而且，這並不困難，任何一位智商爲240的開發者，以及對虐待主義的愛好都應該能夠輕鬆地把它撿起來。

---

@大衛W .:我想我是在回溯困惑。我不得不多次閱讀你的鏈接，但仍然不太明白如何實現它（或不執行它）在我的情況。 - user522962

讓我們舉一個簡單的例子：

my $string = 'foobarfubar'; 
$string =~ /foo.*bar.*(.+)/; 
my $result = $1; 

會有什麼$result是什麼？它將是r。你看這是如何工作的？讓我們看看發生了什麼。

最初，正則表達式被分解爲令牌，並使用第一個令牌foo.*。這實際上整個字符串匹配：

"foobarfubar" =~ /foo.*/ 

但是，如果第一個正則表達式令牌捕獲整個字符串，正則表達式的其餘部分失敗。因此，正則表達式匹配算法來支持曲目：

"foobarfubar" =~ /foo.*/ #/bar.*/ doesn't match 
"foobarfuba" =~ /foo.*/  #/bar.*/ doesn't match. 
"foobarfub" =~ /foo.*/  #/bar.*/ doesn't match. 
"foobarfu" =~ /foo.*/  #/bar.*/ doesn't match. 
"foobarf" =~ /foo.*/  #/bar.*/ doesn't match. 
"foobar" =~ /foo.*/   #/bar.*/ doesn't match. 
... 
"foo" =~ /foo.*/   #Now /bar.*/ can match! 

現在，同樣的情況發生在字符串的其餘部分：

"foobarfubar" =~ /foo.*bar.*/ #But the final /.+/ doesn't match 
"foobarfuba" =~ /foo.*bar.*/ #And the final /.+/ can match the "r"! 

回溯傾向於用，因爲他們的.*和.+表達發生很鬆。我發現你使用的是非貪婪的比賽可以提供幫助，但如果你不小心的話，這仍然是一個問題 - 尤其是如果你有很長和複雜的正則表達式。

我希望這有助於解釋回溯。

您遇到的問題不是您的程序無法正常工作，而是需要很長很長的時間。

我希望我的答案的一般要點是，正則表達式解析並不像Perl所說的那樣簡單。我可以在程序中看到命令sort @foo;，但忘記了如果@foo包含一百萬左右的條目，則可能需要一段時間。理論上，Perl可以使用冒泡排序，因此該算法是一個O 。我希望Perl實際上使用更高效的算法，而我的實際時間將更接近O * log（O）。但是，所有這一切都隱藏在我簡單的一行聲明中。

我不知道在你的情況下回溯是一個問題，但你把整個網頁輸出視爲一個單一的字符串來匹配一個正則表達式，這可能會導致一個很長的字符串。你試圖將它與另一個你反覆做的正則表達式匹配。顯然，這是一個非常流程密集的步驟，它隱藏在一個Perl語句中（很像sort @foo隱藏了它的複雜性）。

考慮到週末的這種情況，你真的不應該試圖用正則表達式來解析HTML或XML，因爲它太瑣碎了。你最終會遇到一些效率低下而脆弱的事情。

在這種情況下，使用類似我更熟悉的HTML::Parser或XML::Simple之類的東西可能會更好，但不一定適用於格式不正確的HTML。

Perl正則表達式很好，但它們很容易就失控。

Answer 2

有一兩件事你可以嘗試在改變所有的捕捉組（......）非捕獲組（？：...）

，將節省一些努力，因爲如果你的匹配需要打印出「找到一個匹配」，但我不確定如果你的真實代碼做得更多，你可以在現實中做到這一點。另外，一般來說，有很多像（。*？）這樣的通配符會增加我的體重，所以也許知道你想要匹配的東西將能夠消除其中的一些？我不能肯定地說，在這裏沒有看到任何純粹的正式優化。