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

Question

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

Answer 1

Оформить заказ ВремяСложность страница в вики-странице py dot org.Он охватывает set/dicts/lists/etc, по крайней мере, с точки зрения временной сложности.

Answer 2

Рэймонд Д.Хеттингер делает отличный разговор (слайды) о встроенных коллекциях 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;В основном это обозначение эффективности использования времени, а не большого количества памяти.