Является ли встроенная строка python лучше, чем kmp

Question

У меня есть большая строка с пробелами, eg;

text = " i am studying in ABC college. I love science......". 

Теперь у меня есть список моделей, которые также могут содержать пробелы например

pattern_array = :["i am" ,"def frfrf", "yes"]. 

Теперь я хочу, чтобы найти все эти строки pattern_arr, которые присутствуют в тексте. В вышеописанном случае он должен вернуть ["i am"]

Я применил KMP в Python для этого, но хотел бы знать, что в построенном методе питона «подстроки» в «текст» быстрее, чем kmp или нет?

Если есть какое-то лучшее решение для этого?

Answer 1

Вы можете использовать модуль python для сравнения различных методов. Ниже я сравниваю 3 метода: x in y, re.search(x, y) и kmpAllMatches(x, y):

>>> import requests, timeit, re 
>>> text = requests.get('https://www.gutenberg.org/files/98/98-0.txt').text 
>>> needle = u"Decidedly. May one ask what it is for?" 
>>> timeit.timeit(lambda: needle in text, number=10000) 
1.666576707008062 
>>> pattern = re.compile(re.escape(needle)) 
>>> timeit.timeit(lambda: pattern.search(text), number=10000) 
1.8376031270017847 
>>> timeit.timeit(lambda: kmpAllMatches(needle, text), number=10000) 
0.005527019500732422 

Как вы можете видеть, KMP может работать лучше. Это сказано, make sure you aren't solving a problem you don't have yet. Встроенные средства Python часто достаточно хороши, и вы будете благодарны позже, если сможете избежать накладных расходов на дополнительный код. Придерживайтесь простого решения и оптимизируйте только после того, как профилировщик всей программы поддерживает ваши предположения о том, что наивный подход слишком медленный.