Какова сложность операции добавления элемента в список?

Чтобы ответить на этот вопрос, нужно разобраться, как списки устроены на низком уровне. Определение списка в исходниках CPython выглядит так:

typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;

Здесь ob_item -- это непрерывный массив указателей на элементы списка, а allocated содержит длину массива. Вот и все, что нужно знать, чтобы отвечать на вопросы о сложности операций со списками.

Во-первых, отсюда сразу видно, что получить длину массива можно очень быстро, за O(1), потому что не нужно пересчитывать все элементы.

len(a) # O(1)

Ещё сразу понятно, что при такой реализации стоимость индексирования не зависит от длины списка или значения индекса, так как изменить значение по известному номеру ячейки тоже можно тоже за O(1).

a[10] = 5 # O(1)

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

5 in a # O(n)

Добавление одиночных элементов в конец списка (метод append()) в большинстве случаев работает за O(1). Но здесь есть одна деталь: место в памяти для массива указателей аллоцируется заранее. И когда занятый объем памяти истощается, интерпретатор выделяет ещё примерно 15% от объема массива. Эта периодическая экспансия время от времени несколько замедляет добавление новых элементов в список, поэтому об O(1) можно говорить условно.

a.append(5) # ~O(1)

Еще одна распространенная потребность это конкатенировать списки, например, с помощью оператора +. Сложность конкатенации линейно зависит от длины присоединяемого списка: если его длина 100 элементов, то нужно 100 раз добавить в конец новый элемент.

a + b # ~O(k)

Чтобы получить доступ к элементам слайса a[i:j], нужно итерироваться между индексами i и j. Поэтому сложность такой операции O(k), где k -- длина слайса. А вот удалить слайс это O(n), из-за необходимости сдвинуть все следующие за удаленным участком элементы на новые места, здесь n -- длина всего массива.

a[i:j] # ~O(k)
del a[i:j] # ~O(n)

Метод, который получает и удаляет последний элемента списка pop(), имеет сложность O(1), в то время как pop(i) элемента из середины списка требует O(n). Почему так? Потому что после того, как один указатель был удален из середины или начала, нужно передвинуть все следующие за ним на 1 позицию вперёд. А когда элемент был удален из конца массива, этого делать не нужно. По этой же причине введение или элемента в середину списка тоже дорогая операция и требует O(n) операций.

a.pop() #O(1)
a.pop(i) #O(n)
a.insert(i, item) #O(n)

Обобщим:

Операция Сложность
----------------------
len(a) O(1)
a[i] O(1)
a[10] = 5 O(1)
5 in a O(n)
a.append(5) ~O(1)
a + b O(k)
a[i:j] O(k)
del a[i:j] O(n)
a.pop() O(1)
a.pop(i) O(n)
a.insert(i, item) O(n)

В общем, чтобы отвечать на вопросы о сложности операций со списками, нужно понимать, как они устроены на низком уровне. Самые дорогие операции -- те, которые требуют обхода части или всего списка, например, поиск значения в списке, конкатенация, слайсинг, удаление или добавление элементов в начало списка. Самые экономные операции -- получение длины списка, операции с элементами в конце списка и со значениями по известному индексу.

В общем случае, сложность добавления элемента в список зависит от того, в середину массива мы добавляем элемент или в конец. Добавить элемент в начало или середину списка это O(n), но операция append() требует только O(1)🐍

#перед_собесом #low_level #типы_данных #списки #алгоритмы #сложность #hardcore

Кеширование небольших чисел в CPython

Поговорим о небольших числах в CPython. Возьмем, например, два числа, 10 и 300:

 
>>> a = 10
>>> b = 300
>>> a is 10
True
>>> b is 300
False

Что?! Почему a указыввет на свое значение, а b y нет?

Все дело в том, что интерпретатор хранит числа в диапазоне от - 5 до 256 в специальном массиве. Поэтому когда мы пишем x = 10, то вообще-то получаем ссылку на объект, который уже существует в памяти:

 
>>> c = 1
>>> id(1)
94492411548416
>>> id(c)
94492411548416

Причем это касается любых значений, которые приводятся к целым числам этого диапазона. Можно завести число хоть в двоичном виде, хоть в hex, кеширование все равно будет работать:

 
>>> id(19)
94579033949504
>>> id(0b10011)
94579033949504
>>> id(0o23)
94579033949504
>>> id(0x13)
94579033949504

Числа вне диапазона - 5, 256 интерпретатор тоже будет пытаться оптимизировать, но только если они находятся в одной строке (или одном файле). В командной строке интерпретатора так не работает:

 
>>> d = 400
>>> d is 400
False

а так будет:

 
>>> e = 500; f = 500 
>>> e is f 
True

В общем и целом то, что нужно запомнить -- это что небольшие числа в интерпретаторе хранятся не так, как большие и что с ними следует пользоваться оператором ==, а не is.

И это снова не фича, а деталь реализации для экономии ресурсов. А пишу я об этом, потому что на задачу с кешем наткнулась на собеседовании, и собеседующий удивился, что я в курсе. Сказал, что узнал об этой особенности, когда начал сам проводить собеседования. Теперь это знаете и вы 🐍

#кеш #детали_реализации #low_level #identity_vs_equality