Dada una cadena, generalmente una oración, quiero extraer todas las subcadenas de longitud 3, 4, 5, 6 . ¿Cómo puedo lograr esto de manera eficiente usando solo la biblioteca estándar de Python ? Aquí está mi enfoque, estoy buscando uno que sea más rápido. Para mí, parece que los tres bucles externos son inevitables de cualquier manera, pero tal vez haya una solución optimizada de bajo nivel con itertools o menos.
import time def naive(test_sentence, start, end): grams = [] for word in test_sentence: for size in range(start, end): for i in range(len(word)): k = word[i:i+size] if len(k)==size: grams.append(k) return grams n = 10**6 start, end = 3, 7 test_sentence = "Hi this is a wonderful test sentence".split(" ") start_time = time.time() for _ in range(n): naive(test_sentence, start, end) end_time = time.time() print(f"{end-start} seconds for naive approach") Salida de naive() :
['thi', 'his', 'this', 'won', 'ond', 'nde', 'der', 'erf', 'rfu', 'ful', 'wond', 'onde', 'nder', 'derf', 'erfu', 'rful', 'wonde', 'onder', 'nderf', 'derfu', 'erful', 'wonder', 'onderf', 'nderfu', 'derful', 'tes', 'est', 'test', 'sen', 'ent', 'nte', 'ten', 'enc', 'nce', 'sent', 'ente', 'nten', 'tenc', 'ence', 'sente', 'enten', 'ntenc', 'tence', 'senten', 'entenc', 'ntence']Segunda versión:
def naive2(test_sentence,start,end): grams = [] for word in test_sentence: if len(word) >= start: for size in range(start,end): for i in range(len(word)-size+1): grams.append(word[i:i+size]) return gramsBueno, creo que esto no es posible para mejorar el algoritmo, pero puedes microoptimizar la función:
def naive3(test_sentence,start,end): rng = range(start,end) return [word[i:i+size] for word in test_sentence if len(word) >= start for size in rng for i in range(len(word)+1-size)]Python 3.8 introduce Expresiones de asignación que son bastante útiles para el rendimiento. Por lo tanto, si puede usar una versión reciente, puede escribir:
def naive4(test_sentence,start,end): rng = range(start,end) return [word[i:i+size] for word in test_sentence if (lenWord := len(word)+1) > start for size in rng for i in range(lenWord-size)]Estos son los resultados de rendimiento:
naive2: 8.28 µs ± 55 ns per call naive3: 7.28 µs ± 124 ns per call naive4: 6.86 µs ± 48 ns per call (20% faster than naive2) Tenga en cuenta que la mitad del tiempo de naive4 se dedica a crear los objetos de cadena word[i:i+size] y el resto se dedica principalmente al intérprete de CPython (principalmente debido a la creación/recuento de referencias/eliminación de enteros de tamaño variable objetos).
Creo que esto lo hará:
test_sentence = "Hi this is a wonderful test sentence".split() lengths = [3, 4, 5, 6] result = [] for t in test_sentence: for l in lengths: if len(t) >= l: start = 0 while start + l <= len(t): result.append(t[start:start+l]) start += 1