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, как показывает ответ JF Sebastian.

---

При использовании встроенных методов наихудший сценарий таков: совпадение отсутствует, что означает, что вы проверили каждый элемент в списке и почти каждое смещение в каждом элементе.

К счастью, 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)

как уже упоминалось @Two-Bit Alchemist

Answer 3

Да, есть более быстрый способ выполнить 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

Примечание: нет смысла измерять производительность по времени на крошечных строках, таких как string = 'a' если вы заинтересованы в поведении Big-O. Либо используйте более репрезентативную выборку для эталонного теста, либо вам не нужен более быстрый (асимптотически) алгоритм в вашем случае.

Answer 4

У меня нет большого набора данных, чтобы попробовать:

Но может что-нибудь подобное сработает?

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