29

さまざまなPythonデータ型のメモリ消費について多くの質問と議論があります。しかし、それらのいくつか（もしあれば）は非常に特定のシナリオになります。大量のKey-Valueデータをメモリに格納する場合、メモリ効率が高いデータ構造、dict、またはタプルのリストはどれですか。

最初は、dictはタプルのリストよりも強力であり、その力にはある程度の代償が必要だと思っていました。実際、空のdictは、空のリストやタプルよりも多くのメモリを占有します（Python構造のメモリ内サイズを参照）。を使用[(key1, value1), (key2, value2), ...]すると、よりもメモリ効率が高くなると考えられ{key1: value1, key2: value2, ...}ました。

私が間違っていたようです。次のコードスニペットを起動するだけで、OSによって報告されたメモリ消費量を確認できます。私はWindowsXPを使用しているので、タスクマネージャーは、大きなdictは40MBのRAMと40MBのVIRTURAL RAMのみを消費しますが、タプルのリストは60MBのRAMと60MBの仮想RAMを消費します。

どうしてそうなるのでしょうか？

from sys import getsizeof as g
raw_input('ready, press ENTER')
i = 1000000
#p = [(x, x) for x in xrange(i)] # Will print 4,348,736 40,348,736
p = dict((x, x) for x in xrange(i)) # Will print 25,165,964 37,165,964
print g(p), g(p) + sum(g(x) for x in p)
raw_input("Check your process's memory consumption now, press ENTER to exit")

アップデート：

以下のコメントをありがとう。明確にしておきたいのは、メモリ効率について話しているということです。いいえ、この場合、Key-Valueルックアップの効率について心配する必要はありません。私のアルゴリズムが、イテレーターを介してそれらを1つずつ消費すると仮定しましょう。

4

2 に答える 2

31

あなたlistのtuplesは余分なレイヤーを追加します。3層のアイテムがあります。

  • 長さ100万の外側のリスト、つまり100万のポインター
    • 100万の2スロットタプル、つまり200万のポインター
      • 100万の整数値への200万の参照

あなたdictだけが保持している間：

  • 200万個のポインターとテーブルを拡張するための追加スペースを備えたdict（100万個のキャッシュされたハッシュを含む）
    • 100万の整数値への200万の参照

100万個のタプルに加えて、それらへの参照を保持するリストが、100万個のキャッシュされたハッシュよりも多くのメモリを消費します。ここには約50％多いポインタが含まれており、見られるメモリ使用量が50％多いことを簡単に説明できます。

タプルのリストには、ルックアップ時間というもう1つの欠点があります。dictで一致するキーを見つけるには、O（1）の複雑さのコストがかかります。タプルのリストで同じことを行うには、リスト全体をスキャンしてO（n）コストを計算する必要があります。キーを値にマップする必要がある場合は、タプルのリストを使用しないでください。

于 2013-03-26T15:50:53.460 に答える
13

この場合、実際にはメモリ使用量の全体像が不完全になっています。辞書の合計サイズは不規則な間隔で2倍以上になります。辞書のサイズが大きくなった直後に、これら2つの構造のサイズを比較すると、再び大きくなります。再帰サイズ関数を使用した単純なスクリプト（以下のコードを参照）は、非常に明確なパターンを示しています。

i:  2  list size:  296  dict size:  328  difference:  -32
i:  3  list size:  392  dict size:  352  difference:  40
i:  4  list size:  488  dict size:  376  difference:  112
i:  5  list size:  616  dict size:  400  difference:  216
i:  7  list size:  808  dict size:  1216  difference:  -408
i:  10  list size:  1160  dict size:  1288  difference:  -128
i:  13  list size:  1448  dict size:  1360  difference:  88
i:  17  list size:  1904  dict size:  1456  difference:  448
i:  23  list size:  2480  dict size:  3904  difference:  -1424
i:  31  list size:  3328  dict size:  4096  difference:  -768
i:  42  list size:  4472  dict size:  4360  difference:  112
i:  56  list size:  5912  dict size:  4696  difference:  1216
i:  74  list size:  7880  dict size:  5128  difference:  2752
i:  100  list size:  10520  dict size:  14968  difference:  -4448
i:  133  list size:  14024  dict size:  15760  difference:  -1736
i:  177  list size:  18672  dict size:  16816  difference:  1856

このパターンはi成長するにつれて続きます。（これは、自分の方法を使用してテストできます。i近くに設定してみ2636744てください。少なくとも私にとっては、その時点で辞書のサイズが大きくなっています。）Martijnは、タプルのリスト内のタプルがメモリオーバーヘッドに追加され、キャンセルされるのは正しいことです。辞書に対するリストのメモリの利点。しかし、結果は、平均して、辞書が優れているということではありません。辞書はほぼ同じだということです。だからあなたの元の質問に答えて：

大量のKey-Valueデータをメモリに格納する場合、メモリ効率が高いデータ構造、dict、またはタプルのリストはどれですか。

あなたが心配しているのが記憶だけであるかどうかは本当に問題ではありません。

ただし、ディクショナリのすべての空のビンの反復を回避する良い方法がないため、ディクショナリの反復はリストの反復よりも少し遅いことが多いことに注意してください。したがって、多少のトレードオフがあります。辞書はランダムキールックアップを実行する場合は（はるかに）高速ですが、リストは反復時に（少し）高速です。ほとんどの場合、辞書の方が優れている可能性がありますが、まれに、リストがマイクロ最適化を提供する場合があります。

サイズをテストするコードは次のとおりです。おそらくすべてのコーナーケースで正しい結果が生成されるわけではありませんが、このような単純な構造を問題なく処理できるはずです。（ただし、問題が発生した場合はお知らせください。）

import sys, collections, itertools, math

def totalsize(x):
    seen = set()
    return ts_rec(x, seen)

def ts_rec(x, seen):
    if id(x) in seen:
        return 0
    else:
        seen.add(id(x))

    x_size = sys.getsizeof(x)
    if isinstance(x, collections.Mapping):
        kv_chain = itertools.chain.from_iterable(x.iteritems())
        return x_size + sum(ts_rec(i, seen) for i in kv_chain)
    elif isinstance(x, collections.Sequence):
        return x_size + sum(ts_rec(i, seen) for i in x)
    else:
        return x_size

for i in (10 ** (e / 8.0) for e in range(3, 19)):
    i = int(i)
    lsize = totalsize([(x, x) for x in xrange(i)])
    dsize = totalsize(dict((x, x) for x in xrange(i)))

    print "i: ", i,
    print " list size: ", lsize, " dict size: ", dsize,
    print " difference: ", lsize - dsize
于 2013-03-26T17:24:04.400 に答える