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

Ответ 1

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

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

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

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

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

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

• словарь состоит из нескольких ковшей, каждая из которых содержит

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

  в целом не менее 12 байтов на 32 бит и 24 байта на 64-битной версии.

• Словарь начинается с 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 -tool составляет 4,6 МБ. Таким образом, общее ожидаемое потребление памяти после создания словаря составляет примерно 4.6 + 2.65 = 7.25 MB. истинный объем памяти (согласно ps) в моем тесте 7,6 МБ. Я предполагаю, что дополнительные ок. 0,35 МБ были израсходованы накладные расходы, генерируемые с помощью стратегии распределения памяти Python (для арена памяти и т.д.).

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

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

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

Ответ 2

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

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

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

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

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

Это FAST и позволит вам легко переносить вещи, то есть вам не нужно загружать весь набор в каждый раз, когда вы хотите его использовать.

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

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

Ответ 3

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

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

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

Numpy (http://numpy.org) выделяет структуры данных, используя собственные C-структуры. Большинство его структур данных предполагают, что вы сохраняете один тип данных, поэтому это не для всех ситуаций (вам может потребоваться хранить нуль и т.д.), Но это может быть очень, очень, очень быстро и примерно так же компактно, как вы могли бы попросить. С ним справляется много науки (см. Также: 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

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

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

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

Удачи!