如何加快与字符串列表的字符串匹配?
我有一个字符串列表。我正在尝试查找列表中是否有任何这些字符串出现在存储为另一个列表的英语字典中。如何加快与字符串列表的字符串匹配?
我观察它需要找到一个匹配线性增长的时间。然而,当原始列表有几千个字符串时,它变得太长了。
在我发展的EC2实例,它需要约2秒100串,〜15秒700串,〜100秒5000串,并〜800秒40000串!
有没有办法加快速度?提前致谢。
matching_word = ""
for w in all_strings:
if w in english_dict:
if matching_word: # More than one possible word
matching_word = matching_word + ", " + w
else:
matching_word = w
而不是创建一个字符串,并扩展它,你可以使用列表理解为是的:
matching_words = [x for x in all_strings if x in english_dict]
现在,您可以使用", ".join(matching_sords)
该列表中的字符串。
另一种选择 - 使用两套可以使用&
操作:
set(all_strings) & set(english_dict)
结果,这里将是一组与您在两份名单有项目。
只要不发生问题的内存,把你的english_dict
到set
(如果你确实有内存问题,加载你的字典作为set
开始与):english_dict = set(english_dict)
(之前的循环,当然)
这应该显著加快查找。如果这还不够,你将不得不求助于创建搜索树和类似的搜索优化。
Zwer。谢谢你的帮助。我可以通过解决方案解决性能问题。现在它是邪恶的快!其实,我的英文字典非常小(仅约15K条目),而最大(全字母)为3628800。现在,它只需要不到一秒的时间。 – RebornCodeLover
如果'all_strings'是大的,你不需要保存的顺序,那么一定把所有的'all_strings'和'english_dict'成组(甚至更好 - 加载它们作为一组),并使用'all_strings.intersection(而不是。 – zwer
是的,那就是我最终做的。对于集合(all_strings)&set(english_dict)中的w是非常快的。 – RebornCodeLover
刚上最后一个音符 - 交集会破坏找到的单词的顺序,因此,如果顺序很重要,应该使用的第一个例子(列表理解) - 打开字典为一组,当然后。 – zwer
谢谢Dekel的解决方案。不幸的是,列表理解需要花费相同的时间。但猜猜看,你提供的解决方案超快。 – RebornCodeLover