Время выполнения бинарных операторов с множеством

Question

Меня смущает время выполнения бинарного оператора множества в Python. например - set1 | set2 Требуется ли линейное время как set1 - set2 или квадратичное время, так как каждый элемент в set1 должен быть побитовым или с каждым числом set2, или наоборот.

Я просмотрел несколько веб-сайтов, но не смог найти четкого представления об этом. ref: https://www.geeksforgeeks.org/sets-in-python/

Answer 1

В Objects / setobject.c в исходном коде CPython есть функция set_or, которую Python использует для | под капотом.

Для тех, кто не умеет читать C, исходный код можно обобщить следующим образом:

def is_any_set(o: object) -> bool:
    return isinstance(o, (set, frozenset))

def set_or(so: set, other: set) -> set:
    if not is_any_set(so) or not is_any_set(other):
        return NotImplemented
    result = so.copy()
    if so is other:
        return result
    result.update(other)
    return result

Так скажем n = len(so); m = len(other). Отсюда видно, что это комбинация set.copy, равная O(n), и set.update, равная O(m) (линейная по отношению ко второму набору). Таким образом, время для всей операции составляет O(n + m), что является линейным, в зависимости от размера обоих наборов.

(Обратите внимание, что это зависит от hash(o), являющегося постоянным.)

Answer 2

Давайте попробуем:

from time import time
from random import randint

size = 1
while size < 100000000:
    size *= 10
    set1 = {randint(0, size * 100) for _ in range(size)}
    set2 = {randint(0, size * 100) for _ in range(size)}
    start = time()
    diff = set1 | set2
    end = time()
    print(end - start, '-', size, '-', (end - start)/size)

выход:

4.0531158447265625e-06 - 10 - 4.0531158447265624e-07
1.52587890625e-05 - 100 - 1.52587890625e-07
0.00018405914306640625 - 1000 - 1.8405914306640625e-07
0.002404928207397461 - 10000 - 2.404928207397461e-07
0.015778064727783203 - 100000 - 1.5778064727783204e-07
0.16070318222045898 - 1000000 - 1.60703182220459e-07

Время выполнения явно линейное.