Где я могу найти временную и пространственную сложность встроенных типов последовательностей в Python?
-
09-06-2019 - |
Вопрос
Мне не удалось найти источник этой информации, мне пришлось самому просмотреть исходный код Python, чтобы определить, как работают объекты.Кто-нибудь знает, где я могу найти это в Интернете?
Решение
Оформить заказ ВремяСложность страница в вики-странице py dot org.Он охватывает set/dicts/lists/etc, по крайней мере, с точки зрения временной сложности.
Другие советы
Рэймонд Д.Хеттингер делает отличный разговор (слайды) о встроенных коллекциях 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
дешево.
Если вы спрашиваете то, о чем, по моему мнению, вы спрашиваете, вы можете их найти. Здесь...стр. 476 и далее.
Он написан вокруг методов оптимизации Python;В основном это обозначение эффективности использования времени, а не большого количества памяти.