与列表相比，字符串的 "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 操作可能是用 C 的 strstr 编码）；而 sub in str.split() 在开始查找单词之前仍然必须拆分整个文本（因此最好的情况总是至少 O(n)，更多的内存消耗等）。

与列表相比，字符串的 "in" 运算符的时间复杂度是否存在差异？

Is there a difference in time complexity of the "in" operator for strings compared to lists?

python

string

list

time-complexity

in-operator