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

Долг за прошлую лекцию: ленивые вычисления AND и OR

Операции над объектами как совокупность методов

• Поля объектов, пространство имён, dir(), поля-методы и поля-поля

  • Python: это всё «атрибуты»
• Операции — это методы

  • int.__add__(100500, 42) или даже (100500).__add__(42) как 100500+42

  • "строка".__len__() как len("строка")

  • и т. п.
• Понятие протокола

  • Пример: числовой протокол (на Си), на Python

  • Строгая типизация (__mul__() vs __rmul__()) и т. п.

  • Последовательность (например, список или кортеж) — это свойство объекта (нужные методы), т. е. тоже протокол ⇒ любой объект, который этот протокол поддерживает — последовательность 🦆

Цикл for

• Общий вид:

     1 for имена in последовательность:
     2     тело
  

  • имена, а не только имя — распаковка, если элемент последовательности — тоже последовательность

  • break, continue

  • else:

• Примеры со строками и кортежами

• Более подробно — в лекции про итераторы. Если коротко: протокол последовательности гарантирует, что из неё можно изготовить объект-итератор, и именно этот объект и подставляется в правую часть for.

Кстати,

• В конструкции множественного связывания имена = последовательность последовательность любая

  • расширенное множественное присваивание вида «A₀, A₁, …, *А_k, …, A_N = последовательность_из_N+m_элементов»

• Функции all() и any() принимают в качестве параметра последовательность

• …они повсюду!

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

Операции над последовательностями

• Имеют метод последовательность.__getitem__(что-то), что означает последовательность[что-то]

Константные последовательности на примере кортежа

• Умножение на число и сложение

• in и not in

• индексирование, +от конца

• поэлементное лексикографическое сравнение

• секционирование:
  • отсутствие ошибок при выходе за границы
  • шаг

  • умолчания (+чем A[:] отличается от A?)

• как на самом деле работает [] — .__getitem__()

  • тип slice

• .__getitem__(кортеж) — не работает, а в других типах может)

Строка (введение)

• Подстрока строки — строка, так что "!@#"[0][0][0][-1][0][-1]… — сработает и выдаст "!"

• ⇒ Хотя строки и хранимая последовательность, её «элементы» вычисляются

Рассмотрим в отдельной лекции.

Списки — модифицируемые последовательности

Имеют метод .__setitem__()

• .__setitem__(число)

• .__setitem__(slice)

  • вариант с шагом

• Операции над модифицируемыми последовательностями

• циклическая сборка [выражение for имена in последовательность]

  • Что работает почти так:

       1   _=[]
       2   for имена in последовательность:
       3       _.append(выражение)
    

  • и даже [выражение for имена1 in последовательность1 for имена2 in последовательность2 ...]:

       1   _=[]
       2   for имена1 in последовательность1:
       3       for имена2 in последовательность2:
       4           . . .
       5               _.append(выражение)
    

    то есть является декартовым произведением

  • Фильтрующая клауза: [выражение1 for имена in последовательность if выражение2]

       1   _=[]
       2   for имена in последовательность:
       3       if выражение2:
       4         _.append(выражение1)
    

• Список как динамическая таблица (массив ссылок на элементы; размер ссылки в Python всегда одинаковый)

  • Сложность модификации его начала — O(n), а конца — O(1)

  • Реализация динамического массива с геометрическим масштабированием

    • Выделяем N элементов массива

    • Если массив переполняется, удваиваем его размер и копируем все элементы на новое место

    • Если массив опустошается на K% (т. н. «нижний урез»; в Python — на 3/4, кажется), ополовиниваем размер и копируем элементы
  • Оценка сложности:

    • Масштабирование случается не чаще одного на N операций (при постоянном добавлении или постоянном удалении, иначе — реже)

    • Сложность масштабирования (и одной из N операций) — O(N)

    • ⇒ Наихудшая средняя сложность операций с концом списка — 2*O(1) ≈ O(1)

  • Сравнение с linked lists; есть ли разница в эффективности?
    • единственная выгода linked list — это константная сложность вставки/удаления произвольного элемента

    • но алгоритмов, требующих вставки/удаления произвольного элемента без предварительного поиска, кажется (?) нет, а поиск в обоих случаях линейный

