Python3 rapide pour trouver si des éléments dans les collections sont sous-chaîne de chaîne

Question

Si j'ai un collection of strings est-il une structure de données ou une fonction qui pourrait améliorer la vitesse de vérification si l'un des éléments des collections sont substrings sur ma chaîne principale ?

En ce moment je suis en boucle à travers mon tableau de chaînes et en utilisant l'opérateur in. Y at-il un moyen plus rapide?

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

Non, il n'y a pas moyen intégré plus rapide.

Si vous avez de grandes quantités de chaînes à tester, il est préférable d'utiliser un package tiers Aho-Corasick, comme le montre J.F. Sebastian's answer.

---

À l'aide des méthodes intégrées, le pire scénario est le suivant: il n'y a pas de correspondance, ce qui signifie que vous avez testé tous les éléments de la liste et presque tous les décalage dans chaque article.

Heureusement, l'opérateur in est très rapide (au moins en CPython) et a été plus rapide de près d'un facteur de trois dans mes tests:

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

---

Voici le script que j'utilisé pour le test:

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 

Ou plus simple:

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

comme mentionné par @ Two-Bit Alchemist

Answer 3

Je n'ai pas un grand ensemble de données pour essayer:

Mais maybes quelque chose comme ça va fonctionner?

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) 

Ou l'inverse:

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

Mes résultats: 6.48119201650843e-07

Answer 4

Oui, il y a un moyen plus rapide pour effectuer found = any(s in main_string for s in collection_of_strings) par exemple, il y a Aho-Corasick_algorithm cela permet d'améliorer any()-based O(n*m*k) algorithme à O(n + m*k) dans l'opération de temps où n est len(main_string), m est len(collections_of_strings), et k représente les longueurs individuelles des chaînes dans la collection.

#!/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 

Note: il n'y a pas de point pour mesurer la performance du temps sur les chaînes minuscules tels que string = 'a' si vous êtes intéressé par le comportement Big-O. Utilisez un échantillon plus représentatif pour le benchmark ou vous n'avez pas besoin d'un algorithme plus rapide (asymptotiquement) dans votre cas.