¿Se ordenan los diccionarios en Python 3.6+?

python-3.x dictionary

Question

Los diccionarios se ordenan en Python 3.6 (al menos en la implementación de CPython) a diferencia de las encarnaciones anteriores. Esto parece un cambio sustancial, pero es solo un breve párrafo en la documentation . Se describe como un detalle de implementación de CPython en lugar de una función de lenguaje, pero también implica que esto puede convertirse en estándar en el futuro.

¿Cómo funciona mejor la nueva implementación del diccionario que la anterior al tiempo que conserva el orden de los elementos?

Aquí está el texto de la documentación:

dict() ahora usa una representación "compacta" iniciada por PyPy . El uso de memoria del nuevo dict () es entre un 20% y un 25% menor en comparación con Python 3.5. PEP 468 (Preservar el orden de ** kwargs en una función) es implementado por esto. El aspecto de preservación del orden de esta nueva implementación se considera un detalle de implementación y no se debe confiar en él (esto puede cambiar en el futuro, pero se desea tener esta nueva implementación dict en el idioma durante algunas versiones antes de cambiar la especificación del idioma para ordenar la semántica de preservación del orden para todas las implementaciones actuales y futuras de Python; esto también ayuda a preservar la compatibilidad con versiones anteriores del lenguaje donde el orden de iteración aleatoria todavía está en vigencia, por ejemplo, Python 3.5). (Contribución de INADA Naoki en el número 27350. Idea sugerida originalmente por Raymond Hettinger ).

Actualización de diciembre de 2017: el pedido de inserción de retención de dict está guaranteed para Python 3.7

Answer 1

¿Se ordenan los diccionarios en Python 3.6+?

Se ordenan por inserción ^[1] . A partir de Python 3.6, para la implementación CPython de Python, los diccionarios recuerdan el orden de los elementos insertados . Esto se considera un detalle de implementación en Python 3.6 ; debe usar OrderedDict si desea un orden de inserción garantizado en otras implementaciones de Python (y otro comportamiento ordenado ^[1] ).

A partir de Python 3.7 , esto ya no es un detalle de implementación, sino que se convierte en una característica del lenguaje. guaranteed :

Hazlo así. "Dict mantiene orden de inserción" es el fallo. ¡Gracias!

Esto simplemente significa que puede confiar en ello . Otras implementaciones de Python también deben ofrecer un diccionario de inserción ordenada si desean ser una implementación conforme de Python 3.7.

¿Cómo funciona mejor la implementación del diccionario Python 3.6 ^[2] que la anterior al tiempo que conserva el orden de los elementos?

Básicamente, manteniendo dos matrices .

• La primera matriz, dk_entries , contiene las entradas ( de tipo PyDictKeyEntry ) para el diccionario en el orden en que se insertaron. El orden de preservación se logra al ser una matriz de agregar solo donde siempre se insertan nuevos elementos al final (orden de inserción).

• El segundo, dk_indices , contiene los índices para la matriz dk_entries (es decir, valores que indican la posición de la entrada correspondiente en dk_entries ). Esta matriz actúa como la tabla hash. Cuando una clave se codifica, conduce a uno de los índices almacenados en dk_indices y la entrada correspondiente se obtiene indexando dk_entries . Dado que solo se mantienen los índices, el tipo de esta matriz depende del tamaño general del diccionario (que va desde el tipo int8_t ( 1 byte) hasta int32_t / int64_t ( int64_t bytes) en las versiones de 64 bits)

En la implementación anterior, se tenía que asignar una matriz dispersa de tipo PyDictKeyEntry y tamaño dk_size ; desafortunadamente, también resultó en mucho espacio vacío ya que no se permitió que esa matriz tuviera más de 2/3 * dk_size completo por razones de rendimiento . (¡y el espacio vacío todavía tenía el tamaño PyDictKeyEntry !).

Este no es el caso ahora, ya que solo se almacenan las entradas requeridas (las que se han insertado) y se mantiene una matriz dispersa de tipo intX_t ( X dependiendo del tamaño del dict) 2/3 * dk_size s full. El espacio vacío cambió de tipo PyDictKeyEntry a intX_t .

