О коллекциях в python
Contents
О коллекциях в python#
Разнообразие коллекций#
В python в любой момент времени имеется доступ к нескольким видам коллекций, среди которых:
list — списки;
tuple — кортежи;
range — диапазоны;
str — строки;
bytearray и bytes — изменяемый и неизменяемый массивы байтов;
dict — словари (ассоциативные массивы, хеш таблицы).
Ещё больше коллекций доступно, если брать в расчет модули стандартной библиотеки:
array.array — массивы численных значений;
collections.deque — двухсторонняя очередь;
collections.OrderedDict — упорядоченный словарь;
collections.defaultdict — словарь, со значениями по-умолчанию;
и т.д.
А ещё ведь существуют разнообразные коллекции из сторонних библиотек. Может показаться, что познакомиться со всеми коллекциями в python — непосильная задача. Однако можно значительно упростить себе задачу, если выявить между некоторыми коллекциями сходства. Благо сам python выделяет среди коллекций некоторую иерархию, которая располагает все свои встроенные коллекции и многие сторонние по полочкам.
Базовые понятия#
Для начала введём три самых базовых понятия с точки зрения python, которые позволят четко сформулировать, что понимается под коллекцией в python.
Контейнер. Container#
Объект считается контейнером (Container), если у него можно спросить, содержит ли он какой-то произвольный элемент x (does it contain x?). Иными словами, если A контейнер, то для любого x следующее выражение должно вычисляться без ошибок и возвращать булевое значение.
x in A
Note
Строго говоря, тип считается контейнером, если у него перегружен метод __contains__, что и позволяет его использовать справа от ключевого слова in. Однако, если объект не является контейнером, но является итерируемым объектом, то этот объект все равно можно использовать справа от ключевого слова in. Такой объект, тем не менее, формально не считается контейнером.
Например, списки являются контейнерами.
print(0 in [1, 0, 2])
True
Tip
Тест на принадлежность списку работает очень медленно. В большинстве ситуаций, если требуется часто проверять наличие элемента в коллекции, быстрее всего отработают множества (set), которые используют хеш-таблицу для быстрого теста на принадлежность.
Итерируемый объект. Iterable#
Объект считается итерируемым (Iterable), если по нему можно пробежаться в цикле (iterate over). Т.е. A — итерируемый объект, если можно написать следующее выражение.
for x in A:
...
Из изученных на первом занятии типов, списки и диапазоны являются итерируемыми объектами, а числа — нет.
Многие python функции ожидают в качестве аргумента итерируемый объект, т.к. возможности пробежаться по элементам итерируемого объекта достаточно для выполнения большинства операций. Например, из итерируемого объекта можно создать список функцией list, к нему можно поэлементно применить функцию функцией map, отфильтровать значения функцией filter, а при выполнении требования на однородность элементов можно искать минимальное и максимальное значения функциями min и max, или получать упорядоченный список элементов функцией sorted.
Кроме этого, из итерируемости объекта следует, что его допустимо использовать справа от ключевого слова in: если python видит, что объект целенаправленно не реализует интерфейс контейнера, то при тесте на принадлежность python пытается воспользоваться итерируемостью объекта. Действительно, можно в цикле сравнить каждый элемент итерируемого объекта с запрашиваем значением, и если хоть один совпал, вернуть истину. Ниже приводится функция contains, иллюстрирующая данную идею.
def contains(element, iterable):
for x in iterable:
if x == element:
return True
return False
В настоящем коде достаточно написать element in iterable, а python сам сгенерирует схожий код.
Warning
Такой поиск является очень медленным: чтобы убедиться в отсутствии значения в итерируемом объекте, придется сравнить это значение с каждым элементов.
Объект ограниченной длины. Sized#
Объект считается объектом ограниченной длины (Sized), если у него можно спросить количество элементов (длина, размер, size) функцией len. Т.е. A — объект ограниченной длинны, если len(A) вычисляется без ошибок и возвращает целое неотрицательное число.
Все коллекции в python удовлетворяют этому свойству, поэтому функцию len можно использовать с любой из них.
print(len((1, 2, 3)))
print(len([1, 2, 3]))
print(len("abc"))
print(len(range(3)))
3
3
3
3
Пример: контейнер, но не итерируемый и без длины#
В качестве примера рассмотрим класс Interval, экземпляры которого должны репрезентировать в программе математические интервалы, т.е. множества вида \((a, b)=\{x\in\mathbb{R}\mid a<x<b\}\). Кроме наличия двух действительнозначных атрибутов a и b, отвечающих за границы интервала, логично для этого типа Interval перегрузить действие оператора in таким образом, чтобы оно проверяло вхождение числа слева от него в интервал справа от него.
Ниже приводится возможное определение класса Interval, удовлетворяющее обозначенным требованиям. Пока можете не обращать внимание на эту ячейку, объявление пользовательских классов будет обсуждаться значительно позже.
from collections.abc import Container
from dataclasses import dataclass
@dataclass
class Interval(Container):
a: float
b: float
def __contains__(self, x: float) -> bool:
return self.a < x < self.b
interval = Interval(0, 1)
print(interval)
Interval(a=0, b=1)
Помимо самого объявления нового типа Interval, в ячейке выше также создан один экземпляр interval с параметрами a=0 и b=1, который соответствует интервалу \((0, 1)\). Этот объект теперь можно использовать для определения принадлежности любого числа x интервалу \((0, 1)\) синтаксисом x in interval.
numbers = (-0.5, 0.5, 1.5)
for x in numbers:
contains = x in interval
print(f"{x=}: {contains=}")
x=-0.5: contains=False
x=0.5: contains=True
x=1.5: contains=False
С формальной точки зрения такой объект является контейнером. Теперь зададимся вопросами:
можно ли поставить в соответствие интервалу \((a, b)\) какое-то разумное значение длины?
можно ли в каком-то разумном порядке пробежаться по числам из интервала \((a, b)\)?
Ответ на первый вопрос — нет. Функция len должна возвращать неотрицательное целое число, т.к. её смысл — количество элементов. Известно, что в отрезке \((a, b)\) находится бесконечное количество точек, поэтому len не может возвращать количество точек внутри отрезка (значение +inf может принимать только float в python). Математическая длина отрезка \(b-a\) тоже не подходит, т.к. в общем случае эта величина является не целым числом (да и противоречило бы изначальному смыслу, вкладываемому в функцию len). В связи с этим разумно заключить, что Interval не является объектом ограниченной длины.
Ответ на второй вопрос — нет. Мало того, что внутри отрезка \((a, b)\) находится бесконечное множество чисел, так это множество ещё и не является счетным (более конкретно, оно является континуумом), что как раз и значит, что даже теоретически невозможно поставить в соответствие каждому числу из интервала \((a, b)\) уникальное натуральное число (его порядковый номер). В связи с этим разумно заключить, что Interval не является итерируемым объектом.
Итого, такой объект имеет все полномочия называться контейнером, но он не удовлетворяет определениям итерируемого объекта и объекта ограниченной длины.
from collections.abc import Container, Iterable, Sized
print(isinstance(interval, Container))
print(isinstance(interval, Iterable))
print(isinstance(interval, Sized))
True
False
False
Пример: итерируемый, но не контейнер и безграничный#
Забегая вперед, можно привести пример объекта, по которому можно пробежаться в цикле, но который не является контейнером и не имеет определенного размера. В python есть специальный тип генераторов, для создания которых даже предусмотрен свой специальный синтаксис (см. Генераторы).
Генераторы очень похожи на итераторы, но в отличии от них по-требованию выдают не существующие элементы какого-то итерируемого объекта, а вычисляют новые значения по заданному правилу. Одна из основных идей, скрывающихся за генераторами, заключается в экономии памяти: вместо одновременного хранения всех элементов последовательности в памяти, достаточно хранить только рецепт для вычисления каждого следующего.
В зависимости от того, какое правило использовалось при создании генератора, последовательность элементов, генерируемая им, может исчерпаться за конечное число шагов, а может длиться бесконечно.
Tip
Примером бесконечного генератора является itertools.count, который генерирует бесконечную арифметическую последовательность.
Внизу объявляется генератор generator (обратите на наличие ключевого слова yield), и демонстрируется, что по нему можно пробежаться в цикле.
def generator(n):
yield from range(n)
for i in generator(10):
print(i, end=" ")
0 1 2 3 4 5 6 7 8 9
При этом в общем случае невозможно автоматически заранее вычислить длину этой последовательности, хотя бы потому, что она может оказаться бесконечной. Поэтому генераторы не поддерживают вызов функции len, а значит не являются объектами ограниченной длины. Внизу демонстрируется этот факт.
len(generator(10))
---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
Cell In[8], line 1
----> 1 len(generator(10))
TypeError: object of type 'generator' has no len()
Проверить наличие элемента в генераторе, можно только воспользовавшись тем, что он итерируемый объект, т.к. в общем случае невозможно заранее предугадать будет ли такой элемент в генерируемой последовательности, особенно, если она бесконечная.
Однако такое поведение является побочным проявлением итерируемости генераторов, и используя генераторы в качестве контейнеров, можно наткнуться на неожиданные эффекты. Посмотрите на следующий пример, две последовательные проверки вхождений 0 в один и тот же объект генератора g дают разный ответ.
g = generator(10)
print(0 in g)
print(0 in g)
True
False
Кроме того, использование бесконечно генератора справа от ключевого слова in запустит бесконечный цикл. Ну и наконец, наиболее формальный ответ: у генераторов не перегружен метод __contains__, что отнимает у них право называться контейнером.
Итого, генераторы являются итерируемыми объектами, но не контейнерами и не объектами ограниченной длины.
from collections.abc import Container, Iterable, Sized
print(isinstance(g, Container))
print(isinstance(g, Iterable))
print(isinstance(g, Sized))
False
True
False
Коллекции#
Коллекция — объект, который одновременно является контейнером, итерируемым объектом и объектом ограниченный длинны.
С бытовой точки зрения, коллекция — нечто, хранящее в себе совокупность объектов.
Эта совокупность не может быть бесконечной, т.к. она физически хранится внутри коллекции, а значит должна быть ограниченного размера, т.е. допускает вызов функции
len.Т.к. эта совокупность ограничена, то мы всегда можем пробежаться по её элементам (например, в случайном порядке, хотя нередко этот порядок возникает естественным образом), а значит она должна являться итерируемым объектом.
Т.к. мы всегда можем пробежаться по её элементам, то мы всегда можем проверить наличия произвольного элемента в коллекции (например, просто сравнив каждый элемент коллекции на равенство в цикле), т.е. коллекция должна являться контейнером.
Разработчики языка python смотрят на эту иерархию понятий, как на иерархию классов, где абстрактный класс Collection наследуется от всех трех выше обозначенных абстрактных классов: Container, Iterable и Sized.
from collections.abc import Collection, Container, Iterable, Sized
print(issubclass(Collection, Container))
print(issubclass(Collection, Iterable))
print(issubclass(Collection, Sized))
True
True
True
Note
Более конкретно, каждый абстрактный класс в иерархии задаёт интерфейс: только объекты, удовлетворяющие заданному интерфейсу, можно считать экземплярами этого класса. Все производные классы тоже обязаны удовлетворять этому интерфейсу, а значит экземпляры класса Collection должны одновременно удовлетворять интерфейсам классов Container, Iterable и Sized.
Дальнейшее ветвление в иерархии#
Выше было перечисленно сравнительно большое количество объектов, являющихся коллекциями. Дальнейшая их классификация обычно производится по способу получения доступа к элементам. По такому принципу можно выделить два наиболее широких класса — последовательности (Sequence) и отображения (Mapping), хотя ещё существуют множества (Set) и другие.
from collections.abc import Collection, Sequence, Mapping
print(issubclass(Sequence, Collection))
print(issubclass(Mapping, Collection))
True
True
Про последовательности речь пойдет на следующей странице, а среди класса Mapping мы познакомимся только с одним представителем, но несколько позже (см. Словари. dict).