Python3 就运行时而言，输入顺序对 .intersection() 函数重要吗？

Question

假设您有两个集合，set1 非常大(几百万个值)，而 set2 相对较小(几十万个值)。如果我想使用 .interstion() 函数获得这两个集合之间的值的交集，是否会根据输入的顺序进行运行时改进？
例如，其中一个会比另一个运行得更快吗？

set1.intersection(set2)
set2.intersection(set1)

Answer 1

不，输入顺序无关紧要。在 CPython(标准 Python 实现)中，set_intersection函数处理集合交集。在另一个参数也是一个集合的情况下，函数将交换两个集合，以便迭代较小的集合，而较大的集合用于(恒定时间)查找，如 Booboo described :

        if (PySet_GET_SIZE(other) > PySet_GET_SIZE(so)) {
            tmp = (PyObject *)so;
            so = (PySetObject *)other;
            other = tmp;
        }

        while (set_next((PySetObject *)other, &pos, &entry)) {
            key = entry->key;
            hash = entry->hash;
            rv = set_contains_entry(so, key, hash);
            if (rv < 0) {
                Py_DECREF(result);
                return NULL;
            }
            if (rv) {
                if (set_add_entry(result, key, hash)) {
                    Py_DECREF(result);
                    return NULL;
                }
            }
        }

因此，其中set1和 set2是套，set1.intersect(set2)和 set2.intersect(set1)将具有相同的性能。使用 timeit 进行的小型实证测试同意:

import random
import string
import timeit

big_set = set()
while len(big_set) < 1000000:
    big_set.add(''.join(random.choices(string.ascii_letters, k=6)))


small_set = set()
while len(small_set) < 10000:
    small_set.add(''.join(random.choices(string.ascii_letters, k=6)))

print("Timing...")
print(f"big_set.intersection(small_set): {min(timeit.Timer(lambda: big_set.intersection(small_set)).repeat(31, 500))}")
print(f"small_set.intersection(big_set): {min(timeit.Timer(lambda: small_set.intersection(big_set)).repeat(31, 500))}")