Коллекции

В этой лекции мы познакомимся с коллекциями (также называемыми контейнерами) - специальными классами, предназначенными для хранения множества объектов и предоставляющими доступ к ним. В Python существует несколько разновидностей коллекций - часть из них относится к встроенным типам данных, другие реализованы в отдельных модулях. Это многообразие связано с тем, что невозможно создать один тип, оптимально подходящий для всех возможных классов задач. Кроме того, многие коллекции относятся к неизменяемым типам данных и запрещают модификацию своих элементов. Это делает их непригодными для задач, где нужно часто изменять значения элементов, но позволяет эффективнее реализовать некоторые другие операции. В данной лекции мы обращаем внимание читателя на то, когда применять тот или иной тип коллекции.

Содержание лекции

Общая информация

Все коллекции относятся к итерируемым типам данных, то есть предоставляют доступ к отдельным элементам в некотором порядке. Для этого у каждого типа коллекции реализован специальный метод __iter__, который возвращает специфичный для нее итератор - специальный объект, имеющий метод __next__, который используется интерпретатором Python в цикле for ... in для получения следующего элемента. Когда метод __next__ итератора генерирует исключение StopIteration, интерпретатор сам перехватывает его и завершает выполнения цикла, переходя к следующей за ним инструкции.

Помимо того, что коллекции можно использовать в цикле for ... in, для всех них можно применять операцию in, которая возвращает True, если указанный элемент присутствует в коллекции, и False в противном случае. Эту операцию часто называют операцией проверки на вхождение.

Существует несколько встроенных функций, которые могут использоваться для любого типа коллекции, рассматривамого в этой лекции. Логично перечислить их здесь, но возможно некоторые из них станут полностью понятны вам только после того, как вы изучите всю лекцию. Заметим, что необязательные параметры методов или функции здесь и далее выделяются курсивом, а с помощью символов "..." мы иногда указываем, что в описании были перечислены не все необязательные параметры (за дополнительной информацией в этом случае стоит обращаться к справочному руководству Python).

Название
Описание
len(col)
Возвращает количество элементов в коллекции
all(col)
Возвращает True, если все элементы коллекции в логическом контексте оцениваются как True
any(col)
Возвращает True, если хотя бы один элемент коллекции в логическом контексте оцениваeтся как True
max(col, ...)
Возвращает наибольший элемент в коллекции
min(col, ...)
Возвращает наименьший элемент в коллекции
sum(col, start=0)
Возвращает сумму элементов коллекции плюс элемент start
sorted(col, key=None, reverse=False)
Возвращает список отсортированных в прямом или обратном (reverse=True) порядке элементов коллекции

Типы коллекций объединены в иерархию наследования. Следствием этого является тот факт, что один и тот же код зачастую способен работать с разными типами, ведь все они реализуют общие интерфейсы, наследуемые от базовых классов. Помимо этого, каждый отдельно взятый тип коллекции может добавлять специфичные для него методы.

В примерах в этой лекции мы будем использовать простой класс для демонстрации тех или иных возможностей различных коллекций. Ниже представлена его реализация.

In [1]:
class CollectionItem:
    def __init__(self, value):
        self.value = value
    
    # переопределяем метод для того, чтобы объекты класса `CollectionItem`
    # нормально выводились на экран при печати коллекции, содержащей их
    def __repr__(self):
        return 'CollectionItem({})'.format(self.value)
    
    # методы, которые потребуются при сравнении коллекций и при
    # поиске элементов в них

    def __eq__(self, other):
        if isinstance(other, CollectionItem):
            return self.value == other.value
        return NotImplemented

    def __lt__(self, other):
        if isinstance(other,CollectionItem):
            return self.value < other.value
        return NotImplemented

    def __le__(self, other):
        if isinstance(other,CollectionItem):
            return self.value <= other.value
        return NotImplemented

Последовательности

Последовательностью (англ. sequence) в Python называют коллекцию, представляющую собой набор пронумерованных элементов. Номер элемента определяет его позицию в последовательности и по другому еще называется индексом. Нумерация начинается с нуля, то есть в последовательности размера $N$ содержатся элементы с индексами $0$, $1$, ... , $N-1$.

Один из типов коллекций, относящийся к последовательностям, нам уже известен - это str (элементами, которые он хранит, являются символы). Последовательности поддерживают операции конкатенации +, дублирования * и взятия среза [], про которые мы рассказывали в контексте типа str здесь.

Также последовательности могут сравниваться друг с другом с помощью стандартных операций <, <=, ==, !=, >=, >. Сравнение при этом производится поэлементно, например операция seq1 < seq2 выполняется так:

  1. если первый элемент seq1 меньше первого элемента seq2, то результат True
  2. если первый элемент seq1 больше первого элемента seq2, то результат False
  3. если первые элементы равны, то сравниваем вторые и т.д.
  4. если в последовательности seq1 закончились элементы, а в seq2 нет, то результат True (это возможно, когда seq1 состоит из тех же элементов, что и seq2, но короче)
  5. если в seq2 закончились элементы, то результат False (аналогично предыдущему пункту, только в этот раз вторая последовательность короче)

Кроме уже перечисленных операций, стоит упомянуть о двух методах, также реализованных всеми последовательностями:

Название
Описание
seq.count(item)
Возвращает количество элементов, равных item, в последовательности
seq.index(item, start=0, end=len(seq))
Возвращает индекс первого элемента, равного item, из среза [start, end)

Важно отметить, что любые операции, связанные с поиском элементов в последовательности (in, методы count и index) в общем случае выполняются неэффективно, потому что требуют прохода по всем ее элементам. Если такие операции планируется использовать часто, лучше применить другой тип коллекции (забегая вперед, скажем, что речь идет о словаре, который рассматривается далее). Последовательности в основном предназначены для хранения элементов в определенном порядке и извлечении их по индексу.

Кортеж

