¿Cómo se implementa set()?

Question

He visto a personas decir que los objetos set en python tienen O (1) comprobación de membresía. ¿Cómo se implementan internamente para permitir esto? ¿Qué tipo de estructura de datos usa? ¿Qué otras implicaciones tiene esa implementación?

Todas las respuestas aquí fueron realmente esclarecedoras, pero solo puedo aceptar una, así que voy a responder con la mayor precisión a mi pregunta original. ¡Gracias a todos por la información!

Answer 1

Según this thread:

De hecho, los conjuntos de CPython se implementan como algo así como diccionarios con valores ficticios (las teclas siendo los miembros del conjunto), con un poco de optimización (s) que explotan esta falta de valores

Así que básicamente un set utiliza una tabla hash como su estructura de datos subyacente. Esto explica la comprobación de pertenencia O (1), ya que buscar un elemento en una tabla hash es una operación O (1), en promedio.

Si le gusta, puede incluso navegar por el CPython source code for set que, de acuerdo con Achim Domma, es principalmente un método de cortar y pegar de la implementación dict.

Answer 2

Creo que es un error común, set búsqueda (o hashtable para el caso) no son O (1).
from the Wikipedia

En el modelo más simple, la función hash es completamente indeterminado y la tabla no cambia de tamaño. Para la mejor elección posible de la función hash, una tabla de tamaño n con un direccionamiento abierto no tiene colisiones y contiene hasta n elementos, con una única comparación para una búsqueda exitosa, y una tabla de tamaño n con cadenas y k tiene el mínimo (0, kn) colisiones y O (1 + k/n) comparaciones para la búsqueda. Para la peor opción de función hash, cada inserción provoca una colisión y las tablas hash degeneran en búsqueda lineal, con comparaciones amortizadas Ω (k) por inserción y hasta k comparaciones para una búsqueda exitosa.

relacionadas: Is a Java hashmap really O(1)?

Answer 3

Todos tenemos fácil acceso a the source, donde el comentario anterior set_lookkey() dice:

/* set object implementation 
Written and maintained by Raymond D. Hettinger <python@rcn.com> 
Derived from Lib/sets.py and Objects/dictobject.c. 
The basic lookup function used by all operations. 
This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4. 
The initial probe index is computed as hash mod the table size. 
Subsequent probe indices are computed as explained in Objects/dictobject.c. 
To improve cache locality, each probe inspects a series of consecutive 
nearby entries before moving on to probes elsewhere in memory. This leaves 
us with a hybrid of linear probing and open addressing. The linear probing 
reduces the cost of hash collisions because consecutive memory accesses 
tend to be much cheaper than scattered probes. After LINEAR_PROBES steps, 
we then use open addressing with the upper bits from the hash value. This 
helps break-up long chains of collisions. 
All arithmetic on hash should ignore overflow. 
Unlike the dictionary implementation, the lookkey function can return 
NULL if the rich comparison returns an error. 
*/ 


... 
#ifndef LINEAR_PROBES 
#define LINEAR_PROBES 9 
#endif 

/* This must be >= 1 */ 
#define PERTURB_SHIFT 5 

static setentry * 
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash) 
{ 
... 

Answer 4

Cuando la gente dice conjuntos tienen O (1) membresía de comprobación, que son hablando sobre el caso promedio. En el caso peor (cuando todos los valores hash colisionan) la comprobación de membresía es O (n). Vea el Python wiki on time complexity.

El Wikipedia article dice el mejor de los casos complejidad de tiempo para una tabla hash que no cambia el tamaño es O(1 + k/n). Este resultado no se aplica directamente a los conjuntos Python ya que los conjuntos Python usan una tabla hash que cambia de tamaño.

Un poco más en el artículo de Wikipedia dice que para el caso promedio, y asumiendo una simple función de hash uniforme, la complejidad del tiempo es O(1/(1-k/n)), donde k/n puede estar delimitado por una constante c<1.

Big-O se refiere solo al comportamiento asintótico como n → ∞. Desde k/n puede estar delimitado por una constante, c < 1, independiente de n,

O(1/(1-k/n)) es no más grande que O(1/(1-c)) que es equivalente a O(constant) = O(1).

Asumiendo hashing simple uniforme, en promedio, comprobación de pertenencia para conjuntos de Python es O(1).

Answer 5

Para enfatizar un poco más la diferencia entre set's y dict's, aquí hay un extracto de las secciones de comentarios setobject.c, que aclaran la principal diferencia de los conjuntos contra los dicts.

Los casos de uso de los juegos difieren considerablemente de los diccionarios en los que las claves buscadas son más propensas a estar presentes. Por el contrario, los conjuntos son principalmente sobre la prueba de membresía donde no se conoce la presencia de un elemento en el avance . De acuerdo con esto, la implementación del conjunto necesita optimizar tanto el caso encontrado como el no encontrado para el caso encontrado .

fuente de github