1. Лекция 5
19 октября 2018 г.
Заметили ошибку или есть предложение? Напишите на почту: romansdidnotcrucify@gmail.com
2. Протоколы
Я сделаю, возможно, ранний заход - расскажу о понятии протокола в питоне.
2.1. Понятие протокола
Мы помним, что питон - язык со строгой динамической (утиной) типизацией. Это означает, например, что для того, чтобы объект был индексируемым, необходимо и достаточно, чтобы у него присутствовал метод __getitem__:
1 >>> a = 1,2,3 # У кортежа
2 >>> dir(a) # Метод __getitem__ есть
3 ['__add__', '__class__', '__contains__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__getnewargs__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__rmul__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', 'count', 'index']
4 >>> a[0] # Поэтому любой кортеж - индексируемый объект
5 1
6
Обращаю внимание, что достаточно именно наличия у объекта метода __getitem__, что бы он на самом деле ни делал. Забегая вперёд, продемонстрирую это:
1 >>> class C: # Создадим класс, у которого опишем метод __getitem__
2 ... def __getitem__(self, *args): # Звёздочка здесь - пресловутый плейсхолдер, указание на то, что приезжающие в качестве аргументов объекты, сколько бы их ни было - это один кортеж
3 ... return 100500 # При вызове __getitem__ просто вернуть 100500
4 ...
5 >>> c = C() # Объект только что описанного нами класса
6 >>> c[2] # К которому применима операция индексирования
7 100500
8 >>> c[-2077] # При этом мы описали метод так, что ему можно передавать в качестве индекса любую чушь
9 100500
10 >>> c["assdf"] # Даже так
11 100500
12
Понятно, что подобное поведение объекта - довольно глупая штука, поэтому помимо собственно наличия метода в питоне есть ещё некоторые требования относительно того, что должно получаться в результате работы метода; какими свойствами метод должен обладать.
Совокупность тех методов и их свойств, которыми должен обладать объект, и составляет понятие "протокола" в питоне (по сути это "общепринятое соглашение"). Это понятие не очень формальное; некоторые из протоколов описаны в питоновской документации, обычно на уровне реализации на C.
2.2. С какими протоколами мы будем работать
Для нас с вами интересно следующее:
Итератор - это такая штука, которая имеет метод __next__ и (возможно, но не обязательно) возвращает исключение StopIteration;
Последовательность (sequence) должна иметь метод __getitem__ и ещё дополнительно может иметь большое количество необязательных операций (сложение, умножение, изменение и т.п.);
Для участия объекта в правой части цикла for из него должно быть возможно изготовить итератор, т.е. он должен иметь метод __iter__ и/или __getitem__;
Есть и разные другие интересные протоколы, например, протокол числа (number protocol), подразумевающий наличие у объекта, считающегося числом, большого количества разнообразных арифметических операций с определёнными свойствами.
Протоколы могут быть довольно сложными; например, умножение последовательности на число:
1 >>> s = "oraora" # Возьмём строку
2 >>> s * 8 # Мы уже знаем, что в операции умножения на число она может стоять как слева
3 'oraoraoraoraoraoraoraoraoraoraoraoraoraoraoraora'
4 >>> 8 * s # Так и справа
5 'oraoraoraoraoraoraoraoraoraoraoraoraoraoraoraora'
6 >>> dir(s) # В первом случае на самом деле вызывается метод строки __mul__
7 ['__add__', '__class__', '__contains__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__getnewargs__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mod__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__rmod__', '__rmul__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', 'capitalize', 'casefold', 'center', 'count', 'encode', 'endswith', 'expandtabs', 'find', 'format', 'format_map', 'index', 'isalnum', 'isalpha', 'isdecimal', 'isdigit', 'isidentifier', 'islower', 'isnumeric', 'isprintable', 'isspace', 'istitle', 'isupper', 'join', 'ljust', 'lower', 'lstrip', 'maketrans', 'partition', 'replace', 'rfind', 'rindex', 'rjust', 'rpartition', 'rsplit', 'rstrip', 'split', 'splitlines', 'startswith', 'strip', 'swapcase', 'title', 'translate', 'upper', 'zfill']
8 >>> s.__mul__(8) # Напоминаю - в байткоде на питоне операций как таковых нет, есть только методы объектов; операции - это синтаксический сахар
9 'oraoraoraoraoraoraoraoraoraoraoraoraoraoraoraora'
10 >>> a = 8 # Как тогда работает умножение 8 * s? Вызывается метод __mul__ от числа? И что, он должен поддерживать все возможные объекты, которые нам захочется умножить на число?
11 >>> a.__mul__(s) # Нет; тогда как работает правое умножение объекта на число? По протоколу, если у объекта не реализован метод __mul__ с соответствующим операндом, возвращается объект NotImplemented
12 NotImplemented
13 >>> type(NotImplemented) # Имеющий, иронично, тип NotImplementedType
14 <class 'NotImplementedType'>
15 >>> dir(s) # И вот если при попытке вызвать __mul__ от первого операнда возвращается значение NotImplemented, проверяется, нет ли у второго операнда метода, задающего правое умножение на него - __rmul__
16 ['__add__', '__class__', '__contains__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__getnewargs__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__iter__', '__le__', '__len__', '__lt__', '__mod__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__rmod__', '__rmul__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', 'capitalize', 'casefold', 'center', 'count', 'encode', 'endswith', 'expandtabs', 'find', 'format', 'format_map', 'index', 'isalnum', 'isalpha', 'isdecimal', 'isdigit', 'isidentifier', 'islower', 'isnumeric', 'isprintable', 'isspace', 'istitle', 'isupper', 'join', 'ljust', 'lower', 'lstrip', 'maketrans', 'partition', 'replace', 'rfind', 'rindex', 'rjust', 'rpartition', 'rsplit', 'rstrip', 'split', 'splitlines', 'startswith', 'strip', 'swapcase', 'title', 'translate', 'upper', 'zfill']
17 >>> s.__rmul__(8) # У строки __rmul__ есть, и поэтому выражение 8 * s работает именно как s.__rmul__(8)
18 'oraoraoraoraoraoraoraoraoraoraoraoraoraoraoraora'
19
Когда поговорим про объектную модель, сможем задавать подобное поведение и самостоятельно.
3. Списки
3.1. Связь с кортежами
Мы с вами уже говорили про кортежи и выяснили, что кортеж - это такой массив связей имён с объектами; таблица ссылок на соответствующие объекты питона. В зависимости от реализации интерпретатора, это даже может быть буквально массив с адресами объектов в памяти.
Список, как мы уже видели в некоторых примерах, задаётся квадратными скобочками [] и имеет ту же самую структуру - это тоже массив в памяти:
1 >>> a = ("eggs", "spam", "UFO") # Кортеж
2 >>> type(a)
3 <class 'tuple'>
4 >>> b = ["eggs", "spam", "UFO"] # Список
5 >>> type(b)
6 <class 'list'>
7 >>> a[0] # Операцию индексирования поддерживают и кортеж (это же массив, верно?)
8 'eggs'
9 >>> b[1] # И список
10 'spam'
11 >>> a[:2] # То же самое с операцией секционирования
12 ('eggs', 'spam')
13 >>> b[:2]
14 ['eggs', 'spam']
15 >>> len(a) # И кортеж, и список имеют определённую длину
16 3
17 >>> len(b) # Словом, массивы как массивы
18 3
19
Однако есть между ними и важное отличие: кортеж - неизменяемый тип данных, а список - изменяемый:
1 >>> a[0] = "timetravelling spam" # С кортежами такое не пройдёт
2 Traceback (most recent call last):
3 File "<stdin>", line 1, in <module>
4 TypeError: 'tuple' object does not support item assignment
5 >>> b[0] = "timetravelling spam" # А со списками - сколько угодно
6 >>> b[0]
7 'timetravelling spam'
8
3.1.1. Изменяемые объекты
Изменяемые объекты - это целая отдельная тема. Для изменяемого объекта мы не можем утверждать, что, если идентификатор объекта остался прежним, сам объект не изменился (в отличие от строк, кортежей, чисел и т.д.):
1 >>> a = [1,2,3,4,56,7,8,9]
2 >>> a
3 [1, 2, 3, 4, 56, 7, 8, 9]
4 >>> b = a
5 >>> b is a # Необязательно было вводить второе имя для a, но это позволит продемонстрировать лишний раз разницу между именем объекта и самим объектом
6 True
7 >>> id(a) # Для неизменяемых объектов (кортежи, строки, числа) идентификатор однозначно соответствует не только месту в памяти, но и содержимому объекта
8 2117686282376
9 >>> id(b)
10 2117686282376
11 >>> a[3] = "QQ" # К слову, списки тоже могут хранить значения разных типов - это объясняется тем, что и кортеж, и список - всего лишь массив "указателей" (не в строгом C-шном смысле) на объекты
12 >>> a
13 [1, 2, 3, 'QQ', 56, 7, 8, 9]
14 >>> b
15 [1, 2, 3, 'QQ', 56, 7, 8, 9]
16 >>> id(a) # Для изменяемого же объекта идентификатор остался прежним, хотя содержимое поменялось
17 2117686282376
18 >>> id(b)
19 2117686282376
20 >>> b[5] = "QKRQ" # Идентификатор и здесь не поменяется
21 >>> id(a)
22 2117686282376
23 >>> id(b)
24 2117686282376
25 >>> a
26 [1, 2, 3, 'QQ', 56, 'QKRQ', 8, 9]
27 >>> b
28 [1, 2, 3, 'QQ', 56, 'QKRQ', 8, 9]
29
В этом плане список очень похож на массив в других языках программирования, с той лишь разницей, повторяю, что это массив связей имён с объектами, а не непосредственно объектов.
3.2. Вставка вместо сечения
Помимо отдельных элементов списка, мы можем заменять и удалять целые секции (срезы):
1 >>> l = list("QWERTYISANICEFISH") # Кстати, обратите внимание как из строки - т.е. последовательности - создался список
2 >>> l
3 ['Q', 'W', 'E', 'R', 'T', 'Y', 'I', 'S', 'A', 'N', 'I', 'C', 'E', 'F', 'I', 'S', 'H']
4 >>> l[1:3] = [7,7,7,7,7] # Эта операция сначала удаляет элементы списка, соответствующие указанному срезу, а затем распаковывает последовательность в правой части, поэлементно добавляя её в список вместо удалённых элементов
5 >>> l # Как видите, длина удалённой подпоследовательности не обязана совпадать с длиной вставляемой подпоследовательности
6 ['Q', 7, 7, 7, 7, 7, 'R', 'T', 'Y', 'I', 'S', 'A', 'N', 'I', 'C', 'E', 'F', 'I', 'S', 'H']
7 >>> l[4:6] = "JACKPOT!" # Причём в правой части не обязан быть список; это может быть произвольная последовательность, которая, как уже было сказано, будет распакована
8 >>> l
9 ['Q', 7, 7, 7, 'J', 'A', 'C', 'K', 'P', 'O', 'T', '!', 'R', 'T', 'Y', 'I', 'S', 'A', 'N', 'I', 'C', 'E', 'F', 'I', 'S', 'H']
10 >>> l[12:] = range(9) # Вычислимая последовательность тоже может стоять в правой части
11 >>> l
12 ['Q', 7, 7, 7, 'J', 'A', 'C', 'K', 'P', 'O', 'T', '!', 0, 1, 2, 3, 4, 5, 6, 7, 8]
13
Обратите внимание: то, что стоит в левой части операции присваивания - вовсе не список; это такая специальная конструкция, которая говорит "пожалуйста, замените элементы списка с такими-то индексами на элементы последовательности в правой части".
В питоне, как и во многих языках программирования, выражение в левой части операции присваивания (lvalue) - это совсем не то же самое, что выражение в правой (rvalue).
Дальше - больше. Вы можете манипулировать сечениями с шагом. Единственное требование: длина того, что стоит справа в операции присваивания, должна совпадать с длиной того, что стоит слева1:
1 >>> l[11:1:-2] = 100,200,300,400,500 # Заменить элементы, проходя с конца, начиная с 11-го и до 1-го не включая его, на элементы кортежа
2 >>> l # Количество элементов совпало, всё работает
3 ['Q', 7, 7, 500, 'J', 400, 'C', 300, 'P', 200, 'T', 100, 0, 1, 2, 3, 4, 5, 6, 7, 8]
4 >>> l[11:1:-2] = 100,200,300,400,500,600 # Количество элементов не совпадает, трюк не пройдёт
5 Traceback (most recent call last):
6 File "<stdin>", line 1, in <module>
7 ValueError: attempt to assign sequence of size 6 to extended slice of size 5
3.3. Под капотом
Что такое кортеж в памяти, мы понимаем: массив из N элементов - связей с объектами, хранится где-то в памяти, размер постоянный.
Но как хранится в памяти список, длина которого не строго фиксирована и может значительно увеличиться или уменьшиться?
В питоне при заведении списка память выделяется в размере, кратном некоторому числу (восьми, кажется, если мне память не изменяет). Если вам этого хватило - отлично; если нет - происходит перевыделение памяти, и размер выделенной под список памяти кратно увеличивается. Обычно довольно быстро наступает одно из двух: либо вам начинает хватать памяти, и больше она не перевыделяется, либо на вашей машине заканчивается память.
Поэтому, когда мы говорим, что операция изменения списка - скажем, добавление элементов в конец - имеет константную сложность, мы кривим душой: сложность константная, если у вас ещё осталось выделенное, но не использованное списком место.
В некоторых случаях помимо самой операции происходит, как уже было сказано, перераспределение памяти. При этом:
- чем больше размер вашего списка, тем более редкое это явление (если, конечно, скорость потребления вами памяти не растёт экспоненциально);
- перераспределение памяти иногда происходит и при сокращении списка (когда в вашем списке останется достаточно мало элементов).
На практике накладные расходы (overhead) от изменения размера списка - вещь редко возникающая, и по этому поводу можно практически не беспокоиться.
Важный момент: id объекта не меняется при перераспределении памяти.
3.4. Методы списков
У списков есть несколько интересных методов:
Которые мы с вами разберём.
3.4.1. append
Метод append позволяет добавлять в конец списка элемент:
3.4.2. pop
Обратная операция - убрать элемент из конца списка, как со стека - реализована в методе pop:
3.4.3. clear
Метод clear позволяет очистить список, т.е. удалить всё его содержимое, при этом сохранив id списка:
Другой способ очистить список, не меняя его id - воспользоваться заменой сечения на пустой список:
3.4.4. copy
Метод copy позволяет, как нетрудно догадаться, сделать копию объекта:
1 >>> l = [1,2,3]
2 >>> id(l)
3 2117686305736
4 >>> t = l # Так мы никакого нового объекта с тем же содержимым не создали; t - лишь дополнительное имя, указывающее на всё тот же объект
5 >>> id(t)
6 2117686305736
7 >>> t = l.copy() # А вот так имя t будет связано уже с другим объектом, хоть и имеющим точно такое же содержимое, как у l
8 >>> l
9 [1, 2, 3]
10 >>> t
11 [1, 2, 3]
12 >>> id(t)
13 2117686304520
14 >>> t is l
15 False
16
Ирония в том, что, хоть объекты-спики t и l в примере выше разные, элементы, составляющие их содержимое - это буквально одни и те же объекты (помните, что список - это массив связей с объектами, "указателей" на объекты, а не самих объектов?):
1 >>> l = [[1,2,3], [4,5,6]] # Возьмём список списков
2 >>> t = l.copy()
3 >>> t is l # Сами списки списков - разные
4 False
5 >>> t[0] is l[0] # Но вот элементы этих "списков списков" остались всё теми же объектами
6 True
7 >>> t[0][0] = 100500 # Что может дать иногда неожиданный результат
8 >>> t # t и l - разные объекты, а зависимость между ними осталась
9 [[100500, 2, 3], [4, 5, 6]]
10 >>> l
11 [[100500, 2, 3], [4, 5, 6]]
12
Причина, по которой copy по умолчанию выполняет лишь поверхностное копирование - в сложности глубокого копирования (элемент списка может оказаться списком, элемент которого может оказаться списком... И вот всё это надо было бы копировать, не всегда понятно зачем).
3.4.4.1. Если хочется глубокого копирования
Хотите глубокого копирования - используйте модуль copy (что подразумевает рекурсивный обход последовательности):
3.4.5. count
Метод count выполняет подсчёт количества вхождений элемента в список:
3.4.6. extend
Метод extend, как и append, позволяет расширить список; но теперь уже не на один элемент, а на целую последовательность:
3.4.7. index
Метод index позволяет найти индекс первого вхождения элемента в список (первого в некотором диапазоне индексов):
1 >>> l = [1, 7, 2, 7, 3, 7, 7, 7, 8, 7]
2 >>> l.index(7) # Индекс первого вхождения семёрки
3 1
4 >>> l.index(7, 2) # Индекс первого вхождения семёрки среди элементов с индексом, не меньшим 2
5 3
6 >>> l.index(7, 0, 1) # Индекс первого вхождения семёрки среди элементов с индексами от 0 до 1, не включая последний
7 Traceback (most recent call last):
8 File "<stdin>", line 1, in <module>
9 ValueError: 7 is not in list
3.4.8. insert
Метод insert позволяет вставить по указанному индексу подпоследовательность в список:
1 >>> l
2 [1, 7, 2, 7, 3, 7, 7, 7, 8, 7]
3 >>> l.insert(3, [5,5,5]) # Вставить подпоследовательность в последовательность так, чтобы её начало имело индекс 3
4 >>> l # При такой вставке, кстати, никакие элементы не удаляются
5 [1, 7, 2, [5, 5, 5], 7, 3, 7, 7, 7, 8, 7]
6 >>> l.pop(3)
7 [5, 5, 5]
8 >>> l
9 [1, 7, 2, 7, 3, 7, 7, 7, 8, 7]
10 >>> l[3:4] = [5,5,5] # В отличие от вставки подпоследовательности с помощью среза
11 >>> l
12 [1, 7, 2, 5, 5, 5, 3, 7, 7, 7, 8, 7]
13
3.4.9. remove
Метод remove позволяет найти и удалить первое вхождение элемента в список:
3.4.10. legacy-методы: reverse и sort
Оставшиеся два метода, которые мы не рассмотрели - это такое legacy.
Метод reverse переворачивает список:
Метод sort список сортирует:
1 >>> l = [1,0,0,5,0,0]
2 >>> l.sort()
3 >>> l
4 [0, 0, 0, 0, 1, 5]
5 >>> l[2] = "QQ" # Но работает он только если все элементы списка между собой сравнимы
6 >>> l.sort()
7 Traceback (most recent call last):
8 File "<stdin>", line 1, in <module>
9 TypeError: '<' not supported between instances of 'str' and 'int'
Интересное отличие от C++: в функцию sort в качестве параметра передаётся не компаратор, выполняющий, скажем, сравнение "a > b", а функция для вычисления некоторого ключа; а уже потом именно по значениям ключей будет произведена сортировка.
1 >>> l = [0,1,2,3,4,5,6,7,8,9,10]
2 >>> def kk(i): return i % 5 # Определим функцию, вычисляющую значение ключа
3 ...
4 >>> sorted(l, key=kk) # sorted(l) делает то же, что и l.sort(), только вернёт новый отсортированный список, а не отсортирует старый
5 [0, 5, 10, 1, 6, 2, 7, 3, 8, 4, 9]
6 >>> l
7 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
8
Кстати, sorted всегда будет возвращать список, хотя на вход может принимать и другие последовательности (range, например).
Так же, как .sort() сортирует сам список, а sorted() - создаёт отсортированную копию, функция reversed() вернёт нам, в отличие от .reverse(), итератор, с помощью которого можно пройтись от конца списка к началу:
3.4.11. Операции с присваиванием
Как мы уже упомянули вскользь, при изменении изменяемого объекта содержимое объекта меняется, но сам объект - нет (имеется в виду, что его id остаётся тем же самым):
1 >>> l
2 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
3 >>> id(l)
4 2706506948424
5 >>> l = l + [11, 12, 13] # Мы просим: возьми объект, с которым связано имя l, возьми объект [1,2,3], сложи их и результат назови l
6 >>> id(l) # Поэтому id объекта, очевидно, поменяется
7 2706506926664
8 >>> l += [14, 15, 16] # Но вот операции с присваиванием содержимое изменяемого объекта меняют, а его id - нет
9 >>> id(l)
10 2706506926664
11
Подобное поведение обусловлено наличием у списков специальных методов, задающих сложение и умножение с присваиванием - __iadd__ и __imul__.
3.5. Вычислительная сложность операций со списками
Давайте поговорим о том, как внутреннее устройство списка определяет стоимость операций с ним; какие операции быстрые, а какие - медленные.
В дальнейшем разговоре опустим worst-case случай, т.е. считаем, что перераспределения памяти не происходит (как мы уже выяснили, это действительно не столь частое явление).
3.5.1. Константный стек, линейный список
Т.к. добавление элемента в конец списка - всего лишь увеличение счётчика его элементов и занесение записи в последнюю ячейку, операция добавления элемента в конец списка имеет константную сложность. Точно так же сложность операции удаления последнего элемента списка тоже константная.
Но вот если вы добавляете что-то в начало списка (или удаляете что-то), вам придётся сдвигать в памяти уже имеющиеся в массиве ссылки (помните, что список - всего лишь массив ссылок на объекты?), поэтому операции вставки в список (не в его конец) и удаления из него имеют линейную сложность.
Получается, что со списком можно эффективно работать как со стеком, но в других операциях мы получим в среднем линейную сложность.
3.5.2. Нужны ли "linked list"-списки в питоне?
Возникает вопрос: нужны ли в питоне списки в другом, уже известном нам из курса алгоритмов и структур данных, смысле?
Давайте сравним сложность операций в динамических списках питона (назовём их динамическими списками) и в связных списках (назовём их "linked list"-списками):
Индексация: в динамических списках имеет константную сложность (просто взять адрес начала массива и прибавить смещение), в "linked list"-списках - линейную;
Поиск: в списках обоих типов имеет линейную сложность (нужно пройтись по списку последовательно);
Вставка перед данным элементом списка: в динамических списках имеет линейную сложность, а вот в "linked list"-списках - константную;
Вставка/удаление из начала/конца списка: константная сложность и для динамических, и для "linked list"-списков.
Таким образом, единственная ситуация, когда "linked list"-списки оказываются выгоднее - это когда нужно вставить/удалить элемент из определённого уже известного нам места списка.
А теперь вопрос.
Откуда мы знаем это самое место списка?
Узнаём ли мы его с помощью поиска, либо с помощью индексации - всё равно получается, что и в "linked list"-списках вставка/удаление элемента из произвольного места списка имеет линейную сложность.
Таким образом, питоновских списков более чем достаточно для работы, и потребности вводить списки в "linked list"-смысле нет.
3.5.2.1. deque
Единственная распространённая абстракция такого рода, которую невозможно эффективно моделировать с помощью списка - это двухсторонняя очередь:
1 >>> import collections # Доступна она через специальный модуль collections, описывающий несколько распространённых контейнеров
2 >>> d = collections.deque() # deque - double-ended queue
3 >>> d
4 deque([])
5 >>> d.append(000) # Можно добавлять элементы как справа
6 >>> d
7 deque([0])
8 >>> d.appendleft(79) # Так и слева
9 >>> d
10 deque([79, 0])
11 >>> d.appendleft(30)
12 >>> d.pop() # Удалять, соответственно, тоже: справа
13 0
14 >>> d
15 deque([30, 79])
16 >>> d.popleft() # Слева
17 30
18 >>> d
19 deque([79])
20
3.6. Имитация многомерных массивов с помощью списков
В питоне есть модули (numpy, например), которые реализуют настоящие в математическом смысле матрицы, многомерные массивы; однако в наших домашних заданиях обычно можно обойтись и простой их имитацией:
1 >>> a = [[1,2,3,4,5,], # Обратите внимание, я ставлю после каждого элемента списка, даже после последнего, запятую
2 ... [2,3,4,5,6,], # (это т.н. trailing comma - адекватным переводом на русский будет что-то вроде "хвостовая запятая")
3 ... [5,3,2,1,0,], # Это распространённая практика, позволяющая в дальнейшем при добавлении или удалении элементов в списке/кортеже в исходном коде
4 ... ] # не думать о том, нужно ли добавлять или убирать запятую или нет
5 >>> a
6 [[1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [5, 3, 2, 1, 0]]
7 >>> a[0][0] # Операция индексации вполне себе работает (первый индекс - номер строки, второй - номер столбца)
8 1
9 >>> a[2][3]
10 1
11 >>> import pprint # Для печати таких массивов можно использовать специальную функцию из модуля pprint (от "pretty print" - красивый вывод)
12 >>> a *= 2 # Наш массив слишком маленький, для демонстрации сделаем его побольше
13 >>> pprint.pprint(a) # Красивый вывод
14 [[1, 2, 3, 4, 5],
15 [2, 3, 4, 5, 6],
16 [5, 3, 2, 1, 0],
17 [1, 2, 3, 4, 5],
18 [2, 3, 4, 5, 6],
19 [5, 3, 2, 1, 0]]
20 >>> print(a) # Для сравнения, некрасивый вывод
21 [[1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [5, 3, 2, 1, 0], [1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [5, 3, 2, 1, 0]]
22 >>> a[2][1] = 0 # Это не массивы в полном смысле этого слова; например, операция матричного умножения "@" к ним не применима;
23 >>> pprint.pprint(a) # Однако получать и изменять элементы по индексу можно, и этого достаточно для некоторых ситуаций
24 [[1, 2, 3, 4, 5],
25 [2, 3, 4, 5, 6],
26 [5, 0, 2, 1, 0],
27 [1, 2, 3, 4, 5],
28 [2, 3, 4, 5, 6],
29 [5, 0, 2, 1, 0]]
30
Единственный недостаток питоновских списков - вы не можете задать список заранее известного размера. С этим связаны интересные подводные камни:
1 >>> a = [0] * 100 # Для одномерного списка можно обойтись таким трюком
2 >>> a
3 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
4 >>> a[0] = 1
5 >>> a # Получился нормальный список из 100 элементов
6 [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
7 >>> a = [[0] * 8] * 8 # А вот попробуем теперь аналогичным образом создать двумерный масссив 8 x 8
8 >>> pprint.pprint(a) # Видите подвох?
9 [[0, 0, 0, 0, 0, 0, 0, 0],
10 [0, 0, 0, 0, 0, 0, 0, 0],
11 [0, 0, 0, 0, 0, 0, 0, 0],
12 [0, 0, 0, 0, 0, 0, 0, 0],
13 [0, 0, 0, 0, 0, 0, 0, 0],
14 [0, 0, 0, 0, 0, 0, 0, 0],
15 [0, 0, 0, 0, 0, 0, 0, 0],
16 [0, 0, 0, 0, 0, 0, 0, 0]]
17 >>> a[0][1] = "QQ"
18 >>> pprint.pprint(a) # А он есть
19 [[0, 'QQ', 0, 0, 0, 0, 0, 0],
20 [0, 'QQ', 0, 0, 0, 0, 0, 0],
21 [0, 'QQ', 0, 0, 0, 0, 0, 0],
22 [0, 'QQ', 0, 0, 0, 0, 0, 0],
23 [0, 'QQ', 0, 0, 0, 0, 0, 0],
24 [0, 'QQ', 0, 0, 0, 0, 0, 0],
25 [0, 'QQ', 0, 0, 0, 0, 0, 0],
26 [0, 'QQ', 0, 0, 0, 0, 0, 0]]
27 >>> # Это из-за того, что мы, по сути, захотели список из 8 объектов "список из 8 нулей", только не учли, что используется неглубокое копирование
28 >>> # (ведь список - лишь массив ссылок на объекты, вот эти ссылки на одни и те же 8 объектов-нулей и были скопированы в каждую из "строк" матрицы)
4. Циклические конструкторы объектов
Для ликвидации этой проблемы (и для многих других целей) в питоне есть т.н. циклические конструкторы объектов:
1 >>> a = [i * 2 + 1 for i in range(10)] # Синтаксис для циклического конструктора списков следующий: в квадратных скобках указывается сначала выражение, которое будет элементом списка,
2 >>> a # затем, после for - переменные, по которым будем проходить (их может быть более одной, как и в цикле), а после in - последовательность, по которой нужно осуществить проход
3 [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
4 >>> a = (i * 2 + 1 for i in range(10)) # У списков и многих других типов объектов циклический конструктор есть, а вот у кортежей - нет
5 >>> a # Получили не кортеж, а генератор (впрочем, для всё той же последовательности элементов)
6 <generator object <genexpr> at 0x00000276285F4C50>
7 >>> a = tuple(i * 2 + 1 for i in range(10)) # Однако кортеж можно получить с помощью явного преобразования
8 >>> a
9 (1, 3, 5, 7, 9, 11, 13, 15, 17, 19)
10 >>> a = [[0] * 8 for i in range(8)] # С помощью циклического конструктора можно создать тот многомерный массив, который у нас не получилось создать через операцию умножения
11 >>> pprint.pprint(a)
12 [[0, 0, 0, 0, 0, 0, 0, 0],
13 [0, 0, 0, 0, 0, 0, 0, 0],
14 [0, 0, 0, 0, 0, 0, 0, 0],
15 [0, 0, 0, 0, 0, 0, 0, 0],
16 [0, 0, 0, 0, 0, 0, 0, 0],
17 [0, 0, 0, 0, 0, 0, 0, 0],
18 [0, 0, 0, 0, 0, 0, 0, 0],
19 [0, 0, 0, 0, 0, 0, 0, 0]]
20 >>> a[0][2] = "QQ" # Вот он уже работает в соответствии с нашими ожиданиями
21 >>> pprint.pprint(a)
22 [[0, 0, 'QQ', 0, 0, 0, 0, 0],
23 [0, 0, 0, 0, 0, 0, 0, 0],
24 [0, 0, 0, 0, 0, 0, 0, 0],
25 [0, 0, 0, 0, 0, 0, 0, 0],
26 [0, 0, 0, 0, 0, 0, 0, 0],
27 [0, 0, 0, 0, 0, 0, 0, 0],
28 [0, 0, 0, 0, 0, 0, 0, 0],
29 [0, 0, 0, 0, 0, 0, 0, 0]]
30 >>> [c for c in "QWERTY"] # Разумеется, последовательность в правой части может быть какой угодно
31 ['Q', 'W', 'E', 'R', 'T', 'Y']
32 >>> [(c, i) for c, i in enumerate("QWERTY")]
33 [(0, 'Q'), (1, 'W'), (2, 'E'), (3, 'R'), (4, 'T'), (5, 'Y')]
34
С помощью циклических конструкторов объектов (в данном случае - списков) можно делать разные интересные и полезные штуки:
Наконец, циклические конструкторы объектов могут быть вложенными:
1 >>> [(i,j) for i in range(10, 15) for j in range(0,6)] # Трактовать такой конструктор нужно как цепочку вложенных (слева направо) операторов for
2 [(10, 0), (10, 1), (10, 2), (10, 3), (10, 4), (10, 5), (11, 0), (11, 1), (11, 2), (11, 3), (11, 4), (11, 5), (12, 0), (12, 1), (12, 2), (12, 3), (12, 4), (12, 5), (13, 0), (13, 1), (13, 2), (13, 3), (13, 4), (13, 5), (14, 0), (14, 1), (14, 2), (14, 3), (14, 4), (14, 5)]
3 >>> for i in range(10,15): # По сути, произошло вот это
4 ... for j in range(0,6):
5 ... print((i,j), end=" ")
6 ...
7 (10, 0) (10, 1) (10, 2) (10, 3) (10, 4) (10, 5) (11, 0) (11, 1) (11, 2) (11, 3) (11, 4) (11, 5) (12, 0) (12, 1) (12, 2) (12, 3) (12, 4) (12, 5) (13, 0) (13, 1) (13, 2) (13, 3) (13, 4) (13, 5) (14, 0) (14, 1) (14, 2) (14, 3) (14, 4) (14, 5) >>>
8
Приведём всё-таки ещё пример использования фильтра:
1 >>> a = [(i,j) for i in range (6,12) for j in range(3,8) if i != j] # Все декартовы произведения, кроме тех, которые состоят из одинаковых элементов
2 >>> pprint.pprint(a)
3 [(6, 3),
4 (6, 4),
5 (6, 5),
6 (6, 7),
7 (7, 3),
8 (7, 4),
9 (7, 5),
10 (7, 6),
11 (8, 3),
12 (8, 4),
13 (8, 5),
14 (8, 6),
15 (8, 7),
16 (9, 3),
17 (9, 4),
18 (9, 5),
19 (9, 6),
20 (9, 7),
21 (10, 3),
22 (10, 4),
23 (10, 5),
24 (10, 6),
25 (10, 7),
26 (11, 3),
27 (11, 4),
28 (11, 5),
29 (11, 6),
30 (11, 7)]
31
Циклический конструктор - вещь ОЧЕНЬ полезная и ОЧЕНЬ часто используемая.
Почему здесь появилось это требование? При указании среза с шагом 1 вы просто удаляли несколько подряд идущих элементов и вставляли в то место, где они были, новую подпоследовательность. Если же вы берёте подпоследовательность с шагом, однозначного очевидного решения, как вставлять элементы, если их больше или меньше, чем было удалено, нет. (1)