Python3 Имеет ли значение порядок ввода для функции .intersection () с точки зрения времени выполнения?

Question

Допустим, у вас есть два набора: set1 очень большой (пара миллионов значений), а set2 относительно мал (пара сотен тысяч значений). Если бы я хотел получить пересечение значений между этими двумя наборами с помощью функции .interstion (), было бы улучшение времени выполнения в зависимости от порядка входных данных?

Например, будет ли один из них работать быстрее, чем другой?

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

Answer 1

Нет, порядок ввода значения не имеет. В CPython (стандартная реализация Python) функция set_intersection обрабатывает пересечение множества. В случае, когда другой аргумент также является набором, функция поменяет местами два набора таким образом, что меньший будет повторяться, а больший набор используется для поиска (постоянное время), как Booboo описано :

        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))}")