Кортеж (англ. tuple) - это последовательность из нуля или более ссылок на объекты произвольных типов. Типом кортежа является класс tuple.

В следующем примере показывается, как создавать кортежи с помощью круглых скобок () или путем явного вызова конструктора класса tuple:

In [2]:
# создание пустого кортежа
t1 = () 
t2 = tuple()

# создание кортежа с несколькими элементами
t3 = (1,)              # если элемент один, то запятая в конце обязательна (иначе создастся int)
t4 = (1, True, 'test') # кортеж, содержащий 3 элемента
t5 = 'hello', 'world'  # скобки можно и не указывать

# создание кортежа из переменной итерируемого типа;
# в этом случае все элементы из аргумента функции tuple вставляются в новый кортеж
t6 = tuple('abc')

# пример использования

print(type(t1))
print(len(t3))
print(t4)
print(t6)
<class 'tuple'>
1
(1, True, 'test')
('a', 'b', 'c')

Так как кортеж, как и любая последовательность, является итерируемым типом, для прохода по его элементам можно использовать цикл for ... in:

In [3]:
t = (1, 2, 3, 4, 5)
t_sum = 0

for item in t:
    t_sum += item

print(t_sum)
15

В Python существует встроенная функция range, принимающая до трех аргументов (для обозначения начала, конца и шага) и возвращающая итератор на соответствующую последовательность целых чисел. Эта функция зачастую используется для реализации еще одного способа обхода коллекций:

In [4]:
t = ('aaa', 'bbb', 'ccc')

# range с одним аргументом arg возвращает итератор на
# последовательность 0, 1, ... , arg
for idx in range(len(t)): 
    print(idx, t[idx])
0 aaa
1 bbb
2 ccc

На элементы кортежа не накладывается никаких ограничений, т.е. он может хранить ссылки на объекты любого типа, в том числе на другие кортежи или экземпляры собственных классов:

In [5]:
some_tuple = ('aaa', 'bbb', 'ccc')
some_item = CollectionItem(5)
some_string = 'hello'

t = (some_string, some_item, some_tuple, 3.0, 'hello', 1)
print(t)
('hello', CollectionItem(5), ('aaa', 'bbb', 'ccc'), 3.0, 'hello', 1)

Продемонстрируем, как могут применяться основные операции, доступные для всех последовательностей, к кортежам:

In [6]:
print(t[2:4])   # выводим срез [2:4] кортежа
print(t[2][0])  # выводим первый элемент вложенного кортежа
print(t[2][1:]) # выводим срез [1:] вложенного кортежа

if CollectionItem(5) in t:
    print('{} is found'.format(CollectionItem(5)))

print(t.count('hello'))

# метод index генерирует исключение ValueError, если элемент не найден,
# поэтому используем try ... except
try:
    print(t.index(1))
except ValueError:
    print('item is not found')
(('aaa', 'bbb', 'ccc'), 3.0)
aaa
('bbb', 'ccc')
CollectionItem(5) is found
2
5
In [7]:
t1 = (1, 2, ('a', CollectionItem(3)))
t2 = (1, 2, ('a', CollectionItem(3)))
t3 = (1, 2, ('a', CollectionItem(333)))

# сравнение выполняется поэлементно, вложенные кортежи (и другие
# последовательности) обрабатываются рекурсивно

print(t1 == t2)
print(t1 == t3)
print(t1 >= t3)
True
False
False

Кортежи, как и строки, относятся к неизменяемым типам данных. Это значит, что нельзя заменить их элементы на другие (будет сгенерировано исключение TypeError):

In [8]:
t = (1, 2, 3)
t[0] = 100
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-8-ca3b752cda23> in <module>()
      1 t = (1, 2, 3)
----> 2 t[0] = 100

TypeError: 'tuple' object does not support item assignment

Для решения этой задачи можно использовать прием, основанный на применении операций взятия среза [] и конкатенации +:

In [9]:
t = ('a', 'b', 'd', 'd', 'e')
t = t[0:2] + ('c',) + t[3:] # обратите внимание, что символ 'c' нужно
                            # добавлять как кортеж, а не как строку!
print(t)
('a', 'b', 'c', 'd', 'e')

Этот способ однако очень неэффективен, и им не стоит злоупотреблять. Если нужно часто модифицировать элементы последовательности, вместо кортежа стоит использовать список, который будет рассмотрен далее.

В заключение скажем, что кортежи в основном используются для хранения небольшого количества связанных значений, а также для распаковки последовательностей. Например, кортеж хорошо подойдет для хранения координат точки на плоскости, при этом нам не потребуется создавать специальный класс для этого:

In [10]:
point1 = (1, 1)
point2 = (3, 3)
point3 = (5, 1)
triangle = (point1, point2, point3)

print(triangle)
((1, 1), (3, 3), (5, 1))

Используя такое представление треугольника на плоскости, мы можем так реализовать функцию, выполняющую его перемещение вдоль координатных осей:

In [11]:
def move_triangle(triangle, shift_x, shift_y):
    new_triangle = ()
    
    for point in triangle:
        new_point = (point[0] + shift_x, point[1] + shift_y)
        new_triangle += (new_point,) # запятая в конце обязательна, потому что без нее в 
                                     # кортеж будет добавлено два значения, а не вложенный кортеж
    return new_triangle


# пример использования

print(move_triangle(triangle, -1, -1))
((0, 0), (2, 2), (4, 0))

Именованный кортеж

Именованный кортеж - это кортеж, к элементам которого можно обращаться не только по индексу, но и по некоторому имени. В остальном именнованный кортеж идентичен обычному и имеет те же ограничения: он является неизменяемым типом и плохо подходит для операция поиска элемента.

Лучше всего именованные кортежи подходят для представления данных, состоящих из нескольких значений. Они лучше обычных кортежей справляются с этой задачей, потому что позволяют дать осмысленное имя каждому значению.

