Есть ли разница во временной сложности оператора «in» для строк по сравнению со списками?

Question

Мне было интересно, есть ли какая-либо польза от поиска строки в списке по сравнению с поиском подстроки в строке с помощью оператора "in".

Я всегда проверял наличие подстроки с помощьюследующее:

substr in str

Но я наткнулся на фрагмент кода, который разбил строку, а затем выполнил проверку.

substr in str.split()

Есть ли какое-либо преимущество в производительности или иноеэто просто предпочтение для этого программиста.

Спасибо!

Answer 1

Они делают две разные вещи. Сложность обоих - O (n), но это не очень важно, потому что вы не выберете одно из другого, потому что они быстрые;Вы бы сделали выбор, основываясь на том, что вы действительно хотите сделать .

>>> "o b" in "foo bar"  # "o b" is a substring of "foo bar"
True
>>> "o b" in "foo bar".split()  # "o b" is not an element of ["foo", "bar"]
False

Answer 2

Как уже упоминалось, оно может немного отличаться:

>>> "Python" in "Monty Python's Flying Circus"
True
>>> "Python" in "Monty Python's Flying Circus".split()
False

И с точки зрения производительности разделение намного дороже (оно создает временный список):

>>> from timeit import timeit
>>> timeit("""'Monty' in "Monty Python's Flying Circus".split() """)
0.20677191999857314
>>> timeit("""'Monty' in "Monty Python's Flying Circus" """)
0.03346360499563161

Мы также можем, вероятно, утверждать, что если искомое слово находится в начале предложения, sub in str будет лучшим сценарием в O (1) (операция in, вероятно, кодируется с помощью strstr в C). );в то время как sub in str.split() все равно придется разбить весь текст, прежде чем начинать искать слово (поэтому в лучшем случае всегда требуется не менее O (n), больше памяти и т. д.).