Эффективность памяти: один большой словарь или словарь меньших словарей?

Question

Я пишу приложение на Python (2.6), которое требует от меня использования словаря в качестве хранилища данных.

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

Я знаю, что в целом много списков и словарей. Я где-то читал, что python внутренне выделяет достаточно места, чтобы словарь / список # элементов в степени 2.

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

Одна из трудностей состоит в том, чтобы знать, как сила 2 системы считает "предметы"? Каждый ключ: пара считается за 1 предмет? Это важно знать, потому что если у вас есть монолитный словарь из 100 элементов, то будет выделено 100 ^ 2 элементов. Если у вас есть 100 словарей по одному элементу (1 ключ: пара), то каждый словарь будет выделяться только 1 ^ 2 (иначе лишнее распределение)?

Любая четко изложенная информация будет очень полезна!

Answer 1

Три предложения:

1. Используйте один словарь.
   Это проще, проще и кто-то другой уже оптимизировал эту проблему для вас. Пока вы на самом деле не измерили свой код и не отследили проблему с производительностью этой части, у вас нет причин не делать простую и понятную вещь.

2. Оптимизация позже.
   Если вы действительно беспокоитесь о производительности, то абстрагируйте проблему, заставив класс обернуть любой механизм поиска, который вы в итоге использовали, и напишите свой код для использования этого класса. Вы можете изменить реализацию позже, если вам понадобится какая-то другая структура данных для повышения производительности.

3. Читать на хеш-таблицах.
   Словари - это хеш-таблицы , и, если вас беспокоит их время или пространство, вы должны прочитать о том, как они реализованы. Это базовая информатика. Суть в том, что хеш-таблицы:

   • средний регистр O (1) время поиска
   • O (n) пробел (ожидается около 2n , в зависимости от различных параметров)

   Я не знаю, где вы читали, что они были O (n ^ 2) пробелом, но если бы они были, то они бы не получили широкого практического использования, как в большинстве современных языков. У этих замечательных свойств хеш-таблиц есть два преимущества:

   1. O (1) время поиска подразумевает, что вы не будете платить время поиска за больший словарь, так как время поиска не зависит от размера.
   2. O (n) пробел означает, что вы ничего не получите от разбиения словаря на более мелкие части. Пространство масштабируется линейно с количеством элементов, поэтому множество небольших словарей не займет значительно меньше места, чем один большой или наоборот. Это не было бы правдой, если бы они были O (n ^ 2) пробел, но, к счастью для вас, это не так.

   Вот еще несколько ресурсов, которые могут помочь:

   • Статья Википедии о хеш-таблицах дает большой список различных схем поиска и распределения, используемых в хеш-таблицах.
   • Документация GNU Scheme содержит хорошее обсуждение того, сколько места можно ожидать для хеш-таблиц, включая формальное обсуждение того, почему "объем пространства, используемого хеш-таблицей, пропорционален на количество ассоциаций в таблице ". Это может вас заинтересовать.

   Вот несколько вещей, которые вы могли бы рассмотреть, если вам действительно нужно оптимизировать реализацию словаря:

   • Вот исходный код C для словарей Python, если вы хотите ВСЕ детали. Здесь есть много документации:
     • dictobject.h
     • dictobject.c
   • Вот реализация Python этого, на случай, если вам не нравится читать C.
     (Спасибо Бену Петерсону )
   • Документы Java Hashtable немного рассказывают о том, как работают коэффициенты загрузки и как они влияют на пространство, занимаемое вашим хешем. Обратите внимание, что существует компромисс между вашим коэффициентом загрузки и частотой перефразирования . Перефразирование может быть дорогостоящим.

Answer 2

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

Это отдает преждевременной оптимизацией, а не улучшением производительности. Профилируйте свой код, если что-то на самом деле является узким местом, но до тех пор просто позвольте Python делать то, что он делает, и сосредоточиться на реальной задаче программирования, а не на основной механике.

Answer 3

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

Подумайте, "Самый простой способ справиться с этим", оптимизируйте намного позже.

Answer 4

Преждевременная оптимизация, бла-бла, не делайте этого, бла-бла.

Я думаю, вы ошибаетесь из-за мощности двух дополнительных распределений. Я думаю, это просто множитель из двух. х * 2, а не х ^ 2.

Я видел этот вопрос несколько раз в различных списках рассылки python.

Что касается памяти, вот перефразированная версия одного такого обсуждения (в рассматриваемом посте требовалось хранить сотни миллионов целых чисел):

1. Функция set () более компактна, чем dict (), если вы просто хотите проверить членство
2. gmpy имеет класс типа bitvector для хранения плотных наборов целых чисел
3. Точки хранятся на 50–30% пустыми, а запись составляет около ~ 12 байт (хотя истинное количество будет немного различаться в зависимости от платформы).

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

Как и другие, сказал, профиль, чтобы увидеть ваши узкие места. Сохранение членства set () и значения dict () может быть быстрее, но вы будете использовать больше памяти.

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

Answer 5

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

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

Он также обеспечивает транзакции и управление версиями.

Answer 6

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

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

Answer 7

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

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

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

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