[Date Prev][Date Next][Thread Prev][Thread Next]
- Subject: Re: Pattern matching: good practices ?
- From: Vaughan McAlley <ockegheim@...>
- Date: Mon, 28 Dec 2009 00:03:44 +1100
2009/12/27 David Manura <firstname.lastname@example.org>:
> On Sat, Dec 26, 2009 at 12:29 PM, David Manura wrote:
> ('a'):rep(5000):match'a*b' -- fails slowly (about a second)
> BTW, s:match'a*b' is equivalent to s:match'^.-(a*b)'.
I think I'm getting a feel for the kind of ambiguity (or looseness)
that causes a lot of backtracking. As a human pattern-matcher, I would
notice that there is no 'b' in the pattern, so wouldn't bother
beginning again at the second character. But a computer is not human!
Reversing the string can speed things up (excuse my less compressed notation):
(('a'):rep(5000)..'caaaab'):match'a*b' -- finds 'aaaab' slowly
local s = ('a'):rep(5000)..'caaaab'
local s1 = string.reverse(s)
print(string.reverse(string.match(s1, "ba*")) -- finds 'aaaab' quickly