Эффективная память int-int dict в Python

Question

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

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

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

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

РЕДАКТИРОВАТЬ Убрал невозможное требование и прочую ерунду.Спасибо, Крейг и Килотан!

---

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

>>> 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 байт / пара?

Answer 1

Вы можете использовать IIBtree от Zope

Answer 2

Я не знаю, является ли это одноразовым решением или частью текущего проекта, но если это первый, то затрачивает ли на него больше оперативной памяти, чем затрачиваемое разработчиком время для оптимизации использования памяти?Даже при 64 байтах на пару вы по-прежнему просматриваете только 15 ГБ, которые достаточно легко поместятся в большинство настольных ПК.

Я думаю, что правильный ответ, вероятно, находится в библиотеках SciPy / NumPy, но янедостаточно знаком с библиотекой, чтобы точно сказать вам, где искать.

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

Вы также можете найти несколько полезных идей в этой теме: Эффективные по памяти альтернативы словарям Python

Answer 3

8 байт на пару ключ / значение было бы довольно сложно при любой реализации, Python или иным образом.Если у вас нет гарантии, что ключи являются смежными, то вы либо потратили бы много места между ключами, используя представление массива (а также нуждаясь в каком-то мертвом значении для указания нулевого ключа), либо вынеобходимо поддерживать отдельный индекс для пар ключ / значение, который по определению будет превышать ваши 8 байтов на пару (даже если только на небольшое количество).

Я предлагаю вам использовать метод массива, нолучший подход будет зависеть от характера ожидаемых ключей.

Answer 4

Как насчет массива Джуди, если вы отображаете из целых чисел? Это своего рода разреженный массив ... Использует 1/4 пространства словарной реализации.

Judy:

$ 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-битных указателей)

Answer 5

Глядя на ваши данные выше, это не 49 байт на целое, это 25. Остальные 24 байта на запись - это сами объекты int.Таким образом, вам нужно что-то значительно меньше, чем 25 байт на запись.Если вы также не собираетесь переопределять объекты int, что возможно, по крайней мере, для ключевых хэшей.Или реализуйте его в C, где вы можете полностью пропустить объекты (это то, что Zopes IIBTree делает, упомянуто выше).

Если честно, словарь Python сильно настраивается различными способами.Это будет не легко победить, но удачи.

Answer 6

Я реализовал свой собственный словарь int-int, доступен здесь (лицензия BSD).Короче говоря, я использую array.array('i') для хранения пар ключ-значение, отсортированных по ключам.Фактически, вместо одного большого массива я сохраняю словарь из меньших массивов (пара ключ-значение хранится в key/65536 -ом массиве), чтобы ускорить смещение во время вставки и двоичный поиск во время поиска.Каждый массив хранит ключи и значения следующим образом:

key0 value0 key1 value1 key2 value2 ...

На самом деле это не только словарь int-int, но и общий словарь object-int, в котором объекты сокращены до их хэшей.Таким образом, словарь hash-int может использоваться как кэш некоторого постоянно хранимого словаря.

Существует три возможных стратегии обработки «столкновений ключей», то есть попытки присвоить другое значение одному и тому же ключу.,Стратегия по умолчанию позволяет это.«Удаление» удаляет ключ и помечает его как конфликтующий, поэтому любые дальнейшие попытки присвоить ему значение не будут иметь никакого эффекта.«Кричащая» стратегия выдает исключение при любой попытке перезаписи и при любом последующем доступе к любому коллизирующему ключу.

См. мой ответ на связанный вопрос дляиначе сформулированное описание моего подхода.