Чтобы создать именованный кортеж, потребуется подключить модуль collections и использовать функцию namedtuple. С помощью нее мы можем создать класс для наших именованных кортежей, в котором будут определены атрибуты, которые мы укажем при вызове функции:

In [12]:
from collections import namedtuple
Address = namedtuple('Address', 'city street number apartment zip')

В примере выше, с помощью функции namedtuple мы создаем класс Address, имеющий атрибуты city, street, number, apartment и zip. Этот класс мы сохраняем в переменную, чтобы потом можно было создавать его объекты, которые и будут нашими именованными кортежами. Делается это так:

In [13]:
a = Address('Tomsk', 'Lenina', 36, 1, '634050')
print(a.street, a.number) # обращаемся к элементам по имени
print(a[1], a[2])         # обращаемся к элементам по индексу
Lenina 36
Lenina 36

На этом мы закончим рассмотрение именованных кортежей, потому что остальные операции выполняются для них так же, как и для обычных, в чем вы можете убедиться самостоятельно.

Список

Список (англ. list), так же, как и кортеж, представляет собой последовательность из нуля или более ссылок на объекты произвольных типов. Ключевое различие между ними заключается в том, что список является изменяемым типом данных, в отличие от кортежа, а это значит, что значения его элементов можно модифицировать. Типом списка является list.

Список можно создавать либо с помощью квадратных скобок [], либо путем явного вызова конструктора list. Все операции, которые можно выполнять с кортежем, можно выполнять и со списком, поэтому мы не будем подробно рассматривать их здесь.

In [14]:
# создание пустого списка
l1 = []
l2 = list()

# создание списка из нескольких элементов
l3 = [1]
l4 = [0.5, CollectionItem(13), ('hello', 'world')]

# создание списка из итерируемого типа
l5 = list((1, 2, 3))

# пример использования

print(type(l5))
print(l5)

     # поиск элемента

if CollectionItem(13) in l4:
    print(CollectionItem(13), 'is found')

    # обращение к элементу или срезу

print(l4[1].value)
print(l4[2][0][0])
print(l4[::-1]) # получаем элементы в обратном порядке

    # конкатенация и дублирование

l3 += [2, 3] # добавляем к списку еще два элемента
l3 *= 2      # дублируем список
print(l3)

    # обход в цикле

result = 0
for item in l3:
    result += item

print(result)
<class 'list'>
[1, 2, 3]
CollectionItem(13) is found
13
h
[('hello', 'world'), CollectionItem(13), 0.5]
[1, 2, 3, 1, 2, 3]
12

Как уже было упомянуто, главной особенностью списка является то, что его элементы можно изменять:

In [15]:
l = [1, 2, 3]

for idx in range(len(l)):
    l[idx] *= 2 # удваиваем элементы

print(l)
[2, 4, 6]

С помощью присваивания итерируемых объектов можно изменять целые срезы в списке, причем срез и итерируемый объект не обязаны иметь одинаковое количество элементов:

In [16]:
l = [1, 0, 0, 5]
l[1:3] = [2, 3, 4] # размер среза - 2; размер итерируемого объекта - 3
print(l)
[1, 2, 3, 4, 5]

Наконец, элементы и целые срезы можно удалять из списка с помощью операции del:

In [17]:
l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

del l[0]    # удаляем первый элемент (0)
print(l)

del l[1::2] # удаляем элементы на нечетных позициях (2, 4, 6, 8)
print(l)

l[0:2] = [] # еще один способ удалить элементы (удаляются 1 и 3)
print(l)
[1, 2, 3, 4, 5, 6, 7, 8, 9]
[1, 3, 5, 7, 9]
[5, 7, 9]

Класс list дополнительно представляет еще несколько методов, которые могут использоваться для списков. Мы перечислим лишь наиболее полезные из них:

Название
Описание
l.append(item)
Вставляет элемент item в конец списка
l.insert(idx, item)
Вставляет элемент item в позицию idx в списке (медленнее, чем append)
l.pop(idx)
Удаляет из списка элемента с индексом idx (по умолчанию - последний) и возвращает его в качестве результата
l.remove(item)
Удаляет первый слева элемент из списка, равный item
l.clear()
Очищает список, удаляя все элементы из него
l.reverse()
Переставляет элементы списка в обратном порядке
l.sort(key=None, reverse=False)
Сортирует список в прямом (по умолчанию) или обратном (reverse=True) порядке
In [18]:
l = ['per', 'aspera', 'astra']

l.insert(2, 'ad')
print(l)

l.reverse()
print(l)
['per', 'aspera', 'ad', 'astra']
['astra', 'ad', 'aspera', 'per']

Отдельно рассмотрим метод sort, который нужно вызывать только с именованными аргументами. По умолчанию для сортировки он использует операцию <, определенную в типах элементов. Если же в параметре key задана функция, то интерпретатор будет вызывать ее для каждого элемента списка, и использовать возвращенное значение для сортировки этого элемента. Например, вот так мы можем отсортировать числа по модулю в обратном порядке:

In [19]:
l = [10, -12, 0, 5, -3, 13, -1]

# сортируем с помощью обычной операции < для int

l.sort() 
print(l)

# для каждого элемента вызывается функция, возвращающая
# модуль числа, который затем сортируется с помощью операции <

l.sort(key=lambda x: x if x >= 0 else -x)
print(l)
[-12, -3, -1, 0, 5, 10, 13]
[0, -1, -3, 5, 10, -12, 13]

Параметр key может пригодиться в случаях, когда нужно сортировать сложные типы данных, состоящие из нескольких полей. Рассмотрим, как сортируется список, состоящий из точек на плоскости:

In [20]:
l = [(0, 0), (1, 5), (-3, 6), (-3, -3), (7, -3)]
l.sort()
print(l)
[(-3, -3), (-3, 6), (0, 0), (1, 5), (7, -3)]