Entonces, obviamente, crear una matriz dispersa de tipo PyDictKeyEntry mucha más memoria que una matriz dispersa para almacenar int s.

Puede ver la conversación completa mail.python.org/pipermail/python-dev/2016-September/146327.html respecto a esta característica si está interesado, es una buena lectura.

En la propuesta original hecha por Raymond Hettinger , se puede ver una visualización de las estructuras de datos utilizadas que captura la esencia de la idea.

Por ejemplo, el diccionario:

d = {''timmy'': ''red'', ''barry'': ''green'', ''guido'': ''blue''}

actualmente está almacenado como:

entries = [[''--'', ''--'', ''--''],
           [-8522787127447073495, ''barry'', ''green''],
           [''--'', ''--'', ''--''],
           [''--'', ''--'', ''--''],
           [''--'', ''--'', ''--''],
           [-9092791511155847987, ''timmy'', ''red''],
           [''--'', ''--'', ''--''],
           [-6480567542315338377, ''guido'', ''blue'']]

En cambio, los datos deben organizarse de la siguiente manera:

indices =  [None, 1, None, None, None, 0, None, 2]
entries =  [[-9092791511155847987, ''timmy'', ''red''],
            [-8522787127447073495, ''barry'', ''green''],
            [-6480567542315338377, ''guido'', ''blue'']]

Como puede ver visualmente ahora, en la propuesta original, una gran cantidad de espacio está esencialmente vacío para reducir las colisiones y agilizar las búsquedas. Con el nuevo enfoque, reduce la memoria requerida al mover la escasez donde realmente se requiere, en los índices.

_{[1]: Digo "inserción ordenada" y no "ordenada" ya que, con la existencia de OrderedDict, "ordenada" sugiere un comportamiento adicional que el objeto dict no proporciona . Los OrderedDicts son reversibles, proporcionan métodos sensibles al orden y, principalmente, proporcionan pruebas de igualdad sensibles al orden ( == ,! != ). Actualmente, los dict no ofrecen ninguno de esos comportamientos / métodos.}

_{[2]: Las nuevas implementaciones de diccionario funcionan mejor en cuanto a memoria al estar diseñadas de manera más compacta; Ese es el principal beneficio aquí. En cuanto a la velocidad, la diferencia no es tan drástica, hay lugares donde el nuevo dict podría introducir leves regresiones ( búsquedas de teclas, por ejemplo ), mientras que en otros (la iteración y el cambio de tamaño vienen a la mente) un aumento de rendimiento debería estar presente.}

_{En general, el rendimiento del diccionario, especialmente en situaciones de la vida real, mejora debido a la compacidad introducida.}

Answer 2

A continuación se responde la primera pregunta original:

¿Debo usar dict u OrderedDict en Python 3.6?

Creo que esta oración de la documentación es suficiente para responder a su pregunta.

El aspecto de preservación del orden de esta nueva implementación se considera un detalle de implementación y no se debe confiar en él

dict no está destinado explícitamente a ser una colección ordenada, por lo que si desea mantenerse coherente y no confiar en un efecto secundario de la nueva implementación, debe seguir con OrderedDict .

Haga su código a prueba de futuro :)

Hay un debate sobre eso here .

EDITAR: Python 3.7 mantendrá esto como una función see

Answer 3

Actualización: Guido van Rossum guaranteed que a partir de los dict s de Python 3.7 en todas las implementaciones de Python debe preservar el orden de inserción.

Answer 4

Quería agregar a la discusión anterior, pero no tengo la reputación de comentar.

Python 3.8 aún no se ha lanzado del todo, pero incluso incluirá la función reversed() en los diccionarios (eliminando otra diferencia de OrderedDict .

Dict y dictviews ahora son iterables en orden de inserción invertido usando reverse (). (Contribución de Rémi Lapeyre en bpo-33462.) Vea las novedades de python 3.8

No veo ninguna mención del operador de igualdad u otras características de OrderedDict por lo que todavía no son del todo iguales.