Почему len(list) имеет временную сложность O(1)? – Погружение в CPython
Я столкнулся с простой задачей поиска дубликатов в списке, и хотя решений было много (оптимизированных и неоптимизированных), два из них привлекли мое внимание. Первое заключалось в итерации по списку с добавлением каждого элемента в набор. Перед добавлением проверялось, присутствует ли уже данный элемент в наборе, и если да, то получался ответ. Конечно, при таком решении мы должны были выполнять итерацию по списку, и в худшем случае пришлось бы просматривать весь список.
def containsDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
uniqueSet = set()
for i in nums:
if i in uniqueSet:
return True
else:
uniqueSet.add(i)
return False
Тогда наше решение будет зависеть от размера списка: O(n). n – количество элементов в списке. В другом решении мы просто сравниваем длину множества списка и длину списка.
len(set(list_name)) == len(list_name)
Учитывая природу множества, которое не может содержать дубликатов, это было бы простым решением. Нам необходимо обратить внимание на функцию len(), которая использовалась для определения длины списка. Эта встроенная функция не зависит от размера списка. Независимо от того, содержит ли ваш список 1 элемент или 1000, согласно стандартной реализации Python (CPython), временная сложность равна O(1).
За счет чего это возможно? Почему время, затрачиваемое на определение длины списка с несколькими элементами и списка с тысячами элементов, должно быть одинаковым? Так началось мое путешествие в кроличью нору CPython и выход из нее.
Для тех, кто не хочет углубляться, ответ на этот вопрос будет следующим:
len() – это встроенная и часто используемая операция, и вместо того, чтобы обходить весь список при каждом ее вызове, Python просто сохраняет и обновляет “количество элементов” (длину) каждой последовательности как часть структуры данных последовательности.
Согласно документации Python, функция len() выполняет следующие действия:
Возвращает длину (количество элементов) объекта. В качестве аргумента может выступать последовательность (например, строка, байт, кортеж, список или диапазон) или коллекция (например, словарь, набор или замороженный набор).
Сказанное выше – все, что нужно для понимания вопроса, вынесенного в заголовок этой статьи. Если же любопытство заставляет вас не останавливаться на достигнутом, давайте копнем глубже…
Прежде чем перейти к рассмотрению CPython, мы должны знать, что он собой представляет. Cpython – это реализация Python по умолчанию. Реализация – это то, что делает возможным процесс преобразования кода Python в машинный код.
pythoncode --compiler--> bytecode --interpreter(VM)--> machinecode
Когда вы пишете исходный код (.py), он сначала компилируется в байткод. Это промежуточный этап, после чего байткод (.pyc) интерпретируется виртуальной машиной в машинный код. Реализация CPython компилирует исходный код в байткод, который не зависит от архитектуры, на которой он будет выполняться. Затем этот байт-код интерпретируется с помощью ВМ на базе CPython в исполняемый машинный код.
В cpython каждый раз, когда вызывается функция len(), у нас есть функция builtin_len, вызываемая в cpython.
/*
len as builtin_len
obj: object
/
Return the number of items in a container.*/
static PyObject *
builtin_len(PyObject *module, PyObject *obj)
{
Py_ssize_t res;
res = PyObject_Size(obj);
if (res < 0) {
assert(PyErr_Occurred());
return NULL;
}
return PyLong_FromSsize_t(res);
}
Прежде чем перейти к рассмотрению функции builtin_len, давайте разберемся, что такое PyObject. Всякий раз, когда мы создаем объект или переменную в Python, будь то встроенный тип, например int, list, dictionary, или объект пользовательского класса, в памяти он представляется в виде PyObject, который, по сути, является структурой c.
typedef struct {
Py_ssize_t ob_refcnt; /* object reference count */
PyTypeObject* ob_type; /* object type */
};
Первый атрибут в структуре PyObject – счетчик ссылок на объект – используется для сбора мусора. Это знаковое целое число, которое используется для хранения количества ссылок на объект. При создании объекта имеется одна ссылка, и она может увеличиваться или уменьшаться. Если и когда количество ссылок достигает нуля, память деаллоцируется. Второй атрибут PyObject, тип объекта, является указателем типа объекта: будь то int, список или объект пользовательского класса.
Основную работу в функции builtin_len выполняет функция PyObject_Size(). Остальное – это проверка, не является ли возвращаемое из PyObject_Size значение отрицательным (что должно приводить к ошибке), и возврат длины путем преобразования из Py_ssize_t (знаковое целое число в c) в Pylong, которое является целым числом Python.
Py_ssize_t
PyObject_Size(PyObject *o)
{
if (o == NULL) {
null_error();
return -1;
}
PySequenceMethods *m = Py_TYPE(o)->tp_as_sequence;
if (m && m->sq_length) {
Py_ssize_t len = m->sq_length(o);
assert(_Py_CheckSlotResult(o, "__len__", len >= 0));
return len;
}
return PyMapping_Size(o);
}
Функция PyObject_Size(), используемая в функции builtin_len(), получает тип объекта, tp_as_sequence и sq_length. Два последних значения не должны быть равны null, если мы имеем дело с объектом типа list или tuple, т.е. с последовательностью. После этого будет возвращена длина. Если один из них равен null, то это означает, что мы имеем объект типа mapping, т.е. словарь. В этом случае будет вызвана функция PyMapping_Size(), которая соответственно вернет длину отображения.
Таким образом, при работе со списками или другими последовательностями реализация CPython гарантирует, что длина объекта или количество элементов хранится и готова к получению в любой момент, независимо от размера объекта, что обеспечивает временную сложность функции len(), равную O(1).