15

「順序付けられた辞書を使用しない理由はありますか」に対するTim Peterの回答で、彼は言います

OrderedDict は dict のサブクラスです。

それほど遅くはありませんが、プレーンな dict を使用するよりもメモリが少なくとも 2 倍になります。

今、特定の質問をしている間、私はいくつかのサンプルチェックを試しipythonましたが、どちらも以前の推論と矛盾しています:

  1. dictとの両方OrderedDictが同じサイズです
  2. での操作は、での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
4

1 に答える 1

10

サイズの問題は、の__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リストのメソッドは純粋な C で実行されますが、そのメソッドは Python で実行されるため、もちろん遅くなります。

>>> %%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
于 2014-07-31T11:01:36.387 に答える