Как мы видим, вначале сравниваются абсциссы, а затем ординаты, что полностью соответвует описанному в разделе Последовательности алгоритму. Возникает вопрос, как переписать этот пример, чтобы сортировка вначале велась по ординате? По сути, нам нужно просто во время сравнения поменять координаты точки местами:

In [21]:
l.sort(key=lambda x: (x[1], x[0]))
print(l)
[(-3, -3), (7, -3), (0, 0), (1, 5), (-3, 6)]

Строка

Некоторые операции со строками, представляемыми типом str, мы уже рассматривали в лекции 5, поэтому будет нелишним освежить их в памяти перед тем, как продолжать изучение материала данного раздела.

Операция in, а также методы count и index, доступные всем типам последовательностей, для строк могут работать не только с отдельными символами, но и с целыми подстроками:

In [22]:
s = 'abcdefabc'

print('def' in s)
print(s.index('def'))
print(s.count('abc'))
True
3
2

Тип str предоставляет специфичные для строк методы. Перечислим некоторые их них:

Название
Описание
s.format(...)
Возвращает копию строки, отформатированную в соответствии с переданными аргументами
s.isalnum()
Возвращает True, если строка не пустая и содержит только алфавитно-цифровые символы
s.isalpha()
Возвращает True, если строка не пустая и содержит только алфавитные символы
s.isdigit()
Возвращает True, если строка не пустая и содержит только цифровые символы
s.isspace()
Возвращает True, если строка не пустая и содержит только пробельные символы
s.lower()
Возвращает копию строки, в которой все символы приведены к нижнему регистру
s.upper()
Возвращает копию строки, в которой все символы приведены к верхнему регистру
s.join(seq)
Объединяет все элементы последовательности seq, вставляя между ними строку s
s.split(substr, n)
Возвращает список строк, выполняя разбиение исходной строки по подстроке substr не более n раз
In [23]:
def get_word_count(text):
    words = text.split() # split без аргументов разбивает строку по пробельным символам
    return len(words)

s = 'Cogito ergo sum'
print(get_word_count(s))

s = '123'
print(s.isdigit())

l = ['a', 'b', 'c']
print('--'.join(l)) # обратите внимание на такой способ вызова метода строки
3
True
a--b--c

Отдельно стоит поговорить о методе format. Он принимает произвольное количество аргументов, которыми заменяет специальные заполнители (англ. placeholder) в строке, для которой он вызван. Проще объяснить это на примере:

In [24]:
format_spec = 'Hello, {}. I\'m {}.' # заполнитель {} обозначает место, в которое нужно вставить аргумент
result = format_spec.format('Alice', 'Bob')
print(result)
Hello, Alice. I'm Bob.

В заполнителях можно указывать номер или имя, которые будут использованы для выбора аргумента - соответственно, позиционного или именованного:

In [25]:
print('{1}, {0}'.format('hello', 'world')) # hello - 0, world - 1
print('{film}: {actor}'.format(film='Pulp Fiction', actor='John Travolta'))
world, hello
Pulp Fiction: John Travolta

Возможности метода format столь широки, что им можно было бы посвятить отдельную лекцию. Например, с его помощью можно определять выравнивание отформатированной строки, систему счисления, в которой выводятся числовые аргументы, и многое другое. Все это подробно описано в справочном руководстве в разделе Format Specification Mini-Language.

Распаковка последовательностей

Интересной возможностью, связанной с последовательностями, является распаковка. Суть этой операции заключается в том, что можно одной простой инструкцией проинициализировать сразу несколько переменных элементами последовательности. Делается это так:

In [26]:
l = [1, 2, 3]
t = ('a', 'b', 'c')

x, y, z = l # распаковываем список
print('x={}, y={}, z={}'.format(x, y, z))

x, y, z = t # распаковываем кортеж
print('x={}, y={}, z={}'.format(x, y, z))
x=1, y=2, z=3
x=a, y=b, z=c

С помощью распаковки можно элегантно обменять значения переменных:

In [27]:
a = 0
b = 1
a, b = (b, a)
print('a={}, b={}'.format(a, b))
a=1, b=0

Если количество переменных слева не совпадает с размером последовательности, то возбуждается исключение ValueError:

In [28]:
l = [1, 2, 3]
x, y = l
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-28-f23100cd4ab8> in <module>()
      1 l = [1, 2, 3]
----> 2 x, y = l

ValueError: too many values to unpack (expected 2)

Можно однако перед одной из переменных, стоящих слева от знака =, указать символ * - тогда в эту переменную интерпретатор запишет список из оставшихся после распаковки элементов последовательности:

In [29]:
l = (1, 2, 3, 4, 5)

a, b, *remainder = l
print('a={}, b={}'.format(a, b))
print('remainder:', remainder)
print('type:', type(remainder))

print('')

a, *remainder, b = l
print('a={}, b={}'.format(a, b))
print('remainder:', remainder)

print('')

*remainder, a, b = l
print('a={}, b={}'.format(a, b))
print('remainder:', remainder)
a=1, b=2
remainder: [3, 4, 5]
type: <class 'list'>

a=1, b=5
remainder: [2, 3, 4]

a=4, b=5
remainder: [1, 2, 3]

Распаковка часто применяется в циклах, делая код более читабельным:

In [30]:
people = [('Alice', 20), ('Bob', 25), ('Carol', 30)]

for name, age in people: # распаковываем кортеж, являющийся элементом списка
    print('{} is {} years old'.format(name, age))
Alice is 20 years old
Bob is 25 years old
Carol is 30 years old

Также можно использовать распаковку для передачи аргументов в функцию. Для этого используется несколько иной синтаксис - символ * ставится перед последовательностью, содержащей аргументы, с которым нужно вызвать функцию:

In [31]:
def get_sum(a, b, c):
    return a + b + c

l = [1, 2, 3]
result = get_sum(*l) # после распаковки a=l[0], b=l[1], c=l[2]
print(result)
6

Множество

