Python: сокращение использования памяти словаря

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

Если вы посмотрите на реализация Python словаря (которая является относительно простой реализацией хеш-таблицы), а также на реализацию встроенных строковых и целочисленных типов данных, например здесь (в частности, object.h, intobject.h, stringobject.h и dictobject .h, а также соответствующие файлы *.c в ../Objects), можно с некоторой точностью рассчитать ожидаемые требования к пространству:

1. Целое число — это объект фиксированного размера, т. е. он содержит счетчик ссылок, указатель типа и фактическое целое число, обычно не менее 12 байтов в 32-битной системе и 24 байта в 64-битной системе, без учета лишнего пространства, которое может быть потеряно из-за выравнивания.

2. Объект string имеет переменный размер, что означает, что он содержит

• счетчик ссылок

• указатель типа

• информация о размере

• место для лениво вычисляемого хэш-кода

• информация о состоянии (например, используется для интернированных строк)

• указатель на динамическое содержимое

  всего не менее 24 байт для 32-разрядной версии или 60 байт для 64-разрядной версии, не включая место для самой строки.

1. Сам словарь состоит из нескольких сегментов, каждый из которых содержит

• хэш-код хранящегося в данный момент объекта (который нельзя предсказать по положению ведра из-за используемой стратегии разрешения коллизий)

• указатель на ключевой объект

• указатель на объект значения

  всего не менее 12 байт для 32-разрядной версии и 24 байта для 64-разрядной версии.

1. Словарь начинается с 8 пустых сегментов, и его размер изменяется за счет удвоения количества записей при достижении его емкости.

Я провел тест со списком из 46 461 уникальной строки (размер объединенной строки 337 670 байт), каждая из которых связана с целым числом — аналогично вашей настройке на 32-разрядной машине. Согласно приведенному выше расчету, я ожидаю, что минимальный объем памяти

• 46 461 * (24+12) байт = 1,6 МБ для комбинаций строки/целого числа.
• 337 670 = 0,3 МБ для содержимого строки
• 65 536 * 12 байт = 1,6 МБ для сегментов хеширования (после 13-кратного изменения размера)

всего 2,65 МБ. (Для 64-битной системы соответствующий расчет дает 5,5 МБ.)

При работе интерпретатора Python в режиме ожидания его размер согласно ps-инструменту составляет 4,6 МБ. Таким образом, общее ожидаемое потребление памяти после создания словаря составляет примерно 4,6 + 2,65 = 7,25 МБ. Реальный объем памяти (согласно ps) в моем тесте составил 7,6. МБ. Я предполагаю, что дополнительно ок. 0,35 МБ были израсходованы накладными расходами, созданными с помощью стратегии распределения памяти Python (для арен памяти и т. д.).

Конечно, многие люди теперь укажут, что мое использование ps для измерения объема памяти является неточным, и мои предположения о размерах типов указателей и целых чисел в 32-битных и 64-битных системах могут быть неверными во многих конкретных системах. Предоставленный.

Но, тем не менее, ключевые выводы, я считаю, таковы:

• Реализация словаря в Python потребляет на удивление небольшой объем памяти.
• Но пространство, занимаемое многими объектами int и (в частности) строковыми объектами, для подсчета ссылок, предварительно рассчитанных хэш-кодов и т. д., больше, чем вы думаете. первый
• Существует едва ли способ избежать накладных расходов на память, если вы используете Python и хотите, чтобы строки и целые числа представлялись как отдельные объекты — по крайней мере, я не понимаю, как это можно сделать.
• Возможно, стоит поискать (или реализовать самостоятельно) расширение Python-C, реализующее хэш, хранящий ключи и значения в виде C-указателей (а не объектов Python). Я не знаю, существует ли это; но я считаю, что это можно сделать и уменьшить объем памяти более чем наполовину.

1) SQLite в памяти звучит как отличное решение, это позволит вам легче запрашивать ваши данные после их загрузки, что доставляет удовольствие

sqlite3.connect(':память:')

2) вам, вероятно, нужен именованный кортеж - я почти уверен, что они легче, чем словари, и вы можете получить доступ к свойствам, используя точечную нотацию (к чему у меня все равно есть эстетическое предпочтение).

http://docs.python.org/dev/library/collections

3) вы можете взглянуть на Redis: https://github.com/andymccurdy/redis-py

Это БЫСТРО и позволит вам легко сохранять вещи, а это означает, что вам не нужно загружать весь набор каждый раз, когда вы хотите его использовать.

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

Но в целом именованные кортежи, вероятно, являются хитростью.

На диске у вас есть только строки, при загрузке в Python интерпретатор должен создать целую структуру для каждой строки и для каждого словаря, помимо самой строки.

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

Похоже на Trie ( http://en.m.wikipedia.org/wiki/Trie) структура данных может лучше соответствовать вашему стремлению к эффективности памяти.

Обновление: эффективность использования памяти python dict была поднята как проблема, хотя она была отклонена из стандартной библиотеки из-за доступности сторонних библиотек. См.: http://bugs.python.org/issue9520.

Вы можете заменить dict на blist.sorteddict для доступа к log(n) без накладных расходов на память. Он удобен тем, что ведет себя точно так же, как словарь, т.е. реализует все свои методы, так что вам нужно изменить только исходный тип.

Если вы пытаетесь компактно хранить числовые данные в python в памяти, лучшим решением, вероятно, будет Numpy.

Numpy (http://numpy.org) размещает структуры данных, используя собственные структуры C. Большинство его структур данных предполагают, что вы храните один тип данных, так что это не для всех ситуаций (вам может понадобиться хранить null и т. д.), но это может быть очень, очень, очень быстро и примерно так же компактно, как вы могли бы попросить. С его помощью делается много научных работ (см. также: SciPy).

Конечно, есть и другой вариант: zlib, если у вас:

• Достаточные циклы ЦП и
• МНОГО данных, которые не помещаются в память

Вы можете просто объявить «страницу» данных (какой бы большой вы ни хотели) как массив, прочитать данные, сохранить их в массиве, заархивировать, а затем прочитать еще некоторые данные, пока у вас не будет всех данных в памяти, которую вы хотеть.

Затем перебирайте страницы, разархивируйте, преобразуйте обратно в массив и выполняйте необходимые операции. Например:

def arrayToBlob(self, inArray):
    a = array.array('f', inArray)
    return a.tostring()

def blobToArray(self, blob, suppressWarning=False):
    try:
        out = array.array('f', [])
        out.fromstring(blob)
    except Exception, e:
        if not suppressWarning:
            msg = "Exception: blob2array, err: %s, in: %s" % (e, blob)
            self.log.warning(msg)
            raise Exception, msg
    return out

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

Конечно, это медленнее, чем хранить все это в несжатом виде, но если вы не можете уместить его в памяти, ваш выбор с самого начала ограничен.

Даже при сжатии все это может не поместиться в памяти, и в этот момент вам, возможно, придется записать сжатые страницы в виде строк или солений и т. д.

Удачи!