Почему обращение к элементам по индексу в Python работает быстро?

Обращение к элементам по индексу в списках (list) и кортежах (tuple) в Python работает быстро, так как эти структуры данных являются массивами с фиксированным размером элементов (или ссылок на элементы).

• Непрерывное размещение в памяти: Элементы списка или кортежа хранятся в непрерывном блоке памяти.
• Прямой доступ: Индекс элемента напрямую соответствует смещению от начала этого блока памяти.
• Вычисление адреса: Адрес нужного элемента вычисляется по формуле base_address + index * element_size, где base_address — адрес начала блока памяти, index — индекс элемента, element_size — размер одного элемента (или размер указателя на объект, если хранятся ссылки).
• Временная сложность: Такая операция индексации имеет временную сложность O(1), что означает, что время доступа не зависит от размера списка или кортежа.

Пример:

python

В отличие от списков и кортежей, доступ к элементам в структурах данных, основанных на связных списках или неструктурированных данных (например, множествам set или словарям dict по ключу), может занимать больше времени, так как требует либо обхода (связные списки), либо вычисления хеша и разрешения коллизий (словари).