1. Лекция 5

19 октября 2018 г.

Заметили ошибку или есть предложение? Напишите на почту: romansdidnotcrucify@gmail.com

Содержание

Лекция 5
Протоколы
1. Понятие протокола
2. С какими протоколами мы будем работать
Списки
Циклические конструкторы объектов

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 >>> 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. Методы списков

У списков есть несколько интересных методов:

   1 >>> dir(l)
   2 ... 'append', 'clear', 'copy', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']

Которые мы с вами разберём.

3.4.1. append

Метод append позволяет добавлять в конец списка элемент:

   1 >>> l = [1,2,3]
   2 >>> l.append(100500)
   3 >>> l
   4 [1, 2, 3, 100500]
   5

3.4.2. pop

Обратная операция - убрать элемент из конца списка, как со стека - реализована в методе pop:

   1 >>> l.pop()     # pop не только удалит элемент из списка, но и вернёт его по завершении своей работы
   2 100500
   3 >>> l
   4 [1, 2, 3]
   5 >>> l.pop(1)    # pop может в качестве аргумента принимаать индекс элемента, который надо удалить
   6 2
   7 >>> l
   8 [1, 3]
   9

3.4.3. clear

Метод clear позволяет очистить список, т.е. удалить всё его содержимое, при этом сохранив id списка:

   1 >>> l
   2 [1, 2, 3]
   3 >>> id(l)
   4 2117686304520
   5 >>> l.clear()
   6 >>> l
   7 []
   8 >>> id(l)
   9 2117686304520
  10

Другой способ очистить список, не меняя его id - воспользоваться заменой сечения на пустой список:

   1 >>> l = [1,2,3]
   2 >>> l
   3 [1, 2, 3]
   4 >>> id(l)
   5 2117686304520
   6 >>> l[:] = []    # Слева - не маленький баян, а сечение списка от начала и до конца
   7 >>> l
   8 []
   9 >>> id(l)
  10 2117686304520
  11

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 (что подразумевает рекурсивный обход последовательности):

   1 >>> import copy
   2 >>> l
   3 [[100500, 2, 3], [4, 5, 6]]
   4 >>> t = copy.deepcopy(l)    # Сравните с примером, приведённым выше
   5 >>> t[0] is l[0]
   6 False
   7 >>> t[0][0] = 1912
   8 >>> t
   9 [[1912, 2, 3], [4, 5, 6]]
  10 >>> l
  11 [[100500, 2, 3], [4, 5, 6]]
  12

3.4.5. count

Метод count выполняет подсчёт количества вхождений элемента в список:

   1 >>> l = [7,95,6,7,"QQ", 7, 7]
   2 >>> l.count(7)
   3 4
   4

3.4.6. extend

Метод extend, как и append, позволяет расширить список; но теперь уже не на один элемент, а на целую последовательность:

   1 >>> l = [1,2,3]
   2 >>> l.extend(range(10))
   3 >>> l
   4 [1, 2, 3, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
   5

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 позволяет найти и удалить первое вхождение элемента в список:

   1 >>> l = [1,2,3,4,5,5,5,6,7]
   2 >>> l.remove(5)
   3 >>> l    # Из списка была удалена первая пятёрка 
   4 [1, 2, 3, 4, 5, 5, 6, 7] 
   5 >>> l.remove(10)    # remove может и не найти значения
   6 Traceback (most recent call last):
   7   File "<stdin>", line 1, in <module>
   8 ValueError: list.remove(x): x not in list

3.4.10. legacy-методы: reverse и sort

Оставшиеся два метода, которые мы не рассмотрели - это такое legacy.

Метод reverse переворачивает список:

   1 >>> l
   2 [1, 2, 3, 4, 5, 5, 6, 7]
   3 >>> l.reverse()
   4 >>> l
   5 [7, 6, 5, 5, 4, 3, 2, 1]
   6

Метод 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(), итератор, с помощью которого можно пройтись от конца списка к началу:

   1 >>> l
   2 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
   3 >>> reversed(l)    # Вернёт, в отличие от l.reverse(), итератор
   4 <list_reverseiterator object at 0x0000027628625AC8>
   5 >>> print(*reversed(l))    # В качестве параметров функции будет передан результат распаковки списка
   6 10 9 8 7 6 5 4 3 2 1 0
   7

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 * 2 + 1 for i in range(10) if i != 6]    # Добавим ещё фильтр в конец, и в наш список не попадёт число 13:
   2 [1, 3, 5, 7, 9, 11, 15, 17, 19]
   3

Наконец, циклические конструкторы объектов могут быть вложенными:

   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)

LecturesCMC/PythonIntro2018/05_Lists/Conspect (последним исправлял пользователь RomanKrivonogov 2018-10-30 22:57:30)