Храним много данных в одном списке

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

Раньше мы сталкивались с задачей обработки элементов последовательности, например, вычисляя наибольший элемент последовательности. Но при этом мы не сохраняли всю последовательность в памяти компьютера. Онако, во многих задачах нужно именно сохранять всю последовательность, например, если бы нам требовалось вывести все элементы последовательности в возрастающем порядке («отсортировать последовательность»).

Для хранения таких данных можно использовать структуру данных, называемую в питоне список (в большинстве же языков программирования используется другой термин «массив»). Список представляет собой последовательность элементов, пронумерованных от 0, как символы в строке. Список можно задать перечислением элементов списка в квадратных скобках, например, список можно задать так:

primes = [2, 3, 5, 7, 11, 13]
rainbow = ['Red', 'Orange', 'Yellow', 'Green', 'Blue', 'Indigo', 'Violet']

В списке primes — 6 элементов, а именно, primes[0] == 2, primes[1] == 3, primes[2] == 5, primes[3] == 7, primes[4] == 11, primes[5] == 13. Список rainbow состоит из 7 элементов, каждый из которых является строкой.

Также как и символы строки, элементы списка можно индексировать отрицательными числами с конца, например, primes[-1] == 13, primes[-6] == 2.

Длину списка, то есть количество элементов в нем, можно узнать при помощи функции len, например, len(A) == 6.

Рассмотрим несколько способов создания и считывания списков. Прежде всего можно создать пустой список (не содержащий элементов, длины 0), в конец списка можно добавлять элементы при помощи метода append. Например, если программа получает на вход количество элементов в списке n, а потом n элементов списка по одному в отдельной строке, то организовать считывание списка можно так:

