在Python中（一般情况下）哪个更有效：迭代短列表并在较长列表中搜索，反之亦然？

Question

我有两个列表，都包含表示为字符串的整数。

large_list

很大，多达数十个数千个元素。

small_list

较小，最多可达数百个元素。我正在用较小的过滤掉较大的。我很想知道哪个更有效率：

（一）

for element in small_list:
    if element in large_list:
        (do something)

（二）

for element in large_list:
    if element in small_list:
        (do something)

对于选项 (a)，迭代次数受到

small_list

长度的限制，但对于每一个，都必须在完整的

large_list

上执行搜索。 对于选项 (b)，迭代会遍历整个

large_list

，但每次搜索都会在

small_list

上执行。

我知道集合是散列的，所以这里最好的选择应该是采用

large_set = set(large_list)

，迭代

small_list

，并在

large_set

上进行每次搜索。但如果我们从方程中去掉集合，是选项 (a) 更有效，还是选项 (b) 更有效？

Answer 1

(a) 会更高效，因为它只会检查直到找到匹配项，这意味着它的 O(n)，其中 n = large_list 的长度。

(b) 慢得多，因为它取决于两个列表的长度。