¿Los diccionarios están ordenados en Python 3.6+?

Los diccionarios están ordenados en Python 3.6 (al menos bajo la implementación de CPython) a diferencia de las encarnaciones anteriores. Esto parece un cambio sustancial, pero es solo un párrafo corto en la documentación . Se describe como un detalle de implementación de CPython en lugar de una característica de lenguaje, pero también implica que esto puede volverse estándar en el futuro.

¿Cómo funciona mejor la implementación del nuevo 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% más pequeño en comparación con Python 3.5. PEP 468 (Preservando el orden de ** kwargs en una función.) Se implementa mediante esto. El aspecto de conservación de orden de esta nueva implementación se considera un detalle de la implementación y no se debe confiar en él (esto puede cambiar en el futuro, pero se desea tener esta nueva implementación de dictado en el idioma para algunas versiones antes de cambiar la especificación del idioma). para ordenar la semántica de conservación de órdenes para todas las implementaciones actuales y futuras de Python, esto también ayuda a preservar la compatibilidad con versiones anteriores del lenguaje en el que el orden de iteración aleatorio sigue vigente, 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 orden de inserción de retención s está garantizado para Python 3.7

¿Los diccionarios están ordenados en Python 3.6+?

Son ordenados de 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 que el orden de inserción esté 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 y se convierte en una característica de lenguaje. De un mensaje python-dev por GvR :

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

Esto simplemente significa que puedes depender de ello . Otras implementaciones de Python también deben ofrecer un diccionario ordenado de inserción 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?

Esencialmente, 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 conservación se logra al ser una matriz solo anexa 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 está en hash, conduce a uno de los índices almacenados en dk_indices y la entrada correspondiente se recupera indexando dk_entries . Dado que solo se mantienen los índices, el tipo de esta matriz depende del tamaño total del diccionario (desde el tipo int8_t ( 1 byte) hasta int32_t / int64_t ( int64_t bytes) en comstackciones de 64 bits)

En la implementación anterior, se tuvo 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 la matriz estuviera más de 2/3 * dk_size full por razones de rendimiento . (y el espacio vacío todavía tenía tamaño PyDictKeyEntry !).

Este no es el caso ahora ya que solo se almacenan las entradas necesarias (aquellas 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 en Python-Dev con respecto a esta función 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'} 

se almacena actualmente como:

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

En su lugar, 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 ahora visualmente, en la propuesta original, una gran cantidad de espacio está esencialmente vacío para reducir las colisiones y hacer que las búsquedas sean más rápidas. Con el nuevo enfoque, reduce la memoria requerida moviendo la dispersión 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 artículos ordenados son reversibles, proporcionan métodos sensibles al orden y, principalmente, proporcionan pruebas de igualdad sensibles al orden ( == ,! != ). dict s actualmente no ofrecen ninguno de esos comportamientos / métodos.


[2]: Las implementaciones del nuevo diccionario funcionan mejor en cuanto a memoria al ser 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 dictamen puede introducir regresiones leves ( búsquedas de clave, por ejemplo ), mientras que en otros (la iteración y el cambio de tamaño vienen a la mente) debería estar presente un aumento de rendimiento.

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

A continuación está respondiendo la primera pregunta original:

¿Debo usar dict o OrderedDict en Python 3.6?

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

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

dict no tiene la intención explícita de ser una recostackción ordenada, por lo tanto, si desea mantenerse coherente y no confiar en un efecto secundario de la nueva implementación, debe atenerse a OrderedDict .

Haga su código a prueba de futuro 🙂

Hay un debate sobre eso aquí .

EDITAR: Python 3.7 mantendrá esto como una característica ver

Actualización: Guido van Rossum anunció en la lista de correo que a partir de Python 3.7 los dict de todas las implementaciones de Python deben conservar el orden de inserción.