OrderedDict vs Dict en python

En la respuesta de Tim Peter a “¿Hay alguna razón para no usar un diccionario ordenado?”, Dice.

OrderedDict es una subclase de dict.

No es mucho más lento, pero al menos duplica la memoria en lugar de usar un dict simple.

Ahora, mientras pasaba por una pregunta en particular , probé algunos controles de muestra usando ipython y ambos contradicen el razonamiento anterior:

  1. tanto dict como OrderedDict son del mismo tamaño
  2. operar en un OrderedDict toma fácilmente alrededor de 7-8 veces más tiempo que operar en un dict (por lo tanto, mucho más lento)

¿Puede alguien explicarme dónde me equivoco en mi razonamiento?


Crea un gran Dict y OrderedDict y compara tamaños:

 import sys import random from collections import OrderedDict test_dict = {} test_ordered_dict = OrderedDict() for key in range(10000): test_dict[key] = random.random() test_ordered_dict[key] = random.random() sys.getsizeof(test_dict) 786712 sys.getsizeof(test_ordered_dict) 786712 

Verifique el tiempo de las inserciones usando %timeit :

 import sys import random from collections import OrderedDict def operate_on_dict(r): test_dict = {} for key in range(r): test_dict[key] = random.random() def operate_on_ordered_dict(r): test_ordered_dict = OrderedDict() for key in range(r): test_ordered_dict[key] = random.random() %timeit for x in range(100): operate_on_ordered_dict(100) 100 loops, best of 3: 9.24 ms per loop %timeit for x in range(100): operate_on_dict(100) 1000 loops, best of 3: 1.23 ms per loop 

Creo que el problema con el tamaño se debe al hecho de que no hay __sizeof__ método __sizeof__ definido en la implementación Python 2.X de OrderedDict , por lo que simplemente __sizeof__ método __sizeof__ de dict.

Para demostrar esto aquí, he creado una clase A aquí que extiende la list y también agregué un método adicional foo para verificar si eso afecta el tamaño.

 class A(list): def __getitem__(self, k): return list.__getitem__(self, k) def foo(self): print 'abcde' >>> a = A(range(1000)) >>> b = list(range(1000)) 

Pero aún el mismo tamaño es devuelto por sys.getsizeof :

 >>> sys.getsizeof(a), sys.getsizeof(b) (9120, 9120) 

Por supuesto, A va a ser lento porque sus métodos se ejecutan en Python, mientras que el método de la lista se ejecutará en C pura.

 >>> %%timeit ... for _ in xrange(1000): ... a[_] ... 1000 loops, best of 3: 449 µs per loop >>> %%timeit for _ in xrange(1000): b[_] ... 10000 loops, best of 3: 52 µs per loop 

Y esto parece solucionarse en Python 3, donde ahora hay un método __sizeof__ bien definido:

 def __sizeof__(self): sizeof = _sys.getsizeof n = len(self) + 1 # number of links including root size = sizeof(self.__dict__) # instance dictionary size += sizeof(self.__map) * 2 # internal dict and inherited dict size += sizeof(self.__hardroot) * n # link objects size += sizeof(self.__root) * n # proxy objects return size