|Just another Perl shrine|
Re^6: matching the words (166 quadrillion times faster!!)by BrowserUk (Pope)
|on Feb 17, 2013 at 01:59 UTC||Need Help??|
Of course, if numbers of words and/or terms is very large, and performance is critical, and you are prepared to throw memory at the problem, there is another, yet faster way. (How much faster is difficult to express in terms that most of us would understand).
The basic principle is an old favorite of mine: don't search; index. In this case that means building a hash that contains every possible variation of each word in the wordlist. For 'fred', that means adding '_red', 'f_ed', 'fr_d' & 'fre_' as keys to the hash with 'fred' as the values. Then, each of the wildcarded terms can be looked up directly. The result:
Which makes the process 8 quadrillion times faster than the regex against a string; and (an unbelievable) 166 quadrillion times faster than the regex engine over an array.
If my math is right, that means it can do in 1 second; what the regex engine would take 5 billion years to do!
(And I've checked and checked, and it really does appear to be true?)
With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.