python中的“in”运算符功能

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

但是我读到一篇关于堆栈溢出的文章，上面说：

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循环

所以我的问题是，在我的代码中的{{CD8}}循环中，我是否应该考虑嵌套^ {< CD8>}循环，因为^ {< CD6>}运算符在后台使用^ {< CD8>}循环吗？如果是，该计划的时间复杂度是多少

Answer 1

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

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

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

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

Answer 2

当in相当于一个循环时，它必须“遍历”迭代器并依次比较每个项

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

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

请注意，这里实际上有3个循环，因为replace也将遍历字符串

由于如果未找到char，replace不会引发任何错误，因此只需在不首先测试char in string1的情况下执行此操作就更简单了

Answer 3

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)