Time-complessità di verificare se due set sono uguali in Python

Question

lettura this question, mi chiedevo quanto tempo (asintoticamente parlando) ci vuole per Python per valutare le espressioni come

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

Vale a dire, per controllare se due istanze di set class sono uguali.

Answer 1

Il confronto tra i set è implementato dallo function set_richcompare in setobject.c, line 1848. Vedrete che l'uguaglianza è implementato come segue:

1. Se i set non hanno la stessa dimensione, restituire false.

2. Se entrambi gli insiemi sono stati sottoposti a hash e gli hash sono diversi, restituire false.

3. Chiama set_issubset.

Il test sottoinsieme per due set si presenta in questo modo:

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; 

Vedrai che funziona mediante iterazione su tutti gli elementi del primo set e poi guardando ognuno nell'altro impostato. Quindi (a meno che non ci siano molte collisioni hash) questo è lineare nella dimensione del primo set.