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

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 2

不，没有更快的内置方法。

如果您要测试大量字符串，那么最好使用第三方 Aho-Corasick package, as 节目。

使用内置方法，最坏的情况是：没有匹配项，这意味着您已经测试了列表中的每个项目以及几乎每个项目中的每个偏移量。

幸运的是，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 3

我没有大型数据集可以尝试：

但也许这样的事情会奏效？

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() 的 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

注意：如果您对 Big-O 行为感兴趣，则没有必要测量 string = 'a' 等微小字符串的时间性能。要么为基准使用更具代表性的样本，要么在您的情况下不需要更快（渐近）的算法。

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

Python3 Fast Way To Find If Any Elements In Collections Are Substring Of String

python

algorithm

python-3.x

big-o

string-algorithm