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行爲的實時性能。要麼使用更具代表性的樣本進行基準測試，要麼在您的案例中不需要更快（漸近）的算法。