a = [1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
a.append(6)
[1, 2, 3, 4, 5, 6]
a.pop()
[1, 2, 3, 4, 5]
В данном случае хвост - это цифра "5", голова - "1". Списки в python являются изменяемой последовательностью, реализованной в виде стека (последний зашел, первый вышел). Вы можете добавить элемент в "хвост" списка (метод append), либо удалить хвостовой элемент (метод pop). Список также может быть использован в качестве очереди (первый зашел, первый вышел). Вы можете добавлять элементы к "концу", и удалять из "головы", однако это является не эффективным методом из-за того, что при удалении из "головы" потребуется сдвинуть все элементы на одну позицию.
На самом низком уровне списки представлены в виде массива, в ячейках которого хранятся ссылки на объекты в памяти.
Из-за этого списки имею некоторые особенности:
Временная сложность операций:
Вставка элемента в "голову" | O(n) | insert(i, x) |
Вставка элемента в "хвост" | O(1) | append(x) |
Удаление элемента из "головы" | O(n) | pop(i) |
Удаление элемента из "хвоста" | O(1) | pop |
Проход по списку | O(n) | for val in list |
Получение элемента по индексу | O(1) | list[i] |
Получение длины последовательности | O(1) | len(list) |
Присвоение значения по индексу | O(1) | list[i]=1 |
Кортеж является неизменяемым типом данных. Это значит, что после инициализации объекта, его нельзя модифицировать, однако в качестве элементов могут быть изменяемые типы данных. Помимо того, что кортежи ведут себя как последовательности, они являются объектами с неименованными полями. Об этой их особенности очень часто забывают. Аналогично списку, на самом низком уровне кортежи представлены в виде массива. Из-за этого кортежи очень похожи на списки и имеют близкую к ним временную сложность операций. Вместе с тем, имеются некоторые отличия, связанные в первую очередь с тем, что кортежи неизменяемы.
При попытке присвоить значение по индексу возникнет ошибка
t = (1, 2)
t[0] = 3
TypeError: 'tuple' object does not support item assignment
Однако допустимо следующее
t = ([1, 2], 3)
t[0].append(3)
print(t)
([1, 2, 3], 3)
l_1 = [1]
l_2 = list(l_1)
print(f"{id(l_1) == id(l_2)}")
t_1 = (1,)
t_2 = tuple(t_1)
print(f"{id(t_1) == id(t_2)}")
False
True
l_1 = [1, 2, 3, 4, 5]
print(f"{l_1.__sizeof__()}")
t_1 = (1, 2, 3, 4, 5)
print(f"{t_1.__sizeof__()}")
80
64
Множество – это неупорядоченная, изменяемая последовательность уникальных элементов. Отличительной особенностью множества являются математические операции над ними: объединение, пересечение, разность и симметрическая разность. Помимо уникальности, все объекты множества должны быть хешируемыми (Примечание: т.е. иметь функции __hash__ для вычисления хэша и __eq__ или __cmp__ для сравнения объектов между собой).
На самом низком уровне множества представлены в виде хеш таблицы. Из-за этого множества имею некоторые особенности:
l_1 = [1, 2, 3, 4, 5]
print(f"{l_1.__sizeof__()}")
s_1 = {1, 2, 3, 4, 5}
print(f"{s_1.__sizeof__()}")
80
712
Временная сложность операций:
Вставка элемента | O(1) | add |
Удаление элемента | O(1) | remove |
Проход по множеству | O(n) | for val in set |
Вхождение элемента | O(1) | val in set |
Получение длины последовательности | O(1) | len(set) |
Пересечение
a = { 1, 2, 3 }
b = { 2, 3, 4}
c = a & b
{2, 3}
Объединение
a = { 1, 2, 3 }
b = { 2, 3, 4}
c = a | b
{1, 2, 3, 4}
Симметрическая разность
a = { 1, 2, 3 }
b = { 2, 3, 4}
c = a ^ b
{1, 4}
Разность
a = { 1, 2, 3 }
b = { 3, 4 }
c = a - b
{1, 2}
Неизменяемые множества – это множества, которые не поддерживают изменения коллекции элементов, т.е. не имеют методов add и remove. Сам по себе объект set не хешируемый, а это значит, что данные последовательности не могут содержать в качестве элемента вложенное множество. В противоположность этому объект frozenset является хешируемым, а значит может быть включен в множество:
fs_1 = frozenset([1.1, 1.2, 1.3])
s_1 = {fs_1, 2, 3, 4, 5}
print(s_1)
{2, 3, 4, 5, frozenset({1.1, 1.3, 1.2})}
В отличае от списков, set и frozenset занимают одинаковый размер памяти
fs_1 = frozenset([1.1, 1.2, 1.3])
s_1 = set([1.1, 1.2, 1.3])
print(f"{fs_1.__sizeof__()}")
print(f"{s_1.__sizeof__()}")
200
200
Словарь – это изменяемая последовательность элементов, содержащих в себе ключ и сами данные. Если в списках и кортежах мы могли взять значение по индексу, то в словарях используется ключ. Объект dict не хешируемый, однако в качестве ключей можно использовать только хешируемые типы данных. Это связанно с тем, что, как и множества, словари основаны на хеш таблицах.
Временная сложность операций:
Вставка элемента | O(1) | add |
Удаление элемента | O(1) | remove |
Проход по словарю | O(n) | for val in dict |
Вхождение элемента | O(1) | val in dict |
Получение длины последовательности | O(1) | len(dict) |
Взятие элемента по ключу | O(1) | dict["key"] |
Класс, который располагается в модуле collections.
Двусторонняя очередь является обобщением стеков и очередей. Эта последовательность позволяет эффективно добавлять элементы как в конец, так и в начало с временной сложностью O(1). Добавление в середину работает уже не так эффективно. Этот контейнер реализован в виде двусвязного списка. Это означает, что каждый элемент помимо самих данных хранит ссылки на следующий и предыдущий объект в памяти. Отсюда следует, что добавление и удаление элементов не влечет смещение остальных объектов, как это было в случае со списком.
Двусторонняя очередь отлично подходит тогда, когда вам требуется последовательно читать элементы контейнера. Если необходимо получать доступ к случайному элементу последовательности, то следует использовать списки. Представим очередь с 10 элементами. Просто извлечь значение четвертого элемента мы не сможем, потому что не знаем, по какому адресу оно находится. Потребуется последовательно пройти от первого до четвертого элемента, используя ссылки. Поэтому временная сложность доступа по индексу(кроме первого и последнего, там O(1)) к элементу объекта deque равна O(n).
Объект deque имеет атрибут maxlen, который позволяет ограничить размер последовательности. В случае если он не задан, контейнер может иметь любую длину. В противном случае, размер очереди ограничен. При достижении максимального значения maxlen, добавление элемента вызовет отбрасывание другого элемента с противоположного конца.
Временная сложность операций:
Вставка элемента в "голову" | O(1) | appendleft(x) |
Вставка элемента в "хвост" | O(1) | append(x) |
Удаление элемента из "головы" | O(1) | popleft |
Удаление элемента из "хвоста" | O(1) | pop |
Проход по списку | O(n) | for val in deque |
Получение элемента по индексу | O(n) | deque[i] |
Получение длины последовательности | O(1) | len(deque) |
Присвоение значения по индексу | O(n) | deque[i]=1 |