'in' python 中的运算符功能

Question

我需要删除 string1 中存在于 string2 中的字符。这里 string1 和 string2 只有小写字符 a-z，条件是 string1 的长度每次都会变大。

我使用的是 in 运算符：

def removeChars (string1, string2):
    for char in string2:
        if char in string1:
            string1 = string1.replace(char, '')
    return string1

但我在 Stack Overflow 上读到一篇，上面写着：

For container types such as list, tuple, set, frozenset, dict, or collections.deque, the expression x in y is equivalent to any(x is e or x == e for e in y).

这意味着 in 运算符正在幕后使用 for 循环。

所以我的问题是，在我代码的 for 循环中，我是否应该考虑使用嵌套的 for 循环，因为 in 运算符使用 for 在后台循环？如果是，这个程序的时间复杂度是多少？

Answer 1

当in相当于一个循环时，它要'walk'迭代器，依次比较每一项。

这意味着每个循环是 O(n)，所以对于 2 个级别，这是 O(n²)

https://wiki.python.org/moin/TimeComplexity

请注意，您实际上在这里有 3 个循环 - 因为您的 replace 也会遍历字符串。

由于如果 char 未找到，替换不会引发任何错误，因此无需先测试 char in string1.

即可执行此操作更简单

Answer 2

in 不一定在幕后使用循环。例如：

r = range(100000000000)
print(333 in r)  # prints True immediately without looping

如果要循环 r 将花费很长时间，很明显这不会发生。

in 基本上调用（在幕后）对象的 __contains__ 方法。对于某些迭代器，它实际上会“循环”遍历所有内容，但情况并非总是如此。

这个例子和调用基本一样：

r.__contains__(333)

正如评论中指出的那样 - str 对象特别具有比普通循环更智能的算法，如您所见 here

另请参阅示例答案 here

并查看文档 here

因为现实世界的场景可能意味着 string1 可以是任意长的，但是要删除的字符将是一个有限的小集合，所以将所有字符相加可能会更有效率不在 string2 中的字符。像这样：

def removeChars (string1, string2):
    result = ''
    for char in string1:
        if char not in string2:
            result += char
    return result

这将涉及循环 string1 一次，但使用 in 对 string2 进行多次检查。这可以进一步简化（以避免 += 循环结果）：

def removeChars (string1, string2):
    return ''.join(char for char in string1 if char not in string2)

Answer 3

您确实有一个嵌套的 for 循环，但是，它不需要完全执行（平均而言），直到达到匹配为止。

所以最好的情况是 O(n)——如果每个列表的所有元素都匹配，那么对于列表 1 的每个元素，它需要内部循环的一个步骤来确定它匹配。

最坏的情况是 O(n^2) -- 如果只有列表 2 的最后一个元素匹配，则外循环的每次迭代都需要测试内循环 n 次。

至少，我是这么理解的，但不是专家。

'in' python 中的运算符功能

'in' operator functionality in python

python

time-complexity