¿Cómo se implementa set()?
He visto gente decir que setlos objetos en Python tienen verificación de membresía O(1). ¿Cómo se implementan internamente para permitir esto? ¿Qué tipo de estructura de datos utiliza? ¿Qué otras implicaciones tiene esa implementación?
Cada respuesta aquí fue realmente esclarecedora, pero solo puedo aceptar una, así que elegiré la respuesta más cercana a mi pregunta original. ¡Gracias a todos por la información!
Según 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.
Básicamente, a setutiliza una tabla hash como estructura de datos subyacente. Esto explica la O(1)verificación de membresía, ya que buscar un elemento en una tabla hash es una O(1)operación, en promedio.
Si lo desea, puede incluso explorar el código fuente de CPythonset que, según Achim Domma , originalmente era principalmente un cortar y pegar de la dictimplementación.
Nota: Hoy en día, las implementaciones de sety han divergido significativamente , por lo que los comportamientos precisos (por ejemplo, orden arbitrario versus orden de inserción) y el rendimiento en varios casos de uso difieren; todavía se implementan en términos de tablas hash, por lo que la búsqueda e inserción de casos promedio se mantiene , pero ya no es solo " , sino con valores ficticios/omitidos".dictO(1)setdict
Cuando la gente dice que los conjuntos tienen una verificación de membresía O (1), se refieren al caso promedio . En el peor de los casos (cuando todos los valores hash chocan), la verificación de membresía es O(n). Consulte la wiki de Python sobre la complejidad del tiempo .
El artículo de Wikipedia dice que el mejor caso de complejidad temporal para una tabla hash que no cambia de tamaño es O(1 + k/n). Este resultado no se aplica directamente a los conjuntos de Python ya que los conjuntos de Python utilizan una tabla hash que cambia de tamaño.
Un poco más adelante, el artículo de Wikipedia dice que para el caso promedio , y suponiendo una función hash uniforme simple, la complejidad del tiempo es O(1/(1-k/n)), donde k/npuede estar limitada por una constante c<1.
Big-O se refiere sólo al comportamiento asintótico como n → ∞. Dado que k/n puede estar acotado por una constante, c<1, independiente de n ,
O(1/(1-k/n))no es mayor que O(1/(1-c))lo que equivale a O(constant)= O(1).
Entonces, suponiendo un hash simple y uniforme, en promedio , la verificación de membresía para conjuntos de Python es O(1).
Todos tenemos fácil acceso a la fuente , donde el comentario anterior 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)
{
...
Para enfatizar un poco más la diferencia entre set'sy dict's, aquí hay un extracto de las setobject.csecciones de comentarios, que aclaran la principal diferencia entre conjuntos y dictados.
Los casos de uso de conjuntos difieren considerablemente de los diccionarios donde es más probable que estén presentes las claves buscadas. Por el contrario, los conjuntos se refieren principalmente a pruebas de membresía en las que la presencia de un elemento no se conoce de antemano. En consecuencia, la implementación del conjunto debe optimizarse tanto para el caso encontrado como para el caso no encontrado.
fuente en github
Los conjuntos en Python emplean una tabla hash internamente. Primero hablemos de la tabla hash. Deje que haya algunos elementos que desee almacenar en una tabla hash y tenga 31 lugares en la tabla hash donde pueda hacerlo. Sean los elementos: 2,83, 8,23, 9,38, 10,23, 25,58, 0,42, 5,37, 28,10, 32,14, 7,31. Cuando desee utilizar una tabla hash, primero determine los índices en la tabla hash donde se almacenarían estos elementos. La función de módulo es una forma popular de determinar estos índices, así que digamos que tomamos un elemento a la vez, lo multiplicamos por 100 y aplicamos el módulo por 31. Es importante que cada operación de este tipo en un elemento dé como resultado un número único como La entrada en una tabla hash puede almacenar solo un elemento a menos que se permita el encadenamiento. De esta forma, cada elemento se almacenaría en una ubicación gobernada por los índices obtenidos mediante la operación módulo. Ahora, si desea buscar un elemento en un conjunto que esencialmente almacena elementos usando esta tabla hash, obtendrá el elemento en tiempo O(1) ya que el índice del elemento se calcula usando la operación de módulo en un tiempo constante. Para explicar la operación del módulo, permítanme escribir también un código:
piles = [2.83, 8.23, 9.38, 10.23, 25.58, 0.42, 5.37, 28.10, 32.14, 7.31]
def hash_function(x):
return int(x*100 % 31)
[hash_function(pile) for pile in piles]
Salida: [4, 17, 8, 0, 16, 11, 10, 20, 21, 18]