Множеством в Python называется коллекция, моделирующая поведение одноименного математического объекта. Из такого раздела математики, как теория множеств, мы помним, что множество состоит из уникальных элементов и для него можно выполнять такие операции, как объединение, пересечение и другие.

В Python типом множества является класс set. Как и множество в математике, множество в Python хранит уникальные элементы и поддерживает аналогичные операции. Оно является неупорядоченной коллекцией (не относится к последовательностям), а следовательно к нему не применимы понятия индекса элемента или среза. С другой стороны, множество является изменяемым типом, и добавление элементов или их удаление выполняется гораздо быстрее чем, например, для кортежей, в которых это реализуется путем создания нового экземпляра. Кроме того, операция проверки на вхождение in для множеств выполняется несоизмеримо эффективнее, чем для последовательностей.

Из всего вышесказанного становится понятно, что множества стоит использовать тогда, когда вам нужен быстрый поиск элемента и не важен порядок, в котором они хранятся.

Множество можно создать с помощью фигурных скобок {} или путем вызова конструктора set:

In [32]:
# создание пустого множества
s1 = set()
# s = {} - так нельзя, потому что такой способ создает словарь (см. далее)!

# создание множества из нескольких элементов
s2 = {0.0}
s3 = {1, 'hello', -2.5}

# создание множества из итерируемого типа
s4 = set('apple')

# пример использования

print(type(s1))
print(len(s2))
print(s3)
print(s4)
<class 'set'>
1
{1, -2.5, 'hello'}
{'e', 'p', 'l', 'a'}

Обратите внимание, что множеcтво хранит элементы в произвольном порядке - не обязательно в том, в котором они указывались при его создании. Также на примере s4 видно, что множество содержит только уникальные элементы, отбрасывая при необходимости дубликаты.

Рассмотрим основные методы, реализованные в классе set:

Название
Описание
s.add(item)
Добавляет item в множество, если его там нет
s.discard(item)
Удаляет элемент item из множества, если он там есть
s.remove(item)
Удаляет элемент item из множества, если его нет - возбуждает исключение KeyError
s.clear()
Удаляет все элементы из множества
s1.union(s2)
Возвращает новое множество, содержащее объединение s1 и s2
s1.intersection(s2)
Возвращает новое множество, содержащее пересечение s1 и s2
s1.difference(s2)
Возвращает новое множество, содержащее разность s1 и s2
s1.symmetric_difference(s2)
Возвращает новое множество, содержащее симметрическую разность s1 и s2
s1.issubset(s2)
Возвращает True, если s1 подмножество s2
s1.issuperset(s2)</div >
Возвращает True, если s1 надмножество s2
In [33]:
s1 = set()

s1.add(1)
s1.add(2)
s1.add(1) # ничего не добавит, потому что 1 уже есть в множестве

s2 = {2, 'string', 3.5}
s2.discard(3.5)

print(s1)
print(s2)
print('')

print(s1.union(s2))
print(s1.intersection(s2))
print(s1.symmetric_difference(s2))
print('')

s3 = {1}
print(s1.issuperset(s3))
{1, 2}
{'string', 2}

{1, 2, 'string'}
{2}
{'string', 1}

True

Вместо методов union, intersection, difference и symmetric_difference можно использовать перегруженные для типа set операции |, &, - и ^, для которых также поддерживаются комбинированные операции присваивания вида x op= y:

In [34]:
s1 = {1, 2, 3}
s2 = {1, 3, 5}

print(s1 | s2)
print(s1 & s2)
print(s1 - s2)

s1 ^= s2
print(s1)
{1, 2, 3, 5}
{1, 3}
{2}
{2, 5}

Множества могут сравниваться между собой с использованием стандартных операций <, <=, ==, !=, >=, >. При этом операции == и != имеют обычный смысл и позволяют узнать, состоят ли множества из одинаковых элементов или нет, а остальные определяют, является ли одно множество подмножеством другого.

In [35]:
s1 = {1, 2 ,3}
s2 = {1, 2, 3}
s3 = set()
s4 = {1, 3}
s5 = {3, 5}

print('s1 == s2:', s1 == s2)
print('s1 < s2:', s1 < s2)
print('s1 <= s2:', s1 <= s2)
print('s3 < s4:', s3 < s4)
print('s4 >= s5:', s4 >= s5)
s1 == s2: True
s1 < s2: False
s1 <= s2: True
s3 < s4: True
s4 >= s5: False

Несмотря на то, что само множество является изменяемым типом данных (добавление/удаление элементов не требует создания нового объекта), его элементы должны иметь неизменяемый тип. Это ограничение связано с внутренней реализаций множества, и при попытке его нарушить генерируется исключение:

In [36]:
s = set()
item = CollectionItem(0) # изменяемый тип!
s.add(item)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-36-f42b567f4744> in <module>()
      1 s = set()
      2 item = CollectionItem(0) # изменяемый тип!
----> 3 s.add(item)

TypeError: unhashable type: 'CollectionItem'

Как мы уже говорили, множество оптимизировано для задач, связанных с поиском элементов в нем. Давайте посмотрим, сколько времени потребует операция in, выполненная для очень большого множества.

Замерить время выполнения ячейки можно с помощью специальной команды %%time, которая предоставляется исключительно средой Jupyter Notebook и не является частью самого языка Python. Заметим, что существуют и другие подобные команды, которые в совокупности называются магическими в Jupyter Notebook.

Для нашего эксперимента создадим вначале очень большое множество:

In [37]:
s = set()

for value in range(1000000): # добавляем 1 000 000 элементов!
    s.add(value)

print(len(s))
1000000

Теперь замерим время поиска случайного элемента:

In [38]:
%%time

value = 123456
print(value in s)
True
Wall time: 0 ns

Удивительный результат! Для того, чтобы найти один элемент из миллиона, у интерпретатора ушло 0 наносекунд, т.е. настолько мало времени, что оно округлилось в итоге до нуля.

