python - Pythonでのメモリ効率の高いint-intdict

Question

O（log n）時間で次の操作をサポートするPythonのメモリ効率の高いint-intdictが必要です。

d[k] = v  # replace if present
v = d[k]  # None or a negative number if not present

私は約2億5000万ペアを保持する必要があるので、それは本当にタイトでなければなりません。

適切な実装（Python 2.7）を知っていますか？

編集不可能な要件やその他のナンセンスを削除しました。ありがとう、クレイグとキロタン！

言い換えると。これは、1Mペアの簡単なint-int辞書です。

>>> import random, sys
>>> from guppy import hpy
>>> h = hpy()
>>> h.setrelheap()
>>> d = {}
>>> for _ in xrange(1000000):
...     d[random.randint(0, sys.maxint)] = random.randint(0, sys.maxint)
... 
>>> h.heap()
Partition of a set of 1999530 objects. Total size = 49161112 bytes.
 Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
     0      1   0 25165960  51  25165960  51 dict (no owner)
     1 1999521 100 23994252  49  49160212 100 int

平均して、整数のペアは49バイトを使用します。

2Mの整数の配列は次のとおりです。

>>> import array, random, sys
>>> from guppy import hpy
>>> h = hpy()
>>> h.setrelheap()
>>> a = array.array('i')
>>> for _ in xrange(2000000):
...     a.append(random.randint(0, sys.maxint))
... 
>>> h.heap()
Partition of a set of 14 objects. Total size = 8001108 bytes.
 Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
     0      1   7  8000028 100   8000028 100 array.array

平均して、整数のペアは8バイトを使用します。

辞書で8バイト/ペアを達成するのは一般的にかなり難しいことを私は受け入れます。 言い換えると、49バイト/ペアよりかなり少ない値を使用するint-intディクショナリのメモリ効率の高い実装はありますか？

score 6 · Accepted Answer

6

ZopeのIIBtreeを使用できます

于 2010-10-26T11:46:51.530 に答える

score 5 · Accepted Answer

これがワンショットソリューションなのか、進行中のプロジェクトの一部なのかはわかりませんが、前者の場合、メモリ使用量を最適化するために必要な開発者の時間よりも安く、より多くのRAMを投入していますか？ペアあたり64バイトであっても、15GBしか見ていません。これは、ほとんどのデスクトップボックスに簡単に収まります。

正解はおそらくSciPy/NumPyライブラリ内にあると思いますが、どこを見ればよいかを正確に伝えるには、ライブラリに精通していません。

http://docs.scipy.org/doc/numpy/reference/

また、このスレッドでいくつかの有用なアイデアを見つけることができます： Python辞書のメモリ効率の良い代替手段

score 4 · Accepted Answer

キー/値ペアあたり8バイトは、Pythonやその他の実装では、かなり困難です。キーが連続しているという保証がない場合は、配列表現を使用してキー間のスペースを大量に浪費するか（nullキーを示すために何らかのデッド値が必要になる）、またはキーと値のペアに対して個別のインデックスを維持する必要があります。これは、定義上、ペアあたり8バイトを超えます（少量であっても）。

配列メソッドを使用することをお勧めしますが、最善のアプローチは、私が期待するキーの性質によって異なります。

score 3 · Accepted Answer

intsからマッピングしている場合、Judy配列はどうですか？これは一種のスパース配列です...辞書実装のスペースの1/4を使用します。

ジュディ：

$ cat j.py ; time python j.py 
import judy, random, sys
from guppy import hpy
random.seed(0)
h = hpy()
h.setrelheap()
d = judy.JudyIntObjectMap()
for _ in xrange(4000000):
    d[random.randint(0, sys.maxint)] = random.randint(0, sys.maxint)

print h.heap()
Partition of a set of 4000004 objects. Total size = 96000624 bytes.
 Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
     0 4000001 100 96000024 100  96000024 100 int
     1      1   0      448   0  96000472 100 types.FrameType
     2      1   0       88   0  96000560 100 __builtin__.weakref
     3      1   0       64   0  96000624 100 __builtin__.PyJudyIntObjectMap

real    1m9.231s
user    1m8.248s
sys     0m0.381s

辞書：

$ cat d.py ; time python d.py   
import random, sys
from guppy import hpy
random.seed(0)
h = hpy()
h.setrelheap()
d = {}
for _ in xrange(4000000):
    d[random.randint(0, sys.maxint)] = random.randint(0, sys.maxint)

print h.heap()
Partition of a set of 8000003 objects. Total size = 393327344 bytes.
 Index  Count   %     Size   % Cumulative  % Kind (class / dict of class)
     0      1   0 201326872  51 201326872  51 dict (no owner)
     1 8000001 100 192000024  49 393326896 100 int
     2      1   0      448   0 393327344 100 types.FrameType

real    1m8.129s
user    1m6.947s
sys     0m0.559s

スペースの約1/4：

$ echo 96000624 / 393327344 | bc -l
.24407309958089260125

（私は64ビットのPythonを使用しているので、64ビットのポインターが原因でベース番号が大きくなる可能性があります）

score 2 · Accepted Answer

上記のデータを見ると、intあたり49バイトではなく、25バイトです。エントリあたりの他の24バイトは、intオブジェクト自体です。したがって、エントリあたり25バイトよりも大幅に小さいものが必要です。intオブジェクトも再実装する場合を除いて、少なくともキーハッシュでは可能です。または、オブジェクトを完全にスキップできるCで実装します（これは、前述のZopes IIBTreeが行うことです）。

正直なところ、Python辞書はさまざまな方法で高度に調整されています。それを打ち負かすのは簡単ではありませんが、幸運を祈ります。

score 1 · Accepted Answer

ここで入手できる独自のint-int辞書を実装しました（BSDライセンス）。要するに、私はarray.array('i')キーでソートされたキーと値のペアを格納するために使用します。key/65536実際、挿入時のシフトと取得時のバイナリ検索を高速化するために、1つの大きな配列の代わりに、小さな配列の辞書を保持しています（キーと値のペアはth配列に格納されています）。各配列は、次の方法でキーと値を格納します。

key0 value0 key1 value1 key2 value2 ...

実際、これはint-intディクショナリであるだけでなく、オブジェクトがハッシュに縮小された一般的なobject-intディクショナリです。したがって、hash-intディクショナリは、永続的に保存されているディクショナリのキャッシュとして使用できます。

「キーの衝突」を処理するには、3つの可能な戦略があります。つまり、同じキーに異なる値を割り当てようとします。デフォルトの戦略ではそれが可能です。「削除」はキーを削除し、衝突としてマークするため、それ以上値を割り当てようとしても効果はありません。「叫び」戦略は、上書きの試行中および衝突するキーへのそれ以上のアクセス時に例外をスローします。

私のアプローチの別の言い回しの説明については、関連する質問への私の回答を参照してください。

python - Pythonでのメモリ効率の高いint-intdict

6 に答える 6

Related

Reference