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

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

Son inserción ordenada^[1]. A partir de Python 3.6, para la implementación de 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 otras ordenadas comportamiento^[1]).

A partir de Python 3.7 , esto ya no es un detalle de implementación y en su lugar se convierte en una característica de lenguaje. De un mensaje python-dev de GvR:

Hazlo así. "Dict mantiene la 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 conformes implementación de Python 3.7.

¿Cómo funciona mejor la implementación del diccionario Python 3.6?^[2] que el más antiguo conservando el orden de los elementos?

Esencialmente, por manteniendo dos matrices.

• El primer array, dk_entries, contiene las entradas ( de tipo PyDictKeyEntry) para el diccionario en el orden en que fueron insertados. Preservar el orden se logra al ser un apéndice solo array donde siempre se insertan nuevos elementos al final (orden de inserción).

• El segundo, dk_indices, contiene los índices de 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 es hash, conduce a uno de los índices almacenados en dk_indices y la entrada correspondiente se obtiene indexando dk_entries. Dado que solo se mantienen índices, el tipo de esta matriz depende del tamaño total de la diccionario (que van desde el tipo de int8_t(1 byte) a int32_t/int64_t (4/8 bytes) 32/64 poco construye)

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 una gran cantidad de espacio vacío ya que no se permitía que esa matriz estuviera más que 2/3 * dk_size llena por razones de rendimiento. (y el espacio vacío todavía tenía PyDictKeyEntry tamaño!).

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

Así que, obviamente, crear una matriz dispersa de tipo {[6] } requiere mucho más memoria que una matriz dispersa para almacenar ints.

Puedes ver la conversación completa en Python-Dev con respecto a esto 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'}

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 se puede ver visualmente ahora, en la propuesta original, una gran cantidad de espacio es esencialmente vacío para reducir colisiones y hacer búsquedas más rápidas. Con el nuevo enfoque, se reduce la memoria requerida moviendo 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. OrderedDicts are reversible, provide order sensitive methods and, mainly, provide an order-sensive pruebas de igualdad(==, !=). dictactualmente no ofrecen ninguno de esos comportamientos/métodos.}

_{[2]: Las nuevas implementaciones del diccionario funcionan mejor en cuanto a memoria al ser diseñadas de forma 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 dictado podría introducir ligeras regresiones ( búsquedas de teclas, por ejemplo), mientras que en otros (iteración y cambio de tamaño vienen a la mente) un rendimiento boost debería estar presente.}

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