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

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

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

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

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

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


Перефразировать. Вот тривиальный словарь 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 байт / пару?

6 Solutions collect form web for “Эффективная память 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 можно использовать в качестве кеша некоторого постоянно хранимого словаря.

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

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

  • Установить на питон Python
  • Что означает «dict-like» в Python?
  • Используйте dicts как элементы в наборе в Python
  • Разница между dict и set (python)
  • pythonic способ связать элементы списка с их индексами
  • Python словарь, который отображает строки в набор строк?
  • Как использовать наборы Python и добавлять к нему строки в качестве значения словаря
  • Что такое объект сопоставления, в соответствии с типом dict?
  • Комбинации словаря со значениями в списке с использованием Python
  • Согласованность порядка Dict / Set Parsing
  • В Python, как вы можете легко получить отсортированные элементы из словаря?
  • Python - лучший язык программирования в мире.