这是对球门柱移动的回应(“我可能需要正则表达式,因为在不久的将来我需要单词分隔符”):
此方法解析文本一次以获得所有“单词”的列表。在目标词的字典中查找每个词,如果是目标词,则对其进行计数。花费的时间是 O(P) + O(T),其中 P 是段落的大小,T 是目标词的数量。迄今为止,除了我的 Aho-Corasick 解决方案之外的所有其他解决方案(包括当前接受的解决方案)都是 O(PT)。
def counts_all(targets, paragraph, word_regex=r"\w+"):
tally = dict((target, 0) for target in targets)
for word in re.findall(word_regex, paragraph):
if word in tally:
tally[word] += 1
return [tally[target] for target in targets]
def counts_iter(targets, paragraph, word_regex=r"\w+"):
tally = dict((target, 0) for target in targets)
for matchobj in re.finditer(word_regex, paragraph):
word = matchobj.group()
if word in tally:
tally[word] += 1
return [tally[target] for target in targets]
finditer 版本是一个稻草人——它比 findall 版本慢得多。
这是目前接受的解决方案,以标准化形式表示并增加了单词分隔符:
def currently_accepted_solution_augmented(targets, paragraph):
def tester(s):
def f(x):
return len(re.findall(r"\b" + x + r"\b", s))
return f
return map(tester(paragraph), targets)
这在关闭时太过分了,可以减少为:
# acknowledgement:
# this is structurally the same as one of hughdbrown's benchmark functions
def currently_accepted_solution_augmented_without_extra_closure(targets, paragraph):
def tester(x):
return len(re.findall(r"\b" + x + r"\b", paragraph))
return map(tester, targets)
当前接受的解决方案的所有变体都是 O(PT)。与当前接受的解决方案不同,带有单词分隔符的正则表达式搜索不等同于简单的paragraph.find(target)
. 因为在这种情况下重新引擎不使用“快速搜索”,所以添加单词分隔符会将其从缓慢变为非常缓慢。