Словарь

Словарем называется неупорядоченная коллекция с типом dict, каждый элемент которой представляет собой пару "ключ-значение". Ключ уникальным образом идентифицирует значение и используется для обращения к нему.

Словарь, как и множество, относится к изменяемым типам данных и обладает теми же сильными сторонами и ограничениями, а именно - реализует столь же быстрый поиск по ключу, но требует, чтобы они имели неизменяемый тип данных. Отличие от множества заключается в том, что к каждому ключу привязано некоторое значение, которое может иметь совершенно произвольный тип данных.

Словарь можно создать с помощью фигурных скобок {} или с помощью вызова конструктора класса dict:

In [39]:
# создание пустого словаря
d1 = {}
d2 = dict()

# создание словаря с нескольки элементами;
# слева от знака ":" указывается ключ, справа - значение;
# обратите внимание, что поскольку tuple является неизменяемым типом, мы
# можем использовать кортеж как ключ (а вот list или CollectionItem - нет)
d3 = {1:'abc', 'abc':1, 'list':[1, 2, 3], (0, 1):CollectionItem(13)}

# создание словаря из итерируемого типа (для каждого его элемента должна
# быть возможность распаковать его в две переменные: для ключа и для значения)
d4 = dict([(1, 1), (2, 2), (3, 3)])

# пример использования

print(type(d1))
print(len(d3))
print(d3)
print(d4)
print('')
<class 'dict'>
4
{1: 'abc', 'abc': 1, 'list': [1, 2, 3], (0, 1): CollectionItem(13)}
{1: 1, 2: 2, 3: 3}

Получение значения элемента происходит с помощью ключа и операции []. С помощью нее можно также изменить значение или добавить новый элемент в словарь. Удаление элемента выполняется операцией del:

In [40]:
d = {1:[1, 2, 3], 'key':'value'}

# получаем значения элементов

print(d[1])
print(d['key'])

# добавляем или изменяем элемент (в случае, если такого ключа
# нет в словаре, то происходит добавление элемента, а иначе -
# модификация существующего)

d['key'] = 'new value'      # элемент с таким ключом есть, будет изменено его значение
d[3] = CollectionItem(1001) # элемента с таким ключом нет, он будет добавлен
print(d)

# удаляем элемент с ключом 1

del d[1]
print(d)
[1, 2, 3]
value
{1: [1, 2, 3], 'key': 'new value', 3: CollectionItem(1001)}
{'key': 'new value', 3: CollectionItem(1001)}

При попытке получить значение, связанное с несуществующим ключом, интерпретатор генерирует исключение KeyError:

In [41]:
d = {}
print(d['abc'])
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-41-b325e82df1aa> in <module>()
      1 d = {}
----> 2 print(d['abc'])

KeyError: 'abc'

Операция in позволяет узнать, присутствует ли указанный ключ в словаре или нет:

In [42]:
d = {0:1, 'aaa':'bbb'}

print('0 in d:', 0 in d)
print('aaa in d:', 'aaa' in d)
print('bbb in d:', 'bbb' in d) # будет False, потому что 'bbb' нет среди ключей
0 in d: True
aaa in d: True
bbb in d: False

Класс dict реализует несколько весьма полезных методов для работы со словарем:

Название
Описание
d.get(key)
Возвращает значение, связанное с ключом key или None, если его нет
d.get(key, value)
Возвращает значение, связанное с ключом key или value, если его нет
d.setdefault(key, value)
То же, что предыдущее, но при отсутствии ключа, добавляет новый элемент key:value
d.pop(key)
Возвращает значение, связанное с ключом key и удаляет элемент (возбуждает KeyError, если ключа нет)
d.pop(key, value)
Возвращает значение, связанное с ключом key и удаляет элемент (возвращает value, если ключа нет)
d.items()
Возвращает представление (англ. view), содержащее кортежи (key, value) для всех элементов словаря
d.keys()
Возвращает представление, содержащее ключи всех элементов словаря
d.values()
Возвращает представление, содержащее значения всех элементов словаря
In [43]:
d = {'key1':1, 'key2':2}

print('key3:', d.get('key3', 'not found'))
print('key3:', d.setdefault('key3', 3))
print('key3:', d.pop('key3', 'value'))
print(d)
key3: not found
key3: 3
key3: 3
{'key1': 1, 'key2': 2}

Два словаря можно сравнивать с помощью операций == и != на предмет того, содержат они одни и те же элементы или нет:

In [44]:
d1 = {1:1, 2:1}
d2 = {1:1, 2:1}
d3 = {1:1, 2:2}

print(d1 == d2)
print(d2 == d3)
True
False

Представления, возвращаемые функциям items, keys и values, являются итерируемыми объектами, доступными только для чтения и предоставляющими определенную информацию об элементах словаря. Поскольку представления относятся к итерируемым типам, их можно использовать в циклах for ... in:

In [45]:
d = {'key1':0, 'key2':1, 'key3':1}

# если для прохода по словарю не использовать представления,
# то он по умолчанию будет осуществляться по его ключам (так же,
# как при проходе по представлению keys)
for key in d:
    print('key:', key)
print('')

# проходим по представлению items, состоящему из пар (key, value)
for item in d.items():
    print('{}: {}'.format(item[0], item[1]))
print('')

# проходим по представлению values, состоящему из значений всех
# элементов словаря
for value in d.values():
    print('value:', value)
key: key1
key: key2
key: key3

key1: 0
key2: 1
key3: 1

value: 0
value: 1
value: 1

У представлений существует две особенности. Во-первых, они отражают все изменения, которые происходят со словарем, из которого они получены:

In [46]:
d = {'a':1, 'b':2, 'c':3}

values = d.values()
print(values)

d['d'] = 4
print(values)
dict_values([1, 2, 3])
dict_values([1, 2, 3, 4])

