OrderedDict vs Dict в python

В Тим Питер ответит на "Есть ли причины не использовать упорядоченный словарь", говорит он

OrderedDict является подклассом dict.

Это не намного медленнее, но, по крайней мере, удваивает память, используя простой dict.

Теперь, просматривая конкретный вопрос , я попробовал несколько выборочных проверок с помощью ipython, и оба они противоречат предыдущим аргументам:

  • оба dict и OrderedDict имеют одинаковый размер
  • работающий на OrderedDict, занимает около 7-8 раз больше времени, чем работа на dict (следовательно, намного медленнее).

Может кто-нибудь объяснить мне, где я ошибаюсь в своих рассуждениях?

Создайте большой Dict и OrderedDict и сравните размеры:

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

Проверьте время, затраченное на вставку, с помощью %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

Ответы

Ответ 1

Я думаю, что проблема с размером связана с тем, что нет метода __sizeof__, определенного в Python 2.X реализация OrderedDict, поэтому он просто возвращается к методу dict __sizeof__.

Чтобы доказать это здесь, я создал класс A здесь, который расширяет list, а также добавил дополнительный метод foo, чтобы проверить, влияет ли это на размер.

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))

Но этот же размер возвращается sys.getsizeof:

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

Конечно, A будет медленным, потому что его методы запущены в Python, тогда как метод списка будет работать в чистом C.

>>> %%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

И это, по-видимому, исправлено в Python 3, где есть теперь определенный метод __sizeof__:

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