О коллекциях в python #
В python в любой момент времени имеется доступ к нескольким видам коллекций, среди которых:
- list — списки;
- tuple — кортежи;
- range — диапазоны;
- str — строки;
- bytearray и bytes — изменяемый и неизменяемый массивы байтов;
- set и frozenset — изменяемые и неизменяемые множества;
- dict — словари (ассоциативные массивы, хеш таблицы).
Ещё больше коллекций доступно, если брать в расчет модули стандартной библиотеки:
- array.array — массивы численных значений;
- collections.deque — двухсторонняя очередь;
- collections.OrderedDict — упорядоченный словарь;
- collections.defaultdict — словарь, со значениями по-умолчанию;
- и т.д.
А ещё ведь существуют разнообразные коллекции из сторонних библиотек. Может показаться, что познакомиться со всеми коллекциями в python — непосильная задача. Однако можно значительно упростить себе задачу, если выявить между некоторыми коллекциями сходства. Благо сам python выделяет среди коллекций некоторую иерархию, которая располагает все свои встроенные коллекции и многие сторонние по полочкам.
Базовые понятия#
Для начала введём три самых базовых понятия с точки зрения python , которые позволят четко сформулировать, что понимается под коллекцией в python .
Контейнер. Container #
Объект считается контейнером ( Container ), если у него можно спросить, содержит ли он какой-то произвольный элемент x (does it contain x?). Иными словами, если A контейнер, то для любого x следующее выражение должно вычисляться без ошибок и возвращать булевое значение.
Строго говоря, тип считается контейнером, если у него перегружен метод __contains__ , что и позволяет его использовать справа от ключевого слова in . Однако, если объект не является контейнером, но является итерируемым объектом, то этот объект все равно можно использовать справа от ключевого слова in . Такой объект, тем не менее, формально не считается контейнером.
Например, списки являются контейнерами.
Тест на принадлежность списку работает очень медленно. В большинстве ситуаций, если требуется часто проверять наличие элемента в коллекции, быстрее всего отработают множества (set), которые используют хеш-таблицу для быстрого теста на принадлежность.
Итерируемый объект. Iterable #
Объект считается итерируемым ( Iterable ), если по нему можно пробежаться в цикле ( iterate over). Т.е. 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 сам сгенерирует схожий код.
Такой поиск является очень медленным: чтобы убедиться в отсутствии значения в итерируемом объекте, придется сравнить это значение с каждым элементов.
Объект ограниченной длины. 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)))
Пример: контейнер, но не итерируемый и без длины#
В качестве примера рассмотрим класс Interval , экземпляры которого должны репрезентировать в программе математические интервалы, т.е. множества вида \((a, b)=\
Ниже приводится возможное определение класса 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 , в ячейке выше также создан один экземпляр 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))
Пример: итерируемый, но не контейнер и безграничный#
Забегая вперед, можно привести пример объекта, по которому можно пробежаться в цикле, но который не является контейнером и не имеет определенного размера. В python есть специальный тип генераторов, для создания которых даже предусмотрен свой специальный синтаксис (см. Генераторы ).
Генераторы очень похожи на итераторы, но в отличии от них по-требованию выдают не существующие элементы какого-то итерируемого объекта, а вычисляют новые значения по заданному правилу. Одна из основных идей, скрывающихся за генераторами, заключается в экономии памяти: вместо одновременного хранения всех элементов последовательности в памяти, достаточно хранить только рецепт для вычисления каждого следующего.
В зависимости от того, какое правило использовалось при создании генератора, последовательность элементов, генерируемая им, может исчерпаться за конечное число шагов, а может длиться бесконечно.
Примером бесконечного генератора является itertools.count, который генерирует бесконечную арифметическую последовательность.
Внизу объявляется генератор generator (обратите на наличие ключевого слова yield ), и демонстрируется, что по нему можно пробежаться в цикле.
def generator(n): yield from range(n) for i in generator(10): print(i, end=" ")
При этом в общем случае невозможно автоматически заранее вычислить длину этой последовательности, хотя бы потому, что она может оказаться бесконечной. Поэтому генераторы не поддерживают вызов функции len , а значит не являются объектами ограниченной длины. Внизу демонстрируется этот факт.
--------------------------------------------------------------------------- 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)
Кроме того, использование бесконечно генератора справа от ключевого слова in запустит бесконечный цикл. Ну и наконец, наиболее формальный ответ: у генераторов не перегружен метод __contains__ , что отнимает у них право называться контейнером.
Итого, генераторы являются итерируемыми объектами, но не контейнерами и не объектами ограниченной длины.
from collections.abc import Container, Iterable, Sized print(isinstance(g, Container)) print(isinstance(g, Iterable)) print(isinstance(g, Sized))
Коллекции#
Коллекция — объект, который одновременно является контейнером, итерируемым объектом и объектом ограниченный длинны.
С бытовой точки зрения, коллекция — нечто, хранящее в себе совокупность объектов.
- Эта совокупность не может быть бесконечной, т.к. она физически хранится внутри коллекции, а значит должна быть ограниченного размера, т.е. допускает вызов функции 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))
Более конкретно, каждый абстрактный класс в иерархии задаёт интерфейс: только объекты, удовлетворяющие заданному интерфейсу, можно считать экземплярами этого класса. Все производные классы тоже обязаны удовлетворять этому интерфейсу, а значит экземпляры класса Collection должны одновременно удовлетворять интерфейсам классов Container , Iterable и Sized .
Дальнейшее ветвление в иерархии#
Выше было перечисленно сравнительно большое количество объектов, являющихся коллекциями. Дальнейшая их классификация обычно производится по способу получения доступа к элементам. По такому принципу можно выделить два наиболее широких класса — последовательности ( Sequence ) и отображения ( Mapping ), хотя ещё существуют множества ( Set ) и другие.
from collections.abc import Collection, Sequence, Mapping print(issubclass(Sequence, Collection)) print(issubclass(Mapping, Collection))
Про последовательности речь пойдет на следующей странице, а среди класса Mapping мы познакомимся только с одним представителем, но несколько позже (см. Словари. dict ).
Создание и удаление объектов. Сборщик мусора
Последовательности: списки, кортежи и строки
By Fadeev Egor
© Copyright 2022.