Во-вторых, представления items и keys поддерживают операции множества: | (объединение), &(пересечение), -(разность) и ^(симметрическая разность). Например, вот так можно определить, какие из указанных ключей содержатся в словаре:

In [47]:
check_keys = {'a', 'b', 'x', 'y'}
result = d.keys() & check_keys
print(result)
{'b', 'a'}

Словари часто используется для хранения счетчиков уникальных элементов. Рассмотрим пример, в котором мы будем подсчитывать количество одинаковых слов в тексте. Для простоты, пусть текст содержит только сами слова, разделенные пробелами без каких-либо знаков препинания.

In [48]:
text = 'word woRD hello TEST astra test WORD'
word_count = dict()

# приводим все слова к одному регистру
text = text.lower()

# разбиваем строку по пробельным символам
words = text.split()

# подсчитываем количество одинаковых слов
for word in words:
    word_count[word] = word_count.get(word, 0) + 1

print(word_count)
{'word': 3, 'hello': 1, 'test': 2, 'astra': 1}

Копирование коллекций

Как мы рассказывали в 4 лекции, все переменные в Python хранят не сами объекты, а лишь ссылки на них. Это позволяет очень эффективно реализовать операцию =, при выполнении которой не происходит копирование данных объекта, размер которых может быть очень большой, а просто переменной слева от знака = присваивается ссылка на объект, находящийся справа. Этот подход требует от программиста более внимательной работы с объектами, чтобы не допустить случайной их модификации. Особенно это касается изменяемых типов данных, к которым относятся в том числе коллекции list, set и dict. Рассмотрим такой пример:

In [49]:
l1 = [1, 2, 3]
l2 = l1
l2.append(4)

В этом пример есть потенциальная ошибка, которую мог допустить невнимательный программист: после операции l2 = l1 обе переменные ссылаются на один и тот же список! А это значит, что изменение его через одну переменную повлияет и на другую, в чем можно легко убедиться:

In [50]:
print(l2)
print(l1)
print(l1 is l2)
[1, 2, 3, 4]
[1, 2, 3, 4]
True

Иногда, конечно, именно такая логика работы и нужна - тогда рассмотренная ситуация не будет ошибкой. В таких случаях лучше оставить какой-то комментарий, чтобы другой разработчик мог понять, что вы специально написали такой код.

Если нужно создать копию коллекции, то можно воспользоваться явным вызовом конструктора, или подключить специальный модуль copy, в котором реализована одноименная функция:

In [51]:
import copy

l1 = [1, 2, 3]

l2 = list(l1)      # копируем с помощью явного вызова конструктора
l2.append(4)

l3 = copy.copy(l2) # копируем с помощью функции copy
l3.append(5)

print(l1)
print(l2)
print(l3)
print(l1 is l2)
print(l2 is l3)
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
False
False

Теперь мы видим, что изменение одного списка никак не затрагивает другой. Проблема решена? Не совсем. Предположим, что в коллекции у нас хранятся ссылки на элементы с изменяемым типом данных. При копировании новая коллекция будет содержать свой набор элементов, но каждый будет ссылаться на то же значение в памяти, что и элемент оригинальной коллекции. Такое копирование называется поверхностным, и оно так же может быть причиной трудно обнаруживаемой ошибки:

In [52]:
import copy

l1 = [0, CollectionItem('a'), CollectionItem('b')]
l2 = copy.copy(l1)
l2.append(CollectionItem('c'))

print('original:', l1)
print('copy:', l2)
print('')

l2[0] += 1
l2[1].value = 'x' 

print('original:', l1)
print('copy:', l2)
original: [0, CollectionItem(a), CollectionItem(b)]
copy: [0, CollectionItem(a), CollectionItem(b), CollectionItem(c)]

original: [0, CollectionItem(x), CollectionItem(b)]
copy: [1, CollectionItem(x), CollectionItem(b), CollectionItem(c)]

Давайте тщательно разберем этот пример (если вам будет что-то непонятно, перечитайте этот раздел):

  1. При добавлении нового элемента в копию списка, оригинальный список не изменился, как и следовало ожидать.
  2. При модификации первого элемента копии, который имеет тип int и следовательно является неизменяемым, интерпретатор создал новый объект вместо существующего, поэтому первый элемент оригинального списка остался прежним.
  3. Про модификации второго элемента копии, которые имеет тип CollectionItem и является изменяемым, никакого нового объекта не создавалось - интерпретатор просто обновил значение атрибута value в памяти. Так как оба списка хранят ссылку на один и тот же объект в памяти, изменения в копии отразились и на оригинале.

Чтобы решить эту проблему, модуль copy предоставляет функцию deepcopy для глубокого копирования, при котором дополнительно создается копия и каждого элемента. Этот метод для больших коллекций работает долго, так что используйте его только в случае крайней необходимости:

In [53]:
import copy
l1 = [CollectionItem(0), CollectionItem(1)]
l2 = copy.deepcopy(l1)
l2[0].value += 1

print(l1)
print(l2)
[CollectionItem(0), CollectionItem(1)]
[CollectionItem(1), CollectionItem(1)]

Генераторы

Почти во всех предыдущих примерах для инициализации коллекций мы использовали литералы соответствующего типа, в которых указывали нужные элементы. Очевидно, что такой способ годится только для небольших коллекций. В случае, когда это не так, применяется программный способ заполнения.

Одним из вариантов инициализации большой коллекции является тот, что мы применили в примере, в котором замерялась скорость поиска элемента в множестве. Другой вариант заключается в использовании генератора - специальных выражений, содержащих цикл и, возможно, дополнительное условие.

Генератор можно создать для таких типов коллекций, как списки, множества и словари. Они имеют следующий синтаксис:

генератор списка:
[expression for item in iterable if condition]

генератор множества:
{expression for item in iterable if condition}

генератор словаря:
{key_expression:value_expression for key, value in iterable if condition}

