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

Question

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

Answer 1

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

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; Это в основном Big-O обозначение эффективности времени, а не много памяти.