Int-int dict с эффективным использованием памяти в Python

Мне нужен эффективный с точки зрения памяти int-int dict в Python, который поддерживал бы следующие операции в O (log n) time:

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

Мне нужно хранить ~ 250M пар, так что действительно должно быть плотным.

Вы случайно не знаете подходящую реализацию (Python 2.7)?

EDIT ] Убрано невозможное требование и прочую чушь. Спасибо, Крейг и Килотан!

Перефразируя. Вот тривиальный словарь int-int с 1 миллионами пар:

>>> 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 байтов на пару в словаре в целом довольно сложно достичь. Перефразированный вопрос: существует ли эффективная для памяти реализация словаря int-int, который использует значительно меньше 49 байт на пару?