pyplot - subplot python title

¿Cómo se implementa set()?

Question

He visto a personas decir que los objetos 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, por lo que daré la respuesta más aproximada a mi pregunta original. ¡Gracias a todos por la información!

Answer 1

Creo que es un error común, la búsqueda de set (o hashtable para ese asunto) no son O (1).
de la Wikipedia

En el modelo más simple, la función hash no está especificada por completo 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.

Relacionado: ¿Es un hashmap de Java realmente O (1)?

Answer 2

Cuando las personas dicen que los conjuntos tienen O (1) verificación de membresía, están hablando del caso promedio . En el peor de los casos (cuando todos los valores hash colisionan) la comprobación de membresía es O (n). Vea la wiki de Python sobre la complejidad del tiempo .

El artículo de Wikipedia dice que la mejor complejidad de tiempo de caso para una tabla hash que no cambia de 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 adelante en el artículo de Wikipedia dice que para el caso promedio , y suponiendo una función de hashing uniforme simple, la complejidad del tiempo es O(1/(1-k/n)) , donde k/n puede estar delimitada por una constante c<1 .

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

O(1/(1-k/n)) no es mayor que O(1/(1-c)) que es equivalente a O(constant) = O(1) .

Por lo tanto, suponiendo que el hash simple uniforme, en promedio , la comprobación de membresía para los conjuntos de Python es O(1) .

Answer 3

De acuerdo con este hilo :

De hecho, los conjuntos de CPython se implementan como algo así como diccionarios con valores ficticios (las claves son los miembros del conjunto), con algunas optimizaciones que explotan esta falta de valores.

Entonces, 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 apetece , incluso puede navegar por el código fuente de CPython para el conjunto que, según Achim Domma , es en su mayoría un corte y pegar de la implementación dict .

Answer 4

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

Los casos de uso para conjuntos difieren considerablemente de los diccionarios donde las claves buscadas tienen más probabilidades de estar presentes. Por el contrario, los conjuntos se refieren principalmente a las pruebas de membresía donde la presencia de un elemento no se conoce de antemano. En consecuencia, la implementación del conjunto necesita optimizar tanto para el caso encontrado como el no encontrado.

fuente en github

Answer 5

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

/* set object implementation
Written and maintained by Raymond D. Hettinger <[email protected]>
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)
{
...