Массивы, они же списки

Замечание: В других языках программирования (например, в Си или C++) слово «список» обозначает довольно сложную в обхождении структуру данных, полное название которой — «связный список», он же linked list. В Python она не используется практически никогда, и термин «список» фактически обозначает «динамический массив»

О массивах вообще

• Одна большая оперативная память на всю программу — ячейки и адреса
• Доступ к ячейке — по адресу (фактически — адреса вместо имён)
• Строка: последовательность ячеек

• адрес n-го элемента строки = адрес начала строки + n

• То же самое — для последовательностей любого одного типа:

  • Должны лежать строго подряд в памяти

  • Если один элемент занимает k ячеек, адрес n-го элемента = начало + n * k

• До и после массива в памяти тоже может что-нибудь быть, поэтому менять его размер нельзя

Это и есть массив!

Python:

• всевозможные проверки (на выход за пределы, например)
• возможность менять размер массива
  • свободное место + копирование/удвоение, если оно закончилось
• возможность хранить в нём произвольные данные (а не только однотипные)
  • в массиве хранятся только идентификаторы объектов (они однотипные!), а сами объекты хранятся где ни попадя
  • эта структура обычно называется «таблица ссылок» но так только хуже понимать)
Список
динамически изменяемый массив произвольных объектов в Python

Кортежи

• последовательности

• индексирование / секционирование / for / in, вот это всё

• Задание: в круглых скобках (иногда и без)

Списки

Первый (кажется) изменяемый объект в нашем курсе!

• Задаётся квадратными скобками

• В него можно записывать объекты L[i] = 2345

• Трюк с несколькими именами одного и того же списка

  • .copy()

• Добавление и удаление элементов
  • Более странные штуки — присваивание секций
  • Линейная сложность всех этих операций, потому что сдвиг…

• …кроме .pop() и .append() — они быстрее

Основные алгоритмы

• Проход всего
• Проход по индексам
• Поиск первого

Пример: поиск максимума

Про eval(input())

Функция eval() вычисляет значение выражения, которое передаётся ей в виде строки. То есть она запускает интерпретатор Python (так же, как это делаем мы, когда запускаем программу!).

• Простой пример

  • >>> a = "6"
    >>> b = "8"
    >>> c = a + "*" + b
    >>> c
    '6*8'
    >>> eval(c)
      48

• То же самое происходит в форматных строках, но в случае eval() всё проще — результат именно такой, каким его вычислил Python:

  >>> type(f"{a} * 2 + {b} // 2")
  <class 'str'>
  >>> type(eval("a * 2 + b // 2"))
  <class 'int'>

• Из примера выше видно, что, как и в форматных строках, eval() умеет использовать пространства имён (т. е. в нём могут встречаться переменные)

• Это опасная функция, и её не стоит использовать, если вы не знаете, откуда получены её параметры и что в них содержится — при должной сноровке можно выполнить произвольный кусок программы!

• Однако она незаменима в домашних заданиях, где правильность ввода гарантируется

Например, вот так начинается программа, в которой сказано «Введите через запятую два числа и строку в кавычках»:

• x, y, s = eval(input())

• Допустим, мы вели строку «123, 345, "ASDF"». Если бы такую строку увидел Python, он посчитал бы, что это обычный кортеж из трёх элементов — двух чисел и строки (потому что она в кавычках)

• Ну так eval(inp) это и делает! Он возвращает кортеж, который раскладывается по трем переменным:

  >>> inp = input()
  123, 456, "ASDF"
  >>> print(inp)
  123, 456, "ASDF"
  >>> res = eval(inp)
  >>> print(res)
  (123, 456, 'ASDF')
  >>> print(type(res))
  <class 'tuple'>
  >>> a, b, s = res
  >>> a
  123
  >>> b
  456
  >>> s
  'ASDF'

Д/З

0. Прочитать и прощёлкать:

   • про списки на pythontutor

   • про списки в tutorial (русский перевод)

1. EJudge: PosCount 'Подсчёт Положительных'

   Вводятся построчно последовательности чисел через запятую. Если в строке нет запятых — это конец ввода, она не учитывается. Вывести общее количество положительных чисел.

   Input:

   1, 3, -3, 0, 234, 657
   -2, -4356, -345, 0, -11, -2134123412341234, 0, 0
   777, 2
   how boring!

   Output:

   6

2. EJudge: NumSearch 'Поиск Числа'

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

   Input:

   123, 2, 777, -8, 2, 100500
   1w21e23qr123rwe34rt5t5
   это кот на клавиатуру 8 раз сел и 22 клавиши нажал!
   777777 7777
   12-8=-123, ой, ошибся…
   .

   Output:

   123: 2
   2: 7
   777: 3
   -8: 1
   2: 7
   100500: 0

3. EJudge: ThirdsOut 'Третий Лишний'

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

   Input:

   print(squeeze([1, 5, 4, 3, 7, 6, 14, 8, 2]))

   Output:

   [1, 4, 3, 7, 6, 8, 2]

4. EJudge: BinSearch 'Двоичный поиск'

   Написать функцию, binsearch(x, A), реализующую двоичный поиск элемента x по индексируемой последовательности (списку, кортежу или даже range) A. Гарантировано, что последовательность упорядочена по возрастанию. Функция возвращает True, если $$ x \in A $$ и False в противном случае.

   Input:

   print(binsearch(123, sorted([123, 12, 45, 67, 23, 678, 12345, 4, 23, 768])))

   Output:

   True