Размер словаря уменьшается при увеличении одного элемента

Ответ 1

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

Реализация Python 2.7 на CPython в четыре раза увеличивает объем памяти, выделяемой хэш-таблице каждый раз, когда она заполняет до 2/3 своей емкости, но сокращает ее, если у нее слишком много выделенной памяти (т.е. Большой непрерывный блок памяти был выделено, но только несколько адресов были использованы).

Так уж получилось, что словари, содержащие от 8 до 11 элементов, выделяют CPython достаточно памяти, чтобы считать их "перераспределенными" и сокращаться.

Ответ 2

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

TL;DR: это связано с арифметикой изменения размера. Каждое изменение размера выделяет 2**i памяти, где 2**i > requested_size; 2**i >= 8 2**i > requested_size; 2**i >= 8, но затем каждая вставка изменяет размер базовой таблицы дальше, если заполнено 2/3 слотов, но на этот раз new_size = old_size * 4. Таким образом, ваш первый словарь заканчивается 32 ячейками, а второй - всего 16 (так как он имеет больший начальный размер заранее).

Ответ: Как отметил @snakecharmerb в комментариях, это зависит от того, как создается словарь. Для краткости позвольте мне сослаться на это отличное сообщение в блоге, в котором объясняются различия между конструктором dict() и литералом dict {} как на уровне реализации байт-кода Python, так и на уровне CPython.

Давайте начнем с магического числа 8 клавиш. Это константа, предопределенная для реализации Python 2.7 в файле заголовков dictobject.h - минимальный размер словаря Python:

/* PyDict_MINSIZE is the minimum size of a dictionary.  This many slots are
 * allocated directly in the dict object (in the ma_smalltable member).
 * It must be a power of 2, and at least 4.  8 allows dicts with no more
 * than 5 active entries to live in ma_smalltable (and so avoid an
 * additional malloc); instrumentation suggested this suffices for the
 * majority of dicts (consisting mostly of usually-small instance dicts and
 * usually-small dicts created to pass keyword arguments).
 */
#define PyDict_MINSIZE 8

Как таковой, он может отличаться между конкретными реализациями Python, но давайте предположим, что мы все используем одну и ту же версию CPython. Тем не менее, размер 8, как ожидается, будет аккуратно содержать только 5 элементов; не беспокойтесь об этом, так как эта конкретная оптимизация не так важна для нас, как кажется.

Теперь, когда вы создаете словарь с использованием dict literal {}, CPython использует ярлык (по сравнению с явным созданием при вызове конструктора dict). Немного упрощая, операция байт-кода BUILD_MAP разрешается, и в результате вызывается функция _PyDict_NewPresized которая создаст словарь, для которого мы уже знаем размер заранее:

/* Create a new dictionary pre-sized to hold an estimated number of elements.
   Underestimates are okay because the dictionary will resize as necessary.
   Overestimates just mean the dictionary will be more sparse than usual.
*/

PyObject *
_PyDict_NewPresized(Py_ssize_t minused)
{
    PyObject *op = PyDict_New();

    if (minused>5 && op != NULL && dictresize((PyDictObject *)op, minused) == -1) {
        Py_DECREF(op);
        return NULL;
    }
    return op;
}

Эта функция вызывает нормальный конструктор dict (PyDict_New) и запрашивает изменение размера вновь созданного dict - но только если ожидается, что он будет содержать более 5 элементов. Это связано с оптимизацией, которая позволяет Python ускорить некоторые вещи, удерживая данные в заранее выделенной "smalltable", без вызова дорогостоящих функций выделения памяти и выделения памяти.

Затем dictresize попытается определить минимальный размер нового словаря. Он также будет использовать магическое число 8 - в качестве отправной точки и многократно умножать на 2, пока не найдет минимальный размер, превышающий запрошенный размер. Для первого словаря это просто 8, а для второго (и всех словарей, созданных с помощью dict literal с менее чем 15 ключами) - 16.

