Tiempo-complejidad de comprobar si dos conjuntos son iguales en Python

Question

lectura this question, me preguntaba cuánto tiempo (asintóticamente hablando) hace que se tarda en Python para evaluar expresiones como

{1,2}=={2,1} 

Es decir, para comprobar si dos instancias del set class son iguales.

Answer 1

La comparación entre los conjuntos está implementada por el function set_richcompare in setobject.c, line 1848. Verá que la igualdad se implementa de la siguiente manera:

1. Si los conjuntos no tienen el mismo tamaño, devuelva falso.

2. Si ambos conjuntos han sido hash, y los hash son diferentes, devuelve falso.

3. Llame set_issubset.

La prueba subconjunto de dos conjuntos tiene el siguiente aspecto:

while (set_next(so, &pos, &entry)) { 
    int rv = set_contains_entry((PySetObject *)other, entry); 
    if (rv == -1) 
     return NULL; 
    if (!rv) 
     Py_RETURN_FALSE; 
} 
Py_RETURN_TRUE; 

Verás que funciona mediante una iteración sobre todos los elementos del primer set y luego mirando hacia arriba cada uno en el otro conjunto. Entonces (a menos que haya muchas colisiones hash) esto es lineal en el tamaño del primer conjunto.