python - 用于字符串查找的集合与正则表达式，哪个更具可扩展性？

Question

假设我需要处理一个非常大的单词列表，并且我需要计算在一段文本中找到这些单词的次数。就可扩展性而言，哪个是最佳选择？

选项 I(正则表达式)

>>> import re
>>> s = re.compile("|".join(big_list))
>>> len(s.find_all(sentence))

选项二(套)

>>> s = set(big_list)
>>> len([word for word in sentence.split(" ") if word in s]) # O(1) avg lookup time

示例:如果列表为 ["cat","dog","knee"] 且文本为“狗跳过了猫，但狗折断了膝盖”，则最终结果应为:4

附注欢迎任何其他选择

Answer 1

如果您的单词是字母数字，我可能会使用以下内容:

s = set(big_list)
sum(1 for x in re.finditer(r'\b\w+\b',sentence) if x.group() in s)

由于集合的隶属度测试平均为 O(1)，因此该算法变为 O(N+M)，其中 N 是句子中的单词数，M 是 big_list 中的元素数。不是太寒酸。它在内存使用方面也表现得很好。