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

Ответ 1

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

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

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

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

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

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

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

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

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

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

Ответ 5

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

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

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

Ответ 6

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

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

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

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

Ответ 7

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

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