¿Hay alguna razón para no usar un OrderedDict?

Me refiero a OrderedDict del módulo de collections , que es un diccionario ordenado.

Si tiene la funcionalidad adicional de ser ordenable, me doy cuenta de que a menudo no es necesario, pero aun así, ¿hay alguna desventaja? ¿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?

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 debajo de las cubiertas, y una lista doblemente enlazada de todas las claves (esa es la parte que recuerda el pedido), y un montón de proxies de debilidad de referencia. No es mucho más lento, pero al menos duplica la memoria en lugar de usar un dict simple.

Pero si es apropiado, ¡úsalo! Por eso está ahí 🙂

Cómo funciona

El dict de base es simplemente un dict ordinario que asigna claves a valores, no está “ordenado” en absoluto. Cuando se agrega un par , la key se agrega a una lista. La lista es la parte que recuerda el pedido.

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

Así que es una lista doblemente enlazada. Eso hace que la eliminación de una clave sea constante ( O(1) ). Pero todavía tenemos que encontrar el nodo de la lista con doble enlace que pertenece a la clave. Para hacer esa operación O(1) tiempo también, un segundo dictado, oculto, asigna claves a nodos en la lista de enlaces dobles.

Por lo tanto, agregar un nuevo par requiere agregar el par al dict de base, crear un nuevo nodo de lista con doble enlace para mantener la clave, agregar ese nuevo nodo a la lista con doble enlace y asignar la clave a ese nuevo nodo en el dict oculto Un poco más del doble de trabajo, pero aún así O(1) (caso esperado) en general.

De manera similar, eliminar una clave que está presente también es un poco más del doble de trabajo, pero O(1) tiempo total esperado: use el dictador oculto para encontrar el nodo de la lista doblemente enlazada de la clave, elimine ese nodo de la lista y elimine la clave a partir de los dos dictados.

Etc. Es bastante eficiente.

multihilo

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

las operaciones de dictado de vainilla 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 locking), aunque no puedo descartar la posibilidad de que se haya codificado con mucho cuidado y cumpla con la definición de reentrada.

demonios menores

uso de memoria si crea toneladas de estos diccionarios

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

¿Por qué no debería usar siempre 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 de forma predeterminada en cPython, pero deshabilitarlo tiene sus usos .

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  gc: collectable  0 [[[...], [...], 'key'], [[...], [...], 'key'], None] 1 [[[...], [...], None], [[...], [...], None], 'key'] 

Incluso si creas un OrderedDict vacío ( d = collections.OrderedDict() ) y no le agregas nada, o tratas explícitamente de limpiarlo llamando al método clear ( d.clear() antes de d.clear() ), todavía obtendrá una lista de autorreferencia:

 gc: collectable  0 [[...], [...], None] 

Este parece haber sido el caso, ya que este compromiso eliminó el método __del__ para evitar que OrderedDict causara ciclos incobrables, que posiblemente sean peores. Como se señala en el registro de cambios para ese compromiso:

Problema nº 9825 : se eliminó __del__ de la definición de collections.OrderedDict. Esto evita que los diccionarios ordenados de autorreferencia creados por el usuario se conviertan en basura GC imposible de recolectar. La desventaja es que eliminar __del__ significa que la lista interna doblemente enlazada tiene que esperar la recostackción del GC en lugar de liberar la memoria inmediatamente cuando el refcnt cae a cero.


Tenga en cuenta que en Python 3, la solución para el mismo problema se hizo de manera diferente y utiliza proxies de debilidad para evitar ciclos:

Problema nº 9825: el uso de __del__ en la definición de colecciones.OrderedDict hizo posible que el usuario crease diccionarios ordenados que hacen referencia a sí mismos y que se convierten en basura GC imposible de recolectar. Se restableció el enfoque de Py3.1 de usar proxies de debilidad débil para que los ciclos de referencia nunca se creen en primer lugar.

Desde Python 3.7, todos los diccionarios están garantizados para ser ordenados. Los contribuyentes de Python determinaron que cambiar a hacer un dict ordenado no tendría un impacto negativo en el rendimiento. No sé cómo el rendimiento de OrderedDict compara con dict en Python> = 3.7, pero imagino que serían comparables ya que ambos están ordenados.

Ver también:

  • ¿Se convertirá OrderedDict en redundante en Python 3.7 ?