Все генераторы работают по одной схеме:

  1. В цикле обрабатываются все элементы из iterable.
  2. Если в генераторе есть предложение if, то для элемента вычисляется condition. Если в результате получается False, то этот элемент iterable игнорируется.
  3. Вычисляется expression (для словарей - key_expression, value_expression), и его результат становится элементом коллекции

Рассмотрим простейший пример генератора. В нем мы используем функцию range с двумя аргументами, которые играют роль начала и конца числовой последовательности

In [54]:
l = [item * 2 for item in range(10, 21)]
print(l)
[20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40]

Более полезным будет пример, в которым мы помещаем в множество только високосные года (здесь перечислены правила, по которым можно их определить):

In [55]:
leap_years = {year for year in range(1900, 2001)\
              if (year % 400 == 0) or (year % 100 != 0 and year % 4 == 0)}
print(sorted(leap_years))
[1904, 1908, 1912, 1916, 1920, 1924, 1928, 1932, 1936, 1940, 1944, 1948, 1952, 1956, 1960, 1964, 1968, 1972, 1976, 1980, 1984, 1988, 1992, 1996, 2000]

Генератор словаря может применяться для создания инвертированного словаря, в котором ключ становится значением, а значение - ключом:

In [56]:
d = {1:'a', 2:'b', 3:'c'}
inverted_d = {value:key for key, value in d.items()}
print(inverted_d)
{'a': 1, 'b': 2, 'c': 3}

Функции с переменным числом аргументов

В Python можно создавать функции, которые принимают переменное число аргументов. Это реализовано следующим образом:

  • При определении функции с помощью инструкции def, один из параметров может перед своим именем содержать префикс * или **.
  • Когда интерпретатор встречает инструкцию вызова такой функции, он вначале инициализирует все обычные параметры. Если после этого остаются какие-то позиционные аргументы, то он создает кортеж из них, а затем использует его в качестве аргумента для параметра с префиксом *. Аналогичным образом он поступает с оставшимися именованными параметрами, только помещает их в словарь и затем использует как аргумент для параметра с префиксом **.

Все станет понятнее, после того, как мы рассмотрим пример такой функции, которая будет выводить все свои аргументы:

In [57]:
def test(param1, param2, *other_params, **other_named_params):
    print('param1:', param1)
    print('param2:', param2)
    print('other positional params:', other_params)
    print('other named params:', other_named_params)
    print('')

# пример использования

test(1, 2)
test('a', param2='b')
test(0.1, 0.2, 0.3, 0.4, 0.5)
test(1, 2, 3, 4, 5, param3=6, param4=7, param5=8)
param1: 1
param2: 2
other positional params: ()
other named params: {}

param1: a
param2: b
other positional params: ()
other named params: {}

param1: 0.1
param2: 0.2
other positional params: (0.3, 0.4, 0.5)
other named params: {}

param1: 1
param2: 2
other positional params: (3, 4, 5)
other named params: {'param3': 6, 'param4': 7, 'param5': 8}

Давайте теперь попробуем реализовать более полезную функцию, в которую можно передавать произвольное число аргументов. Например, пусть эта функция вычисляет некоторую бинарную операцию для всех аргументов:

In [58]:
class BinaryOpError(Exception): pass

def calc(op, *operands): 
    if (len(operands) < 2):
        raise BinaryOpError('not enough arguments')
    
    result = operands[0]
    for idx in range(1, len(operands)): # начинаем цикл со второго элемента!
        result = op(result, operands[idx])
    
    return result


# пример использования

result = calc(lambda x, y: x + y,\
              0, 1, 2, 3, 4, 5)
print(result)

result = calc(lambda x, y: x * y,\
              1, 2, 3, 4, 5)
print(result)
15
120

Другие типы коллекций

В этой лекции мы рассмотрели только самые известные и часто используемые коллекции из имеющихся в Python. Упомянем вкратце еще несколько (если какая-то коллекция реализована в модуле, то имя этого модуля также указывается):

  1. bytes - неизменяемая последовательность байтов (аналог str, только для байтов, а не для символов); применяется для работы с двоичными данными
  2. bytearray - изменяемая последовательность байтов; применяется для работы с двоичными данными, когда их к тому же нужно модифицировать
  3. frozenset - неизменяемое множество; применяется для тех же целей, что и обычное, но в виду того, что frozenset неизменяемый тип, может использоваться как элемент множества или ключ в словаре
  4. collections.defaultdict - обычный словарь, но с возможность задать значение по умолчанию для отсутствующих элементов

Вопросы для самоконтроля

  1. Что такое коллекция? Что такое итерируемый тип? Как интерпретатор выполняет цикл for ... in?
  2. Что такое последовательность? Когда их стоит использовать, а когда нет? Какие типичные операции они предоставляют?
  3. Что такое распаковка последовательностей?
  4. Для каких целей стоит использовать различные типы последовательностей?
  5. Что такое множество? Какие операции наиболее эффективно выполняются для него? Какое ограничение накладывается на элементы множества?
  6. Что такое словарь? Чем он похож на множество, а чем отличается? Что такое представление словаря?
  7. В чем разница между поверхностным и глубоким копированием?
  8. Что представляет собой генератор?

Задание

  1. Проведите эксперимент, определяющий, сколько времени занимает поиск элемента в большом списке. Сравните результат с тем, что был получен для множества.
  2. Придумайте и реализуйте свой алгоритм сортировки списка. Сравните время его работы с временем работы list.sort на одних и тех же данных. Для чистоты эксперимента списки должны быть заполнены случайными целыми числами. Их можно сгенерировать с помощью функции randint(a, b) из модуля random, которая возвращает случайное число между a и b.
  3. Реализуйте функцию с переменным числом позиционных аргументов, являющуюся простым аналогом метода format. Эта функция должна принимать в качестве первого аргумента строку, в которой в произвольных местах могут быть указаны заполнители <>, заменяемые в результате на соответствующие позиционные аргументы.