Как оптимизировать код на Python (поиск в строке)?

Question

[Станислав Фатеев]

Есть такой код - ищет последовательность символов в строке, и возвращает True, если последовательность найдена:

if word in s:
    return True
else:
    return False

Очень просто и наглядно. Проблема в том, что этот участок вызывается программой несколько миллионов раз, и скорость его работы критична. Как можно это ускорить?

UPDATE:
Количество различных s не определено, количество различных word около 1000

Answer 1

[Andrey K]

Реализуйте более быстрый алгоритм. Можно на си, если хотите еще быстрее.
https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D...

Comments

[Станислав Фатеев]

У меня глаза разбежались, может посоветуете что-то?

[Andrey K]

Алгоритм Бойера-Мура.

[Andrey Dugin]

Andrey: Алгоритм Бойера-Мура и так уже заложен в Python.

Answer 2

[mayorovp]

Проверка word in s сама по себе довольно оптимальная. Если вам надо оптимизировать алгоритм для поиска многих подстрок одновременно - то взгляните на алгоритм Ахо-Корасик

Answer 3

[Ivan Velichko]

Если количество уникальных word не слишком велико, то можно сделать "index" по ним. Тогда последующий поиск такой же подстроки будет происходить за O(1), а не за O(n) как это происходит с оператором in. Минус - оверхед по памяти на индекс.

def in_checker(word, s):
    if not hasattr(in_checker, '_index'):
        in_checker._index = {}
    if word not in in_checker._index:
        in_checker._index[word] = word in s
    return in_checker._index[word]

in_checker('abc', 'tttrrrabcwww');  # O(n)
in_checker('abc', 'tttrrrabcwww');  # O(1)

Comments

[Станислав Фатеев]

Что-то я не могу понять, как это будет работать для неопределенного количества различных s

[Ivan Velichko]

Станислав Фатеев: Упс, я исходил из предположения, что s одна и та же. Тогда можно индекс сделать двойной вложенности, сначала по s, затем по word или наоборот. В зависимости от частотности. Плюс можно делать md5(s) в качестве ключа индекса, чтобы не хранить строку целиком.

[Станислав Фатеев]

Иван Величко: уточнил условие

[Ivan Velichko]

Pavel Denisov: Временная сложность поиска и добавления элемента в set и dict одинаковая. По поводу тестов - согласен. Правда в свете обновленных условий вопроса - количество различных s не определено, я бы стал смотреть уже вот в этом направлении https://toster.ru/answer?answer_id=528145.

Answer 4

[xSkyFoXx]

Ещё можно попробовать:

[lambda x: x is word for x in s]

Но не уверен, что это будет быстрее, чем то, что предложил Pavel Denisov

Answer 5

[Алексей Guest007]

(True if word in s else False)

Comments

[Алексей Guest007]

Pavel Denisov: согласен для случая True|False. Просто мой вариант - более общий