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

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

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

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

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

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

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

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

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

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

Как насчет массива Judy, если вы используете сопоставление с ints? Это своего рода редкий массив … Использует 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-битных указателей)

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

 key0 value0 key1 value1 key2 value2 ... 

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

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

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