A = []
for i in range(int(input()):
    A.append(int(input())

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

Для списков целиком определены следующие операции: конкатенация списков (добавление одного списка в конец другого) и повторение списков (умножение списка на число). Например:

A = [1, 2, 3]
B = [4, 5]
C = A + B  # [1, 2, 3, 4, 5]
D = B * 3  # [4, 5, 4, 5, 4, 5]

В результате список C будет равен [1, 2, 3, 4, 5], а список D будет равен [4, 5, 4, 5, 4, 5]. Это позволяет по-другому организовать процесс считывания списков: сначала считать размер списка и создать список из нужного числа элементов, затем организовать цикл по переменной i начиная с числа 0 и внутри цикла считывается i-й элемент списка:

A = [0] * int(input())
for i in range(len(A)):
    A[i] = int(input())

Вывести элементы списка A можно одной инструкцией print(A), при этом будут выведены квадратные скобки вокруг элементов списка и запятые между элементами списка. Такой вывод неудобен, чаще требуется просто вывести все элементы списка в одну строку или по одному элементу в строке. Приведем два примера, также отличающиеся организацией цикла:

for i in range(len(A)):
    print(A[i])

Здесь в цикле меняется индекс элемента i, затем выводится элемент списка с индексом i.

for elem in A:
    print(elem, end = ' ')

В этом примере элементы списка выводятся в одну строку, разделенные пробелом, при этом в цикле меняется не индекс элемента списка, а само значение переменной (например, в цикле for elem in ['red', 'green', 'blue'] переменная elem будет последовательно принимать значения 'red', 'green', 'blue'.

Методы split и join

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

A = input().split()

Если при запуске этой программы ввести строку 1 2 3, то список A будет равен ['1', '2', '3']. Обратите внимание, что список будет состоять из строк, а не из чисел. Если хочется получить список именно из чисел, то можно затем элементы списка по одному преобразовать в числа:

for i in range(len(A)):
    A[i] = int(A[i])

У метода split есть необязательный параметр, который определяет, какая строка будет использоваться в качестве разделителя между элементами списка. Например, метод split('.') вернет список, полученный разрезанием исходной строки по символам '.'.

Используя «обратные» методы можно вывести список при помощи однострочной команды. Для этого используется метод строки join. У этого метода один параметр: список строк. В результате получается строка, полученная соединением элементов списка (которые переданы в качестве параметра) в одну строку, при этом между элементами списка вставляется разделитель, равный той строке, к которой применяется метод. Например программа

A = ['red', 'green', 'blue']
print(' '.join(A))  # -> red green blue
print(''.join(A))  # -> redgreenblue
print('***'.join(A))  # -> red***green***blue

выведет строки 'red green blue', redgreenblue и red***green***blue.

Если же список состоит из чисел, то эта функция не сработает, программа упадёт. О том, как с этим «бороться», будет дальше.

Ввод-вывод и ограничения

Во всех задачах этого листка программа получает на вход строку из целых чисел, разделенных пробелами. В конце строки также могут быть пробелы. Данную строку необходимо считать в список целых чисел.

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

Итерируемые объекты в питоне

Давайте вернёмся к списку цветов радуги:

rainbow = ['Red', 'Orange', 'Yellow', 'Green', 'Blue', 'Indigo', 'Violet']

Достаточно типичная задача — обработка этих цветов по очереди.

Другой сюжет был в теме про циклы: даны два числа $a$ и $b$, нужно вывести числа последовательно от $a$ до $b$ с учётом того, что $b$ может быть меньше. Типичное решение выгядит так:

if b > a:
    for i in range(a, b + 1):
        print(i)
else:
    for i in range(a, b - 1, -1):
        print(i)

Не самое плохое решение. Но если вместо простого вывода там была бы обработка на несколько строчек, то их пришлось бы продублировать. В питоне range — это тоже объект, его можно положить в переменную:

if b > a:
    my_range = range(a, b + 1):
else:
    my_range = range(a, b - 1, -1):
for i in my_range:
    print(i)

# Ещё примеры
another_range = range(50, 10, -3)
for i in my_range: print(i**2, end=', ')  # -> 0, 1, 4, 9, 16, 25, 36, 49, 64, 81,
lst = list(another_range)
print(lst)  # -> [50, 47, 44, 41, 38, 35, 32, 29, 26, 23, 20, 17, 14, 11]

Объединяет эти объекты то, что из них можно последовательно извлекать элементы. Такие объекты называется итерируемыми. Их в питоне достаточно много: списки и кортежи позволяют итерироваться по их элементам, строки позволяют итерироваться по отдельным буквам (вернее символам), из которых они состоят. Открытые текстовые файлы позволяют итерироваться по строчкам.

Итерируемые объекты могут участвовать во многих конструкциях. Например, при переборе элементов по одному:

for элементы in итерируемый_объект:
    обработать(элемент)

list(итерируемый_объект)

Итерация по элементам и функция enumerate

Очень часто при последовательном обработке элементов списка нам не важны индексы. В этом случае гораздо лучше вместо перебора индексов

A = [2, 4, 6, 8]
for i in range(len(A)):
    print(A[i])

сразу делать перебор элементов списка.

A = [2, 4, 6, 8]
for el in A:
    print(el)

Такой код легче читается (в нём меньше скобок и лишних переменных). Кроме того, переменную el можно изменять, не модифицируя при этом сам список.

В случаях, когда вместе с элементами нужны также и их индексы, идеоматический подход в питоне выглядит так:

for i, color in enumerate(('red', 'orange', 'yellow', 'green', 'cyan', 'blue', 'violet')):
    print(i+1, '-th color of rainbow is ', color, sep='')

for i, color in enumerate(('red', 'orange', 'yellow', 'green', 'cyan', 'blue', 'violet'), start=1):
    print(i, '-th color of rainbow is ', color, sep='')

Вот визуализация того, как это работает для превращения строки с числами в список чисел.

Бесконечность

Когда мы ищем что-то самое большое или самое маленькое, то часто удобно сначала положить в переменную что-то, что уж точно меньше (ну или больше), чем всё, что нам может встретиться. В питоне для этого можно использовать бесконечности:
$\infty = $ float('inf'), $-\infty = $ float('-inf')

x = float('inf')
x > 10000  # True
x > 1098465164864134681315  # True
x > 1e300  # True

Ещё один плюс бесконечностей в том, что их легко отличить от «обычных» чисел. Если в переменной осталась бесконечность, значит ничего дельного мы не встретили.

Функции map, enumerate, zip и т.д.

Есть несколько полезных функций, которые умеют брать итерируемый объект или несколько объектов, и возвращать новый итерируемый объект, элементы которого преобразованы каким-нибудь образом. Например, функция map берёт на вход какую-нибудь функцию и последовательно выдаёт элементы итерируемого объекта, к которым применили её применили.

Это всё кажется достаточно сложным, но это очень удобно и не особо сложно. Например, список чисел можно получить из строки сразу:

nums = '12 179 90'
A = list(map(int, nums.split()))  # [12, 179, 90]

Это работает так.
nums.split() берёт строку и нарезает её в список строк, получается ['12', '179', '90'];
map(int, input().split()) создаёт объект, который выдёргивает по одному элементы из этого списка строк и применяет к каждому функцию int . В данном случае объект будет по одному возвращать строки-числа, превращённые в числа;
list(map(int, input().split())) наконец функция list выдёргивает все элементы из итерируемого объекта и собирает из них список. Здесь в список сразу соберутся готовые числа. На выходе получится список [12, 179, 90].

Если нужно считать список действительных чисел, то нужно заменить тип int на тип float.

Также map удобно применять для вывода списка чисел в строку. Обычный join здесь не поможет, так как умеет склеивать только строки. Но map позволяет превратить что угодно в строки:

A = [12, 179, 90]
print(' '.join(map(str, A)))  # '12 179 90'

Здесь map по одному вытягивает числа 12, 179 и 90 из списка A, применяет к ним функцию str. А метод join собирает это всё вместе в одну строку.

Ещё примеры с map

l = [19, -76, 99, -95, 43]
print(list(map(str, l)))  # -> ['19', '-76', '99', '-95', '43']
print(list(map(abs, l)))  # -> [19, 76, 99, 95, 43]
print(list(map(float, l)))  # -> [19.0, -76.0, 99.0, -95.0, 43.0]

Функция zip

a = range(5)
b = range(100, 110, 2)
c = range(-50, -65, -3)
print(list(zip(a, b, c)))
# -> [(0, 100, -50), (1, 102, -53), (2, 104, -56), (3, 106, -59), (4, 108, -62)]

Генераторы списков

Для создания списка, заполненного одинаковыми элементами, можно использовать оператор повторения списка, например:

A = [0] * n

Для создания списков, заполненных по более сложным формулам можно использовать генераторы списков: выражения, позволяющие заполнить список некоторой формулой. Общий вид генератора следующий:

[ выражение for переменная in что-то_итерируемое]

где переменная — идентификатор некоторой переменной, что-то_итерируемое — список значений, который принимает данная переменная (как правило, полученный при помощи функции range), выражение — некоторое выражение, которым будут заполнены элементы списка, как правило, зависящее от использованной в генераторе переменной.

Вот несколько примеров использования генераторов.

Создать список, состоящий из n нулей можно и при помощи генератора:

A = [ 0 for i in range(n)]

Создать список, заполненный квадратами целых чисел можно так:

A = [ i ** 2 for i in range(n)]

Если нужно заполнить список квадратами чисел от 1 до n, то можно изменить параметры функции range на range(1, n + 1):

A = [ i ** 2 for i in range(1, n + 1)]

Вот так можно получить список, заполненный случайными числами от 1 до 9 (используя функцию randint из модуля random):

A = [ randint(1, 9) for i in range(n)]

А в этом примере список будет состоять из строк, считанных со стандартного ввода: сначала нужно ввести число элементов списка (это значение будет использовано в качестве аргумента функции range), потом — заданное количество строк:

A = [ input() for i in range(int(input()))]

Полезные хаки при обработке списков

Довольно часто бывает нужно найти во входных данных какое-нибудь особое значение, но мы не уверены, что там такое есть. Грубо говоря, программа будет выглядеть так:

i = 0
while i < len(данные) and данные[i] не_подходят:
    i += 1
код_который_разбирает_случаи_нашлось_или_не_нашлось

либо так:

for i in range(len(данные)):
    if данные[i] подходят:
        ...
код_который_разбирает_случаи_нашлось_или_не_нашлось

Общего в них то, что мы каждый раз проверяем и выход за границу списка, и условие. А можно вместо этого добавить в конец списка особый элемент, который заведомо удовлетворяет условию. Это позволяет избавиться от одной из проверок. Да и разбирать случай, в котором нужные данные не нашлись, тоже часто становится не нужно.

Также добавлять специальные элементы в начало или конец списка часто удобно в случаях, когда нужно учитывать не ровно один элемент, а дополнительно что-то про его соседей. Эта добавка может позволить не разбирать дополнительно специальные случаи в начале или конце списка, когда соответствующего соседа у элемента просто нет.

Многократный проход по списку: квадратичные решения

В задачах R-W «наивное» решение потребует $n$ проходов по списку длины $n$. В итоге будет выполнено порядка $n^2$ операций. Такие решения называют квадратичными и пишут, что они имеют асимптотику $O(n^2)$. И хотя каждую из этих задач можно решить более эффективно, в рамках этой темы этого не требуется.

Под капотом списка

Для любопытных есть отличная подробная статья, и, конечно же, исходные коды: listobject.h и listobject.c.