python - dict - ¿Hay alguna razón para no usar un diccionario ordenado?

ordereddict python 3

Question

Me refiero al OrderedDict del módulo de collections .

Si tiene la funcionalidad añadida de ser ordenable, lo cual, a mi entender, a menudo puede no ser necesario, pero aun así, ¿hay algún inconveniente? ¿Es más lento? ¿Falta alguna funcionalidad? No vi ningún método faltante.

En resumen, ¿por qué no debería usar siempre esto en lugar de un diccionario normal?

Answer 1

¿Por qué no debería siempre usar esto en lugar de un diccionario normal?

En Python 2.7, el uso normal de OrderedDict creará ciclos de referencia . Por lo tanto, cualquier uso de OrderedDict requiere que el recolector de basura esté habilitado para liberar la memoria. Sí, el recolector de basura está activado por defecto en cPython, pero deshabilitarlo tiene sus aplicaciones .

por ejemplo, con cPython 2.7.14

from __future__ import print_function

import collections
import gc

if __name__ == ''__main__'':
    d = collections.OrderedDict([(''key'', ''val'')])
    gc.collect()
    del d
    gc.set_debug(gc.DEBUG_LEAK)
    gc.collect()
    for i, obj in enumerate(gc.garbage):
        print(i, obj)

salidas

gc: collectable <list 00000000033E7908>
gc: collectable <list 000000000331EC88>
0 [[[...], [...], ''key''], [[...], [...], ''key''], None]
1 [[[...], [...], None], [[...], [...], None], ''key'']

Incluso si solo crea un OrderedDict vacío ( d = collections.OrderedDict() ) y no le agrega nada, o explícitamente intenta limpiarlo llamando al método clear ( d.clear() before del d ), aún obtendrá una lista de auto-referencia:

gc: collectable <list 0000000003ABBA08>
0 [[...], [...], None]

Este parece haber sido el caso dado que esta confirmación eliminó el método __del__ para evitar la posibilidad de que OrderedDict cause ciclos incobrables, que posiblemente sean peores. Como se indica en el registro de cambios para esa confirmación:

Problema n. ° 9825 : eliminado __del__ de la definición de colecciones.OrderedDict. Esto evita que los diccionarios ordenados por el usuario creados por el usuario se conviertan en basura del GC permanentemente incobrable. La desventaja es que la eliminación de __del__ significa que la lista interna doblemente enlazada tiene que esperar la recopilación de GC en lugar de liberar la memoria inmediatamente cuando el refcnt cae a cero.

Tenga en cuenta que en Python 3, la fix para el mismo problema se hizo de manera diferente y utiliza proxies weakref para evitar ciclos:

Problema n. ° 9825: Utilizando __del__ en la definición de colecciones. OrderedDict hizo posible que el usuario creara diccionarios ordenados autorreferencialmente que se convirtieran en basura de CG permanentemente incobrable. Se reestableció el enfoque Py3.1 de usar proxies weakref para que los ciclos de referencia nunca se creen en primer lugar.

Answer 2

OrderedDict es una subclase de dict y necesita más memoria para realizar un seguimiento del orden en que se agregan las claves. Esto no es trivial. La implementación agrega un segundo dict bajo las cubiertas, y una lista doblemente enlazada de todas las claves (esa es la parte que recuerda el orden), y un grupo de proxies weakref. No es mucho más lento, pero al menos dobla la memoria sobre el uso de un dict simple.

¡Pero si es apropiado, úselo! Es por eso que está ahí :-)

Cómo funciona

El dict base es solo un ordinario Dict cartografía claves a valores - no es "ordenado" en absoluto. Cuando se agrega un par de <key, value> , la key se agrega a una lista. La lista es la parte que recuerda el orden.

Pero si esta fuera una lista de Python, eliminar una clave tomaría O(n) tiempo dos veces: O(n) tiempo para encontrar la clave en la lista, y O(n) tiempo para eliminar la clave de la lista.

Entonces, es una lista doblemente vinculada. Eso hace que borrar una clave sea constante ( O(1) ) vez. Pero todavía tenemos que encontrar el nodo de lista doblemente vinculado que pertenece a la clave. Para hacer que esa operación sea O(1) también, un segundo oculto - asigna claves a los nodos en la lista doblemente enlazada.

Así que agregar un nuevo par de <key, value> requiere agregar el par al dict base, crear un nuevo nodo de lista doblemente enlazado para mantener la clave, agregar ese nuevo nodo a la lista doblemente enlazada y mapear la clave a esa nueva nodo en el dict oculto. Un poco más del doble de trabajo, pero aún O(1) (caso esperado) en general.

De forma similar, eliminar una clave que está presente también es un poco más del doble de trabajo pero O(1) tiempo esperado en general: use el dict oculto para encontrar el nodo de lista doblemente vinculado de la clave, elimine ese nodo de la lista y elimine la clave de ambos dictados.

Etc. Es bastante eficiente.

Answer 3

multihilo

si se accede a su diccionario desde varios hilos sin un candado, especialmente como un punto de sincronización.

Las operaciones dict de vanilla son atómicas, y cualquier tipo extendido en Python no lo es.

De hecho, ni siquiera estoy seguro de que OrderedDict sea seguro para subprocesos (sin bloqueo), aunque no puedo descartar la posibilidad de que haya sido cuidadosamente codificado y satisfaga la definición de reentrada.

demonios menores

uso de memoria si creas toneladas de estos diccionarios

el uso de la CPU si todo su código lo hace es munge estos diccionarios