Re^5: Regex infinite loop?

Having seen the pattern, and the description you give of the problem, I suspect that when the program appears to hang, it's actually really really busy trying to match the pattern. It probably won't match, but if it does (after a long time), it's likely to not match what you intended.

You're match is sprinkled with .* and .+. That's usually fine if you know it's going to match. But if it doesn't (and the optimizer hasn't determined this already - but clearly in your case, it hasn't) perl will try every possible length. I count 11 uses of .* and .+, which means your match is running in O(n¹¹) time, where n is the length of the HTML document.

That will take a while. You'd be much better off in making your .* and .+ much more restrictive. For instance,

    id="market-watch-(.+?)"
[download]

can probably be written as

    id="market-watch-([^"]++)"   # Lose one + if you don't use 5.10
[download]

Comment on Re^5: Regex infinite loop? Select or Download Code

Replies are listed 'Best First'.
Re^6: Regex infinite loop? by Ninth Prince (Acolyte) on Oct 17, 2008 at 14:35 UTC
You are correct. The code is not, in fact, hanging -- it's just taking a very long time to execute. I "discovered" this when I unknowingly left the program running over night and came back the next morning--it had executed all the way through. The thing that confuses me, though, is that for most pages, it does all of the matching in a matter of a few seconds. For the colts and the jets however, it takes something like 2 HOURS. Intuitively, it seems like there must be something that is different about their pages, but I'm not sure what it is.	[reply]
Re^7: Regex infinite loop? by JavaFan (Canon) on Oct 17, 2008 at 14:49 UTC
Of course there's something different - their content. And that makes all the difference. (After all, if there wasn't a difference, you wouldn't do this exercise with different pages, would you?)	[reply]
Re^6: Regex infinite loop? by Ninth Prince (Acolyte) on Oct 17, 2008 at 15:46 UTC
I'm hoping you can help me understand a couple of things. First, I thought that if I used the "?" I got non-greedy searching. Shouldn't that be helping things out? Also, I'm trying to understand the code that you have suggested. Within the capturing parentheses you have `[^"]++`. What does this mean exactly? I read it as match anything that's not a double quote. I'm sure that I am wrong. Also, I don't know what the ++ does. I have only ever used one + to indicate "match at least once". What does the double plus, ++, mean? How would I say (in English) what is going on with `[^"]++`?	[reply] [d/l] [select]
Re^7: Regex infinite loop? by JavaFan (Canon) on Oct 17, 2008 at 15:58 UTC
First, I thought that if I used the "?" I got non-greedy searching. Shouldn't that be helping things out? You are right about the first part. The secondary ? quantifier makes the match non-greedy. But greedy/non-greedy only makes a (possible) difference if there is a match. It will not change the fact whether something will or will not match. And while there might be a difference in performance when there is a match (it could go either way, but Friedl suggests that using ? is slower in most cases), there will usually not be much of a performance difference if there's no match. Perl will try all possible lengths before giving up, and it hardly matters when starting from longest match working towards shortest or starting with shortest working up to longest. Within the capturing parentheses you have `[^"]++`. What does this mean exactly? It means, match as many characters that aren't double quotes, and once you've found that many, do not try with less characters if the regexp engine backtracks to this point. The not "giving back" characters is the meaning of the second +, and was introduced in 5.10. The reason I used it here is that in: `something[^"]++"` [download] once the regexp engine has matched 'something', a string of non-double quotes and then a double quote, and the rest of the pattern fails, and hence, the engine backtracks to the matching of the string of non-double quote characters, it's pointless to try it with one character less in the string of non-double quote characters: after all, the next character has to be a double quote.	[reply] [d/l] [select]
Re^8: Regex infinite loop? by Ninth Prince (Acolyte) on Oct 17, 2008 at 16:09 UTC
Thank you. This helps my understanding tremendously.	[reply]
Re^8: Regex infinite loop? by Ninth Prince (Acolyte) on Oct 17, 2008 at 17:03 UTC
Wow, I made the change that you suggested and it is super fast. The jets and colts now complete in about 1-2 seconds rather than 1-2 hours. COOL! Thank you!	[reply]
Re^6: Regex infinite loop? by Ninth Prince (Acolyte) on Oct 17, 2008 at 16:03 UTC
Okay, I think I get at least a part of what `[^"]++` is doing. It is saying "match until you get to the next double quote." Is that correct?	[reply] [d/l]
Re^7: Regex infinite loop? by Anonymous Monk on Oct 18, 2008 at 00:02 UTC
You have an extra +. YAPE::Regex::Explain #!/usr/bin/perl -- use strict; use warnings; use YAPE::Regex::Explain; print YAPE::Regex::Explain->new(qr~[^"]+~)->explain; __END__ The regular expression: (?-imsx:[^"]+) matches as follows: NODE EXPLANATION ---------------------------------------------------------------------- (?-imsx: group, but do not capture (case-sensitive) (with ^ and $ matching normally) (with . not matching \n) (matching whitespace and # normally): ---------------------------------------------------------------------- [^"]+ any character except: '"' (1 or more times (matching the most amount possible)) ---------------------------------------------------------------------- ) end of grouping ---------------------------------------------------------------------- [download]	[reply] [d/l]