Me sorprendió descubrir recientemente que, si bien los dictos están garantizados para preservar el orden de inserción en Python 3.7+, los conjuntos no son:
>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d
{'a': 1, 'b': 2, 'c': 3}
>>> d['d'] = 4
>>> d
{'a': 1, 'b': 2, 'c': 3, 'd': 4}>>> s = {'a', 'b', 'c'}
>>> s
{'b', 'a', 'c'}
>>> s.add('d')
>>> s
{'d', 'b', 'a', 'c'}¿Cuál es la razón de esta diferencia? ¿Las mismas mejoras de eficiencia que llevaron al equipo de Python a cambiar la implementación de dict no se aplican también a los conjuntos?
No busco punteros para implementaciones de conjuntos ordenados o formas de usar dictos como sustitutos para conjuntos. Me pregunto por qué el equipo de Python no hizo que los conjuntos incorporados conservaran el orden al mismo tiempo que lo hicieron para los dictados.
dictysetdesde 2.7.Respuestas:
Los conjuntos y los dictos están optimizados para diferentes casos de uso. El uso principal de un conjunto es la prueba rápida de membresía, que es independiente del orden. Para los dictados, el costo de la búsqueda es la operación más crítica, y es más probable que la clave esté presente. Con los conjuntos, la presencia o ausencia de un elemento no se conoce de antemano, por lo que la implementación del conjunto debe optimizarse tanto para el caso encontrado como para el no encontrado. Además, algunas optimizaciones para las operaciones de conjuntos comunes, como la unión y la intersección, dificultan la retención del orden de conjuntos sin degradar el rendimiento.
Si bien ambas estructuras de datos están basadas en hash, es un error común pensar que los conjuntos solo se implementan como dictados con valores nulos. Incluso antes de la implementación compacta dict en CPython 3.6, las implementaciones set y dict ya diferían significativamente, con poca reutilización de código. Por ejemplo, los dictos usan sondeo aleatorio, pero los conjuntos usan una combinación de sondeo lineal y direccionamiento abierto, para mejorar la localidad de caché. La sonda lineal inicial ( 9 pasos predeterminados en CPython) verificará una serie de pares clave / hash adyacentes, mejorando el rendimiento al reducir el costo del manejo de colisiones hash: el acceso consecutivo a la memoria es más barato que las sondas dispersas.
dictobject.c- maestro , v3.5.9setobject.c- maestro , v3.5.9En teoría, sería posible cambiar la implementación establecida de CPython para que sea similar al dict compacto, pero en la práctica hay inconvenientes, y los desarrolladores principales notables se opusieron a hacer tal cambio.
- Guido van Rossum
- Raymond Hettinger
Puede encontrar una discusión detallada sobre si se compactarán conjuntos para 3.7, y respuestas sobre por qué se decidió en contra, en las listas de correo python-dev.
En resumen, los puntos principales son que los patrones de uso son diferentes (los dictados de orden de inserción como ** kwargs son útiles , menos para los conjuntos), el ahorro de espacio para los conjuntos de compactación es menos significativo (porque solo hay claves y matrices hash para densificar, en lugar de claves, valores hash y valores), y la optimización de sondeo lineal antes mencionada en conjuntos es incompatible con una implementación compacta.
Reproduciré la publicación de Raymond a continuación que cubre los puntos más importantes.
De [Python-Dev] Python 3.6 dict se vuelve compacto y obtiene una versión privada; y las palabras clave se ordenan , septiembre de 2016.
fuente
Discusiones
Su pregunta es pertinente y ya se ha debatido mucho en python-devs no hace mucho tiempo. R. Hettinger compartió una lista de fundamentos en ese hilo . El estado del problema parece abierto ahora, poco después de esta respuesta detallada de T. Peters.
En resumen, la implementación de dictos modernos que conserva el orden de inserción es única y no se considera apropiada con los conjuntos. En particular, los dictos se utilizan en todas partes para ejecutar Python (por ejemplo,
__dict__en espacios de nombres de objetos). Una motivación importante detrás del dict moderno fue reducir el tamaño, haciendo que Python sea más eficiente en memoria en general. Por el contrario, los conjuntos son menos frecuentes que los dictados dentro del núcleo de Python y, por lo tanto, disuaden tal refactorización. Ver también la charla de R. Hettinger sobre la implementación moderna del dict.Perspectivas
La naturaleza desordenada de los conjuntos en Python es paralela al comportamiento de los conjuntos matemáticos . El pedido no está garantizado.
Si se introdujera un orden de cualquier tipo en conjuntos en Python, entonces este comportamiento cumpliría con una estructura matemática completamente separada, a saber, un conjunto ordenado (u Oset). Las Osets juegan un rol separado en matemáticas, particularmente en combinatoria. Se observa una aplicación práctica de Osets en el cambio de campanas .
Tener conjuntos desordenados es coherente con una estructura de datos muy genérica y ubicua que desenreda la matemática más moderna, es decir, la teoría de conjuntos . Presento que es bueno tener conjuntos desordenados en Python.
Vea también publicaciones relacionadas que se expanden sobre este tema:
fuente