python中in和for操作的效率

Question

我这里有两张单子，A和B

len(A) > len(B)

有两种方法：

方法一：

def f():
    return [someFunc(i) for i in A if i in B]

方法二：

def f():
    return [someFunc(i) for i in B if i in A]

哪一个更有效？为什么？你知道吗

Answer 1

虽然in操作的时间复杂度是O(n)，因此整个操作是O(nm)，但这主要适用于它如何随问题大小而扩展。性能方面，除了最坏情况下A和B互斥之外，执行for B if i in A（其中len(A) > len(B)）应该更快，因为一旦找到匹配项in就会停止迭代。你知道吗

考虑一下最佳情况，A和B中的所有条目都具有相同的值。in操作实际上是O(1)和整个操作O(m)。你知道吗

每个人都喜欢的一些基准：

$ python -m timeit "A=list(range(100000));B=list(range(100))" "[i for i in A if i in B]"
10 loops, best of 3: 113 msec per loop

$ python -m timeit "A=list(range(100000));B=list(range(100))" "[i for i in B if i in A]"
100 loops, best of 3: 2.6 msec per loop

撇开性能不谈，请注意，您提供的两个函数的作用不同。第一个循环遍历A并丢弃未出现在B中的值，这与循环遍历B并丢弃未出现在A中的值不同。回到两个列表中的所有值都相同的场景，第一个函数将返回len(A)元素，而第二个len(B)元素。你知道吗

Answer 2

def f(A, B):
    return [someFunc(_) for _ in set(A).intersection(B)]

这应该是最有效的方法（至少如果列表足够长，时间复杂度就成了问题）

Answer 3

两者都是O（mn），因为您正在为另一个列表的每个元素遍历每个列表。你知道吗