Сериализация памяти Python

Мне было интересно, может ли кто-нибудь узнать ответ на следующее.

Я использую Python для создания дерева суффиксов на основе символов. В дереве содержится более 11 миллионов узлов, которые подходят примерно к 3 ГБ памяти. Это снизилось с 7 ГБ с помощью метода класса слот, а не метода Dict.

Когда я сериализую дерево (используя самый высокий протокол), результирующий файл более чем в сто раз меньше.

Когда я загружаю маринованный файл, он снова потребляет 3 ГБ памяти. Откуда возникают эти дополнительные накладные расходы, связано ли это с тем, что Pythons обрабатывает ссылки на память на экземпляры классов?

Обновление

Спасибо вам, ларшаны и Gurgeh за ваши очень полезные объяснения и советы. Я использую дерево как часть интерфейса поиска информации над корпусом текстов.

Я изначально сохранил дочерние элементы (максимум 30) в качестве массива Numpy, затем попробовал версию аппаратного обеспечения (ctypes.py_object*30), массив Python (ArrayType), а также словарь и типы Set.

Списки, казалось, делали лучше (с помощью guppy для профилирования памяти и __slots__['variable',...]), но я все еще пытаюсь выжать его немного больше, если смогу. Единственная проблема, с которой я столкнулся с массивами, - это заранее указать их размер, что вызывает некоторую избыточность в терминах узлов с одним ребенком, и у меня их довольно много.; -)

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

Я дам вам знать, как это происходит.

Ответ 1

Если вы попытаетесь рассортировать пустой список, вы получите:

>>> s = StringIO()
>>> pickle.dump([], s)
>>> s.getvalue()
'(l.'

и аналогично '(d.' для пустого dict. Это три байта. Однако представление в списке в списке содержит

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

На моей машине, которая имеет 64-битные указатели, sizeof объект заголовка списка Python составляет 40 байтов, поэтому на один порядок. Я предполагаю, что пустой dict будет иметь одинаковый размер.

Затем обе стратегии list и dict используют стратегию обхода, чтобы получить амортизированную производительность O (1) для их основных операций, malloc вводит накладные расходы, выравнивание, атрибуты членов, которые вы можете или не можете даже знать, и различные другие факторы, которые вы получите во втором порядке.

Подведение итогов: pickle - довольно хороший алгоритм сжатия для объектов Python:)

Ответ 2

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

Дикты и объекты очень хороши для динамической модификации, но они не очень эффективны в пространстве в режиме только для чтения. Я не знаю точно, для чего вы используете дерево суффиксов, но вы можете позволить каждому node быть представленным 2-мя экземплярами отсортированного массива .array('c') и одинаково длинный кортеж субномов (a кортеж вместо вектора, чтобы избежать обхода). Вы просматриваете дерево, используя модуль bisect для поиска в массиве. Индекс символа в массиве будет соответствовать подзоне в корте subdode. Таким образом вы избегаете dicts, объектов и вектора.

Вы могли бы сделать что-то подобное во время процесса строительства, возможно, используя субнодный вектор, а не subnode-кортеж. Но это, конечно, сделает конструкцию медленнее, поскольку вставка новых узлов в отсортированный вектор - O (N).