优化在同一字符串上多次调用"in"的运行时

Question

在查找子字符串时，in运算符在单个调用的性能方面是最好的。看起来它也是 O（n） 平均运行时间。

如果我想查找字符串中是否存在多个子字符串，如下所示：

if 'dog' in str:
    # ....
if 'cat' in str:
    # ....
if 'frog' in str:
    # ....

这将是 3n 运行时，这是大量的重复工作。有没有办法优化in或其他可用的库，这将是更快的选择？

Answer 1

#EDIT

====

====================================================================

a_list  = re.sub("[^a-zA-Z ]","",s).split()#4957 words (lorum ipsum generated)
search_space = set("dog cat fish bear walrus".split())
def joranbeasley():
    return search_space.intersection(a_list)
def stephenPochmann():
    for needle in search_space:
        if needle in s: print needle

import timeit
print "Stephen Timeit:",timeit.timeit(stephenPochmann,number=1000)
print "joran Timeit:",timeit.timeit(joranbeasley,number=1000)

结果

Stephen Timeit: 0.126952238343
joran Timeit: 0.148540107751

====

====================================================================

set(["dog","cat","frog"]).intersection(my_str.split())

可能会给你你需要的东西，它很难说，应该足够快......

如果您的字符串使用空格以外的分隔符，您可能需要传递一个参数以与您的分隔符（";"或其他东西）进行拆分

您可能还必须清理输入以删除标点符号等内容

my_cleaned_string = re.sub("[^a-zA-Z]","",my_str)

与@StephenPochmans相比，如果我稍微改变一下（即我不需要每次都继续拆分）

import re
a_list  = re.sub("[^a-zA-Z ]","",s).split()#4957 words (lorum ipsum generated)
search_space = set("dog cat fish bear walrus".split())
def stephenPochmann():
    for needle in search_space:
        if needle in a_list: print needle
def joranbeasley():
    return search_space.intersection(a_list)
import timeit
print "Stephen Timeit:",timeit.timeit(stephenPochmann,number=1000)
print "joran Timeit:",timeit.timeit(joranbeasley,number=1000)

和结果

c:py_exp>python test_benchmark.py
Stephen Timeit: 0.356363602542
joran Timeit: 0.166205366392

将@StephenPochmans更改为使用字符串而不是列表后，他是对的，而且确实更快......我将很快在回答的顶部澄清这一点

def stephenPochmann():
    for needle in search_space:
        if needle in s: print needle

这是结果

Stephen Timeit: 0.126952238343
joran Timeit: 0.148540107751

Answer 2

如果你有很多单词，你应该考虑转向算法构建，以便在文本中搜索多个单词。

最流行的是Aho-Corasick 算法（https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_algorithm），你可以在Python中找到许多实现。这只是解释实现算法的众多教程之一：http://carshen.github.io/data-structures/algorithms/2014/04/07/aho-corasick-implementation-in-python.html