检查字符串列表中的所有元素是否都在字符串中的最快方法

Question

我有一个字符串

"我的名字是安德鲁,我非常棒".

让我们说我有一个列表,如

[['andrew','name','awesome'],['andrew','names','awesome']]

我需要我的解决方案才能回归

['andrew','name','awesome']

天真的解决方案是:

myString='My name is Andrew, I am pretty awesome'
keywords = [['andrew', 'name', 'awesome'], ['andrew', 'designation', 'awesome']]
results=[]
for i in keywords:
 if all(substring in myString.lower() for substring in i):
    results.append(i)
print results

我的问题是,当列表关键字非常大(比如100000)时,存在性能瓶颈.我需要知道最有效的方法.

Answer 1

感谢BlackBear 指出由于循环不变量的重新计算,我的时间偏差.在将它们移出时,事情会发生巨大变化.

有两种方法可以做到这一点.理智的方式,以及正则表达方式.首先,设置.

string = "My name is Andrew, I am pretty awesome"
choices = [['andrew', 'name', 'awesome'], ['andrew', 'designation', 'awesome']]

选项1
这个in在列表推导中执行子串检查.该in检查在C语言中修改了Boyer-Moore算法的实现,并且非常快.

>>> [c for c in choices if all(y in string.lower() for y in c)]
[['andrew', 'name', 'awesome']]

现在,为了时间.但首先,一个小的表现挑剔; 你可以缓存循环string.lower() 外的值,它是一个不变量,不需要每次都重新计算 -

v = string.lower()
%timeit [c for c in choices if all(y in v for y in c)]
1000000 loops, best of 3: 2.05 µs per loop

选项2
这个使用re.split+ set.issuperset;

>>> import re
>>> [c for c in choices if set(re.split('\W', string.lower())).issuperset(c)] 
[['andrew', 'name', 'awesome']]

re.split如果你想执行集合检查,由于句子中的标点符号,使用无法避免.

同样,set计算是一个循环不变量,可以移出.这是它的作用 -

v = set(re.split('\W', string.lower()))
%timeit [c for c in choices if v.issuperset(c)] 
1000000 loops, best of 3: 1.13 µs per loop

这是一个例外情况,我发现正则表达式的执行速度略快.但是,这些时间并不是决定性因素,因为数据的大小和结构差别很大.我建议在得出任何结论之前用你自己的数据来解决问题,尽管我的直觉是正则表达式解决方案的扩展性很差.