Где я могу найти временную и пространственную сложность встроенных типов последовательностей в Python

Question

Мне не удалось найти источник этой информации, если не считать самого исходного кода Python, чтобы определить, как работают объекты. Кто-нибудь знает, где я мог найти это онлайн?

Answer 1

Оформить заказ на странице TimeComplexity на вики-сайте. Он охватывает набор /dicts/lists/ и т. Д., По крайней мере, с точки зрения сложности времени.

Answer 2

Раймонд Хеттингер (Raymond D. Hettinger) отлично рассказывает ( слайды) о встроенных коллекциях Python под названием "Базовые контейнеры Python - под капотом". Версия, которую я видел, была сосредоточена в основном на set а также dict, но list был накрыт тоже.

В блоге также есть несколько фотографий соответствующих слайдов от EuroPython.

Вот краткое изложение моих заметок на list:

• Хранит элементы в виде массива указателей. Индекс стоит O(1) времени. Прибавить затраты амортизированные O(1) раз. Вставка стоит O(n) раз.
• Пытается избежать memcpy когда растет путем перераспределения. Многие небольшие списки будут тратить много места, но большие списки никогда не тратят более чем 12,5% на перераспределение.
• Некоторые операции предварительно размера. Приведенные примеры были range(n), map(), list(), [None] * nи нарезка.
• При сжатии массив reallocРед, только когда он тратит 50% пространства. pop дешево.

Answer 3

Если вы спрашиваете, что я думаю, вы спрашиваете, вы можете найти их здесь... стр. 476 и далее.

Он написан на основе методов оптимизации для Python; Это в основном Big-O обозначение эффективности времени, а не много памяти.