• Список как стек, .append(), .pop()

• Работа += на списках

• Другие методы списка

Колоды:

• Востребованный «не последний элемент», искать который не нужно — первый.

  • ⇒ list неэффективен как очередь

• «Колода» / deque (двойная очередь? «колочередь»?)
  • эффективное добавление и в начало, и в конец

  • скорее всего, реализована как кольцевой буфер с геометрическим масштабированием

  • from collectiond import deque

Имитация многомерных структур данных

• «Матрица» как список списков
  • Равенство размеров всех элементов списка?

• (есть array, NumPy и т. д)

Соиспользование связанных объектов

Отсутствие «подковёрного» копирования

• например, это совсем не матрица: [[0] * N] * M — почему? ☺

• a.copy(), a[:] и copy.deepcopy()

Вычислимые последовательности

Значения не хранятся, а вычисляются .__getitem__()-ом

• range (индексируемая!)

  • range(stop) / range(start, stop[, step])

  • «Классический» for i in range(N):

• enumerate

• ещё есть sorted(), но оно возвращает список

Д/З

Напоминалка:

• Если перейти по ссылке, откроется более полная формулировка задания с советами и подсказками
• Подсказки-спойлеры изначально не видны, они открываются, если нажать в шапке страницы меню «комментарии». Обычно в спойлерах излагается алгоритм решения — всё-таки у нас тут не олимпиада ☺

• Любителям «парковки на слух»: всего попыток в турнире 200, а задач примерно 40 — шлите решение, только если уже оттестировали его и уверены, что оно правильное!

Собственно задание:

0. Прочитать и прощёлкать тьюториал (и про цикл for)

   • Операции над последовательностями

   • Операции над модифицируемыми последовательностями

1. EJudge: HiddenSeq 'Скрытая последовательность'

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

   Input:

   1, 0, 3, 3
   9, 1, 19, 17, 0, 17, 17, 3, 9, 16, 3, 16, 10, 15, 11, 13

   Output:

   YES

2. EJudge: TwoDecks 'Тасуем карты'

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

   • Условие: пользоваться внешними процедурами сортировки (например, функцией sorted() или методом .sort()) в этой задаче запрещено.

   Input:

   5, 5, 5, 4, 2, 9, 0, 10, 15, 0

   Output:

   0 0 2 4 5 5 5 9 10 15

   (₃, ₂, 5, ₁, 6, 7) -> ₁, ₂, ₃, 5, 6, 7

3. EJudge: TransposeTriangle 'Транспонирование треугольника'

   Вводятся последовательности из 1, 2, 3, …, N чисел из диапазона 0…9 через запятую (конец ввода — пустая строка). Ввод оформлен в виде треугольника со стороной N. Повернуть треугольник на 60 градусов против часовой стрелки: вывести эту же последовательность, используя в качестве основания левую сторону. Для красоты можно декорировать начало строки пробелами (это не обязательно; а вот «, » между числами обязательно).

   Input:

      1
     5, 8
    9, 2, 3
   7, 1, 3, 6

   Output:

      6
     3, 3
    8, 2, 1
   1, 5, 9, 7

4. EJudge: FourSquares 'Четыре квадрата'

   Известно, что любое натуральное число можно представить в виде суммы не более чем четырех квадратов неотрицательных целых чисел (теорема Лагранжа). Ввести натуральное N⩽100000 и найти для него такие целые неотрицательные x,y,z и t, чтобы x²+y²+z²+t²=N. Вывести все такие четвёрки в следующем формате: x,y,z и t — через пробел, и упорядочены по убыванию, а сами четвёрки — лексикографически по возрастанию (без повторений).

   Input:

   100

   Output:

   5 5 5 5
   7 5 5 1
   7 7 1 1
   8 4 4 2
   8 6 0 0
   9 3 3 1
   10 0 0 0