Действительно ли возможно дать Python dict начальная способность (и действительно ли это полезно),
Я заполняю Python dict приблизительно 10 000 000 объектов. Мое понимание dict (или хеш-таблицы) то, что, когда слишком много элементы входят в них, потребность изменить размер, операция, которые стоят некоторого времени.
Существует ли способ сказать Python dict хранение, по крайней мере, n объектов в нем так, чтобы он мог выделить память от запуска? Или разве эта оптимизация не принесет пользы к моей рабочей скорости?
(И не, я не проверил, что замедление моего маленького сценария из-за этого, я на самом деле не был бы теперь, как сделать это. Это - однако что-то, что я сделал бы в Java, установил бы начальную способность права HashSet),
1 ответ
Во-первых, до меня дошли слухи, что вы можете установить размер словаря при инициализации, но я никогда не видел документации или PEP, описывающих, как это делается.
Учитывая это, я провел анализ вашего количества элементов, описанный ниже. Хотя изменение размера словаря каждый раз может занять некоторое время, я бы рекомендовал двигаться дальше, не беспокоясь об этом, по крайней мере, пока вы не сможете проверить его производительность.
Два правила, которые волнуют нас при определении размера, - это количество элементов и коэффициент изменения размера. Словарь изменит свой размер, когда он будет заполнен на 2/3 при добавлении элемента, превышающего отметку 2/3. Ниже 50,000 элементов он увеличится в 4 раза, выше - в 2 раза. Используя вашу оценку в 10,000,000 элементов (между 2^23 и 2^24), ваш словарь изменит размер 15 раз (7 раз ниже 50k, 8 раз выше). Еще одно изменение размера произойдет сразу после 11 100 000.
Изменение размера и замена текущих элементов в хэш-таблице действительно занимает некоторое время, но мне интересно, заметите ли вы это на фоне всего остального, что происходит в коде поблизости. Я только что собрал набор временных параметров, сравнивая вставки в пяти местах вдоль каждой границы словаря размером от 2^3 до 2^24, и "пограничные" добавления в среднем на 0.4 наносекунды дольше, чем "не пограничные". Это на 0,17% дольше... вероятно, приемлемо. Минимум для всех операций составил 0,2085 микросекунды, а максимум - 0,2412 микросекунды.
Надеюсь, это было познавательно, и если вы проверите производительность своего кода, пожалуйста, дополните его правкой! Моим основным источником информации о внутреннем устройстве словарей был великолепный доклад Брэндона Родса на PyCon 2010: The Mighty Dictionary