Python3快速的方法来查找如果集合中的任何元素是字符串的子串

Question

如果我有一个collection of strings是否有一个数据结构或函数可以提高检查集合中的任何元素是否为主串中的substrings ？

现在我正在循环访问我的字符串数组并使用in运算符。有更快的方法吗？

import timing 

## string match in first do_not_scan 
## 0:00:00.029332 

## string not in do_not_scan 
## 0:00:00.035179 
def check_if_substring(): 
    for x in do_not_scan: 
     if x in string: 
      return True 
    return False 

## string match in first do_not_scan 
## 0:00:00.046530 

## string not in do_not_scan 
## 0:00:00.067439 
def index_of(): 
    for x in do_not_scan: 
     try: 
      string.index(x) 
      return True 
     except: 
      return False 

## string match in first do_not_scan 
## 0:00:00.047654 

## string not in do_not_scan 
## 0:00:00.070596 
def find_def(): 
    for x in do_not_scan: 
     if string.find(x) != -1: 
      return True 
    return False 

string = '/usr/documents/apps/components/login' 
do_not_scan = ['node_modules','bower_components'] 

for x in range(100000): 
    find_def() 
    index_of() 
    check_if_substring() 

Answer 1

没有，有没有更快的内置的方式提及。

如果您有大量字符串需要测试，那么使用第三方Aho-Corasick包可能会更好，如J.F. Sebastian's answer所示。

---

使用内置的方法，在最糟糕的情况是：没有匹配，这意味着你已经在列表中测试每一个项目和每一个项目几乎每一个偏移量。

幸运的是，in运营商（至少在CPython的）非常快，是在我的测试中三个近一个因素更快：

0.3364804992452264 # substring() 
0.867534976452589 # any_substring() 
0.8401796016842127 # find_def() 
0.9342398950830102 # index_of() 
2.7920695478096604 # re implementation 

---

这里是我用于测试的脚本：

from timeit import timeit 
import re 

def substring(): 
    for x in do_not_scan: 
     if x in string: 
      return True 
    return False 

def any_substring(): 
    return any(x in string for x in do_not_scan) 

def find_def(): 
    for x in do_not_scan: 
     if string.find(x) != -1: 
      return True 
    return False 

def index_of(): 
    for x in do_not_scan: 
     try: 
      string.index(x) 
      return True 
     except: 
      return False 

def re_match(): 
    for x in do_not_scan: 
     if re.search(string, x): 
      return True 
    return False 

string = 'a' 
do_not_scan = ['node_modules','bower_components'] 

print(timeit('substring()', setup='from __main__ import substring')) 
print(timeit('any_substring()', setup='from __main__ import any_substring')) 
print(timeit('find_def()', setup='from __main__ import find_def')) 
print(timeit('index_of()', setup='from __main__ import index_of')) 
print(timeit('re_match()', setup='from __main__ import re_match')) 

Answer 2

def check(): 
    if any(w in string for w in do_not_scan): 
     return True 
    else: 
     return False 

或者简单：

def check(): 
    return any(w in string for w in do_not_scan) 

由@两位方士

Answer 3

我没有一个大的数据集来尝试：

但maybes像这样的东西会起作用吗？

python3

from builtins import any 
import timeit 

do_not_scan = ['node_modules', 'bower_components'] 
string = 'a' 


def check_if_substring(): 
    return any(string in x for x in do_not_scan) 


result = timeit.Timer("check_if_substring()", "from __main__ import check_if_substring") 
count = 10000 
print(result.timeit(count)/count) 

或者周围的其他方式：

def check_if_substring(): 
    return any(x in string for x in do_not_scan) 

我的结果：6.48119201650843e-07

Answer 4

是的，有执行found = any(s in main_string for s in collection_of_strings)例如更快的方法，有Aho-Corasick_algorithm允许改进any()-based O(n*m*k)算法到O(n + m*k)时间操作，其中n是len(main_string),m是len(collections_of_strings)和k代表集合中字符串的各个长度。

#!/usr/bin/env python 
import noaho # $ pip install noaho 

trie = noaho.NoAho() 
for s in collection_of_strings: 
    trie.add(s) 
found = trie.find_short(main_string)[0] is not None 

注：没有点来测量微小的字符串，例如string = 'a'如果你有兴趣在大O行为的实时性能。要么使用更具代表性的样本进行基准测试，要么在您的案例中不需要更快（渐近）的算法。