Эффективность памяти: Один большой словарь или словарь меньших словарей?
Я думаю, что это связано с тем, что, когда сравнение «is» оценивается как false, используются два разных объекта. Если он оценивает значение true, это означает, что внутри он использует один и тот же точный объект, а не создает новый, возможно, потому, что вы создали их за долю в 2 или около того секунд и потому, что между ним нет большого промежутка времени и использует тот же объект.
Вот почему вы должны использовать оператор равенства ==, а не is, чтобы сравнить значение строкового объекта.
>>> s = 'one'
>>> s2 = 'two'
>>> s is s2
False
>>> s2 = s2.replace('two', 'one')
>>> s2
'one'
>>> s2 is s
False
>>>
В этом примере я сделал s2, который был другим строковым объектом, ранее равным «одному», но это не тот же объект, что и s, потому что интерпретатор не использовал тот же объект, что и я, один ', если бы я сделал это, это сделало бы их одним и тем же объектом.
7 ответов
Три предложения:
-
Использование один словарь.
Это легче, это более просто, и кто-то еще уже оптимизировал эту проблему для Вас. Пока Вы на самом деле не измерили свой код и проследили проблему производительности до этой части его, у Вас нет причины не сделать простую, простую вещь. -
Оптимизируют позже.
, Если Вы действительно взволнованы по поводу производительности, затем абстрагируйте проблему, делают класс для обертывания безотносительно механизма поиска, который Вы заканчиваете тем, что использовали и пишете свой код для использования этого класса. Можно изменить реализацию позже, если Вы находите необходимость в некоторой другой структуре данных для большей производительности. -
Read на хэш-таблицах.
Словари хэш-таблицы , и если Вы волнуетесь по поводу их времени или пространства наверху, необходимо читать о том, как они реализованы. Это - базовая информатика. За исключением него то, что хэш-таблицы:- средний случай O (1) время поиска
- O (n) пространство (Ожидают приблизительно [1 143] 2n , в зависимости от различных параметров)
я не знаю, где Вы читаете, что они были O (n^2) пространство, но если бы они были, тогда они не были бы в широко распространенном, практическом употреблении, как они находятся на большинстве языков сегодня. Существует два преимущества для этих хороших свойств хэш-таблиц:
- O (1) время поиска подразумевает, что Вы не оплатите стоимость во время поиска для того, чтобы иметь больший словарь, поскольку время поиска не зависит от размера.
- O (n) пространство подразумевает, что Вы не получаете большую часть ничего от разбивания Вашего словаря в мелкие кусочки. Пространство масштабируется линейно с числом элементов, таким образом, много маленьких словарей не поднимет значительно меньше пространства, чем одно большое или наоборот. Это не было бы верно, если бы они были O (n^2) пространство, но удачный для Вас, они не.
Вот еще некоторые ресурсы, которые могли бы помочь:
- статья Wikipedia о Хэш-таблицах дает большой список различных схем поиска и выделения, используемых в хеш-таблицах.
- документация Схемы GNU имеет хорошее обсуждение того, сколько пространства можно ожидать, что хеш-таблицы поднимут, включая формальное обсуждение того, почему "сумма пространства, использованного хэш-таблицей, пропорциональна числу ассоциаций в таблице" . Это могло бы заинтересовать Вас.
Вот некоторые вещи, которые Вы могли бы рассмотреть, находите ли Вы, что на самом деле необходимо оптимизировать реализацию словаря:
- Вот исходный код C для словарей Python, в случае, если Вы хотите Все подробности. Существует обильная документация в здесь:
- <литий> dictobject.h <литий> dictobject.c
- Вот реализация Python из этого, в случае, если Вам не нравится читать C.
(Благодаря Ben Peterson ) - документы класса Хеш-таблицы Java разговор немного о том, как работают коэффициенты загрузки, и как они влияют на пространство, которое поднимает Ваш хеш. Примечание там является компромиссом между Вашим коэффициентом загрузки и как часто Вам нужно к [1 114] рехеширование . Рехеширования могут быть дорогостоящими.
При использовании Python Вы действительно не должны волноваться об этом виде вещи во-первых. Просто создайте свою структуру данных путем, она лучше всего подходит Ваш потребности, не компьютер.
Это имеет привкус преждевременной оптимизации, не повышения производительности. Представьте свой код, если что-то - на самом деле сужение трубы, но до тех пор, просто позвольте Python сделать то, что это делает и фокусирует на фактической задаче программирования а не базовой механике.
"Простой" обычно лучше, чем "умный", особенно если у Вас нет протестированной причины пойти вне "простого". И так или иначе "Память, эффективная", является неоднозначным термином, и существуют компромиссы, когда Вы рассматриваете сохранение, сериализацию, cacheing, свопинг и целый набор другого материала, который кто-то еще уже продумал так, чтобы в большинстве случаев Вы не должны были.
Думают, "Самый простой способ обработать его правильно" оптимизирует намного позже.
Преждевременная оптимизация bla bla, не делайте этого bla bla.
я думаю, что Вы ошибаетесь о , питание из двух дополнительных выделений делает. Я думаю его просто множитель из два. x*2, не x^2.
я видел этот вопрос несколько раз в различных списках рассылки Python.
Относительно памяти, вот перефразируемая версия одного такого обсуждения (рассматриваемое сообщение хотело сохранить сотни миллионов целых чисел):
- набор А () является большим количеством пространства, эффективного, чем dict (), если Вы просто хотите протестировать на членство
- , gmpy имеет класс типа битовый вектора для хранения плотных наборов целых чисел
- , Dicts сохранены между 50% и пустыми 30%, и запись составляет приблизительно ~12 байтов (хотя истинная сумма будет варьироваться платформой немного).
Так, чем меньше объектов Вы имеете, тем меньшей памятью Вы собираетесь быть использование и меньшим количеством поисков, которые Вы собираетесь сделать (так как Вы будете иметь к поиску в индексе, затем второму поиску в фактическом значении).
Как другие, сказал, профиль для наблюдения узких мест. Хранение набора членства () и значение dict () могло бы быть быстрее, но Вы будете использовать больше памяти.
я также предложил бы повторно отправить это на Python определенный список, такой как comp.lang.python, который полон намного более хорошо осведомленных людей, чем я, кто дал бы Вам всем виды полезной информации.
Честно, Вы не будете в состоянии сказать различие так или иначе, или с точки зрения производительности или с точки зрения использования памяти. Если Вы не имеете дело с десятками миллионов объектов или больше, влияние производительности или памяти является просто шумом.
От пути Вы сформулировали свое второе предложение, он кажется, что один большой словарь является Вашим первым наклоном и соответствует более тесно проблеме, которую Вы пытаетесь решить. Если это правда, пойдите с этим. То, что Вы найдете о Python, - то, что решения, что все рассматривают 'право' почти всегда, оказываются теми, которые максимально ясны и просты.
Часто времена, словари словарей полезны для кроме причин производительности. т.е., они позволяют Вам хранить контекстную информацию о данных, не имея дополнительных полей на самих объектах и делать запросы подмножеств данных быстрее.
С точки зрения использования памяти, это выдержало бы обосновать, что один большой словарь будет использовать меньше поршня, чем несколько меньших. Помните, если Вы будете вложенными словарями, то каждый дополнительный слой вложения примерно удвоит количество словарей, которые необходимо выделить.
С точки зрения скорости запроса, несколько dicts займут больше времени из-за увеличенного числа требуемых поисков.
, Таким образом, я думаю, единственный способ ответить на этот вопрос состоит в том, чтобы Вы представили свой собственный код. Однако мое предложение состоит в том, чтобы использовать метод, который делает Ваш код самым чистым и самым легким для поддержания. Из всех функций Python словари, вероятно, наиболее в большой степени настроены для оптимальной производительности.
Если ваш словарь настолько большой, что не помещается в памяти, вы можете взглянуть на ZODB , очень зрелую объектную базу данных для Python.
«Корень» базы данных имеет тот же интерфейс, что и словарь, и вам не нужно загружать всю структуру данных сразу в память, например, вы можете перебирать только часть структуры, предоставляя ключи начала и конца.
Он также обеспечивает транзакции и управление версиями.