Вопрос по python, dictionary, capacity – Можно ли дать Python dict начальную емкость (и это полезно)

12

Я заполняю диктофон около 1000000 предметов. Мое понимание dict (или хеш-таблиц) состоит в том, что когда в них попадает слишком много элементов, необходимо изменить размер, операция, которая стоит довольно много времени.

Есть ли способ сказать диктону python, что вы будете хранить в нем как минимум n элементов, чтобы он мог выделять память с самого начала? Или эта оптимизация не поможет моей скорости бега?

(И нет, я не проверял, из-за этого медлительность моего маленького скрипта, на самом деле я бы сейчас не стал делать это. Однако это то, что я бы сделал в Java, установив правильную начальную емкость HashSet)

Не согласен с дубликатом. Диктовка - это не то же самое, что список. Peter Smit
возможный дубликатPython - создать список с начальной емкостью msw

Ваш Ответ

2   ответа
2

Да, вы можете, и вот решение, которое я нашел в вопросе другого человека, которое относится и к вашему:

d = {}
for i in xrange(4000000):
d[i] = None
# 722ms

d = dict(itertools.izip(xrange(4000000), itertools.repeat(None)))
# 634ms

dict.fromkeys(xrange(4000000))
# 558ms

s = set(xrange(4000000))
dict.fromkeys(s)
# Not including set construction 353ms

это разные способы инициализации словаря с определенным размером.

Если вы используете чужойответ, датьему кредит, особенно когда ответы лицензируются в соответствии сcc by-sa 3.0 сатрибуция требуется, Черт, ты мог бы воспроизвести эталон. Cristian Ciupitu
18

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

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

Два правила, которые нас интересуют при определении размера - это количество элементов и фактор изменения размера. Размер словаря изменится, когда он будет заполнен на 2/3 при добавлении элемента, поместив его над отметкой 2/3. Ниже 50 000 элементов он увеличится в 4 раза, выше этого показателя в 2 раза. Используя вашу оценку в 10 000 000 элементов (от 2 ^ 23 до 2 ^ 24), ваш словарь изменит свой размер в 15 раз (в 7 раз ниже 50k, 8 раз выше). Другое изменение произойдет чуть позже 11 10000.

Изменение размера и замена текущих элементов в хеш-таблице занимает некоторое время, но мне интересно, заметите ли вы это с тем, что у вас происходит в коде поблизости. Я просто собрал набор времени, сравнивающий вставки в пяти местах вдоль каждой границы с размерами словаря от 2 ^ 3 до 2 ^ 24, и добавления «границы» в среднем на 0,4 наносекунды длиннее, чем добавления «без границ». Это на 0,17% дольше ... вероятно, приемлемо. Минимум для всех операций составлял 0,20585 микросекунд, а максимальный - 0,2412 микросекунд.

Надеюсь, что это проницательно, и если вы проверите производительность своего кода, пожалуйста, внесите изменения! Моим основным ресурсом по внутренним компонентам словаря была прекрасная речь, произнесенная Брэндоном Роудсом на PyCon 2010:Могучий словарь

Ссылка снова работает. Celeo
Ссылка на The Mighty Dictionary теперь не работает (ссылка гниль) GUI Junkie

Похожие вопросы