Python словарь итератор производительности

Question

При работе со словарями в Python this page говорит, что временная сложность итерации по элементу словаря составляет O(n), где n - самый большой размер словаря.

Однако, я не думаю, что существует очевидный способ итерации элементов хэш-таблицы. Могу ли я считать хорошую производительность dict.iteritems() при повторении элемента хэш-таблицы без лишних издержек?

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

Answer 1

Если вы посмотрите на notes on Python's dictionary source code, я думаю, что соответствующие пункты являются следующие:

Эти методы (итерации и ключ из списка) цикл по каждому потенциальному входу

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

Максимальная загрузка словаря в PyDict_SetItem. В настоящее время установлено 2/3

Темп роста при максимальной нагрузке. В настоящее время установлено значение * 2.

Это предполагает, что разреженность словаря будет где-то около 1/3 ~ 2/3 (если скорость роста не установлена ​​на * 4, то это 1/6 ~ 2/3). Таким образом, в основном вы будете проверять до 3 (или 6, если * 4) потенциальных записей для каждого ключа.

Конечно, будь то 3 записи или 1000, это все еще O (n), но 3 кажется довольно приемлемым постоянным фактором.

Кстати вот остальная часть документации источника &, что в DictObject в том числе:

http://svn.python.org/projects/python/trunk/Objects/