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ディクショナリのメモリ効率の高い実装はありますか?