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

Question

我有一个字符串

"My name is Andrew, I am pretty awesome".

假设我有一个列表列表，例如

[['andrew', 'name', 'awesome'], ['andrew', 'designation', '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

Thanks to BlackBear for pointing out that my timings were skewed because of the re-computation of loop invariants. On moving them out, things change, drastically.

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

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

选项 1
这一个在列表理解中执行 in 子字符串检查。 in 检查在 Boyer-Moore algorithm 的修改实现上运行在 C 中，并且非常快。

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

现在，时间安排。但首先，一个小的性能吹毛求疵；你可以缓存 string.lower() outside 循环的值，它是一个不变的，不需要每次都重新计算 -

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

这是一个异常(exception)情况，我发现正则表达式的执行速度稍快一些。然而，这些时间并不是决定性的，因为它们因数据的大小和结构而大不相同。我建议在得出任何结论之前先用您自己的数据尝试一下，尽管我的直觉是正则表达式解决方案的扩展性很差。