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

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

• Поля объектов, пространство имён, 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:

• примеры со строками и кортежами
• более подробно — в лекции про итераторы

Кстати,

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

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

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

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

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

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

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

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

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

• in и not in

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

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

• секционирование:
  • отсутствие границ
  • шаг

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

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

  • тип slice

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

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

• Подстрока строки — строка, так что "!@#"[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: CountSort 'Сортировка подчсётом'

   Вводится последовательность пар натуральных чисел, не превышающих 100, последняя строка ввода — пустая. Вывести её в лексикографически отсортированном по возрастанию виде. Дополнительные условия:

   • из составных типов данных можно пользоваться только списками и кортежами (для вывода — строками),
   • целиком последовательность в памяти хранить нельзя!
   Input:

   2, 100
   12, 4
   2, 2
   5, 8
   2, 100
   33, 33
   12, 4

   Output:

   2, 2
   2, 100
   2, 100
   5, 8
   12, 4
   12, 4
   33, 33

2. EJudge: AbsoluteSupreme 'Частичный порядок'

   На вход подаются тройки чисел через запятую, последняя строка ввода — пустая. Между тройками введён частичный порядок: (x₀, x₁, x₂) ≪ (y₀, y₁, y₂), если ∃ i, j, k: (x₀, x₁, x₂) ≠ (yᵢ, yⱼ, yₖ) и x₀ ⩽ yᵢ, x₁ ⩽ yⱼ и x₂ ⩽ yₖ, i≠j≠k. Отсортировать последовательность по убыванию, по возможности не меняя следования элементов: каждая тройка должна быть «не меньше» (т. е. утверждение A ≪ B неверно) следующих за ней. Разрешается использовать устойчивый «тяжёлый» алгоритм сортировки с квадратичной сложностью (например, сортировку выбором).

   • В формулировке присутствует неоднозначность, так что в этом семестре в качестве решения необходимо реализовать описанный ниже неэффективный алгоритм (чуть ли не кубической сложности):

     1. Найти первую тройку, которая не меньше всех остальных
     2. Удалить её из списка и вставить в его начало
     3. Повторить п. п. (1) - (3) над оставшимся фрагментом списка (без вставленного элемента)
   Input:

   7,5,2
   1,7,1
   1,2,3
   12,11,0
   2,3,4
   6,7,8

   Output:

   12, 11, 0
   6, 7, 8
   7, 5, 2
   1, 7, 1
   2, 3, 4
   1, 2, 3

3. EJudge: SpiralDigits 'Цифры по спирали'

   Ввести целые M и N, вывести последовательность 0 1 2 3 4 5 6 7 8 9 0 1 2 3 … в виде спирально (по часовой стрелке, из верхнего левого угла) заполненной таблицы N×M (N строк, M столбцов). Не забываем про то, что M и N могут быть чётными, нечётными и неизвестно, какое больше.

   Input:

   6,5

   Output:

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

4. EJudge: HalfTranspose 'Недостранспонировали'

   Ввели N строк по N целых чисел (для удобства представлены тут цифрами). Полученную матрицу

   • 1234
     5678
     9012
     3456

   попытались «транспонировать на 45° по часовой стрелке» — получилось примерно так:

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

   При этом способе поворота между числами образовались «пустые места» каждое размеров в одно число, размер матрицы увеличился до 2N-1 × 2N-1. Затем все числа «упали на свободные места под ними» — переместились до ближайшей незанятой ячейки:

   •    1
       562
      90173
     3456284

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

   Input:

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

   Output:

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