Re^2: efficient method of matching a string against a list of substrings?

as noted in Regexp:Assemble:

You should realise that large numbers of alternations are processed in perl's regular expression engine in O(n) time, not O(1). If you are still having performance problems, you should look at using a trie.

regexes are often more convenient, rather than efficient. but thanks for pointing me there, because the note also mentions:

... Perl's own regular expression engine will implement trie optimisations in perl 5.10 (they are already available in perl 5.9.3 if you want to try them out).

this would probably solve the problem in the future, but i need to find something for the present.

Comment on Re^2: efficient method of matching a string against a list of substrings?

Replies are listed 'Best First'.
Re^3: efficient method of matching a string against a list of substrings? by demerphq (Chancellor) on May 05, 2005 at 13:19 UTC
For the present you can/should use R::A or one of the other regex modules as they should be patched in time of 5.10 to utilize the TRIE optimisation if possible. OTOH You havent really spelled out if you mean an anchored match or not. Ie is it /^(list\|of\|strings)$/ or is it /^(list\|of\|strings)/ or is it /(list\|of\|strings)/? Depending on which there may be non regex based strategies that are quite competitive. --- $world=~s/war/peace/g	[reply]

Replies are listed 'Best First'.

Re^3: efficient method of matching a string against a list of substrings?
by demerphq (Chancellor) on May 05, 2005 at 13:19 UTC

For the present you can/should use R::A or one of the other regex modules as they should be patched in time of 5.10 to utilize the TRIE optimisation if possible. OTOH You havent really spelled out if you mean an anchored match or not. Ie is it /^(list|of|strings)$/ or is it /^(list|of|strings)/ or is it /(list|of|strings)/? Depending on which there may be non regex based strategies that are quite competitive.

---
$world=~s/war/peace/g

[reply]