Теперь в функции dictresize есть специальный случай для первого, меньший new_size == 8, который предназначен для продвижения вышеупомянутой оптимизации (использование "маленькой таблицы" для сокращения операций манипулирования памятью). Однако, поскольку нет необходимости изменять размер вновь созданного dict (например, пока не было удалено ни одного элемента, поэтому таблица "чиста"), на самом деле ничего не происходит.

Напротив, когда new_size != 8, следует обычная процедура перераспределения хеш-таблицы. Это заканчивается тем, что для хранения "большого" словаря выделяется новая таблица. Хотя это интуитивно понятно (чем больше диктат получил большую таблицу), тем не менее это еще не продвигает нас к наблюдаемому поведению - но, пожалуйста, потерпите меня еще один момент.

Как только у нас есть предварительно выделенный dict, optcodes STORE_MAP сообщают интерпретатору вставлять последовательные пары ключ-значение. Это реализуется с dict_set_item_by_hash_or_entry функции dict_set_item_by_hash_or_entry, которая - что важно - изменяет размер словаря после каждого увеличения размера (т.е. успешной вставки), если более 2/3 слотов уже использовано. Размер увеличится в 4 раза (в нашем случае для больших диктов только в 2 раза).

Итак, вот что происходит, когда вы создаете дикт из 7 элементов:

# note 2/3 = 0.(6)
BUILD_MAP   # initial_size = 8, filled = 0
STORE_MAP   # 'key_1' ratio_filled = 1/8 = 0.125, not resizing
STORE_MAP   # 'key_2' ratio_filled = 2/8 = 0.250, not resizing
STORE_MAP   # 'key_3' ratio_filled = 3/8 = 0.375, not resizing
STORE_MAP   # 'key_4' ratio_filled = 4/8 = 0.500, not resizing
STORE_MAP   # 'key_5' ratio_filled = 5/8 = 0.625, not resizing
STORE_MAP   # 'key_6' ratio_filled = 6/8 = 0.750, RESIZING! new_size = 8*4 = 32
STORE_MAP   # 'key_7' ratio_filled = 7/32 = 0.21875

И в результате получается хэш-таблица с общим размером 32 элемента.

Однако при добавлении восьми элементов начальный размер будет в два раза больше (16), поэтому мы никогда не ratio_filled > 2/3 размер, так как условие ratio_filled > 2/3 никогда не будет выполнено!

И поэтому во втором случае вы получите меньший стол.

Ответ 3

Вы не делаете ничего плохого. Размер словаря не совсем соответствует количеству элементов, так как словари перераспределяются и динамически изменяются в размерах, когда используется определенный процент их пространства памяти. Я не уверен, что делает DICT меньше в 2,7 (а не в 3) в вашем примере, но вам не нужно об этом беспокоиться. Почему вы используете 2.7 и почему вы хотите знать точное использование памяти dict (кстати, в нее не входит память, используемая переменными, содержащимися в словаре, так как сам словарь заполнен указателями).

Ответ 4

Вы на самом деле не делаете ничего плохого. getsizeof получает не размер элементов внутри словаря, а приблизительную оценку словаря. Альтернативный способ решения этой проблемы - json.dumps() из библиотеки json. Хотя он не дает вам фактический размер объекта, он согласуется с изменениями, которые вы вносите в объект.

Вот пример

import sys
import json


diii = {'key1':1,'key2':2,'key3':1,'key4':2,'key5':1,'key6':2,'key7':1}
print sys.getsizeof(json.dumps(diii)) # <----

diii = {'key1':1,'key2':2,'key3':1,'key4':2,'key5':1,'key6':2,'key7':1,'key8':2}
print sys.getsizeof(json.dumps(diii)) # <----

json.dumps() изменяет словарь в строку json, тогда diii может оцениваться как строка. Подробнее о библиотеке Python json читайте здесь