Материалы по курсу «Основы программирования»

Итераторы и цикл `for`

Итераторы и итерируемые объекты

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

Итератор в Python — объект, к которому можно применить встроенную функцию next(it). Функция next(it) одновременно получает текущий элемент и сдвигает итератор к следующему. При достижении конца перебираемых значений выбрасывается исключение (ошибка) StopIteration:

>>> xs = [1, 2, 3]
>>> it = iter(xs)
>>> next(it)
1
>>> next(it)
2
>>> next(it)
3
>>> next(it)
‹сообщение об ошибке StopIteration>

Итераторы могут перебирать элементы какой-то коллекции, либо вообще порождать значения на лету (списковые включения, функции map и zip, функции-генераторы с оператором yield и т.д.) Можно создать даже бесконечные итераторы, вызов next(it) для которых никогда не выбрасывает ошибку.

Итерируемый объект — объект в Python, для которого можно получить итератор при помощи встроенной функции iter(obj). Итерируемыми объектами являются, в частности, встроенные составные типы данных: списки, кортежи, строки, словари, множества.

Итераторы сами, как правило, являются итерируемыми объектами, функция iter(it) возвращает для них самого себя.

Для списков, кортежей, строк и множеств полученный итератор будет перебирать элементы контейнера. Для словарей итератор будет перебирать только ключи.

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

.keys() — итерируемый объект, итератор которого перебирает ключи,
.values() — итерируемый объект, итератор которого перебирает значения,
.items() — итерируемый объект, итератор которого перебирает пары (кортежи) (‹ключ›, ‹значение›).

Конструкторы контейнеров list(it), tuple(it), set(it) могут получать и итерируемые объекты, и итераторы — в результате будут строиться, соответственно, списки, кортежи и множества из соответствующих значений.

Конструктор словаря dict(it) может принимать итерируемый объект или итератор, перебирающий пары (кортежи), нулевой элемент которых будет трактоваться как ключ, первый — как значение.

Напрямую работать с итераторами не очень удобно, поэтому в Python предусмотрен специальный синтаксис для перебора итераторов. Этот синтаксис называется «цикл for».

Цикл `for`

Цикл for предназначен для перебора содержимого итераторов и итерируемых объектов. Синтаксис:

# простой вариант
for ‹перем› in ‹источник›:
    ‹тело цикла›

# с веткой else
for ‹перем› in ‹источник›:
    ‹тело цикла›
else:
    ‹ветка else›

Смысл следующий:

‹источник› — это выражение, значением которого может быть либо итератор, либо итерируемый объект. Содержимое источника будет перебираться в цикле.
‹перем› — переменная, куда будет помещаться очередной элемент, извлечённый из итератора. Если переменных указано несколько, то подразумевается распаковка.
‹тело цикла› — блок кода, который выполняется для каждого извлечённого элемента.
‹ветка else› — блок кода, который выполняется после перебора всех элементов. Если цикл был прерван при помощи оператора break, то ‹ветка else› не выполняется.

На самом деле, ветка else может быть и у цикла while:

while ‹условие›:
    ‹тело цикла›
else:
    ‹ветка else›

и смысл у неё тот же самый, но для цикла while она используется гораздо реже.

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

Последовательность — составной объект, элементы которого пронумерованы последовательными целыми числами. Среди изученных объектов последовательностями являются списки, кортежи и строки. К элементам всех этих составных объектов можно обращаться при помощи операции индексации xs[i].

В Python есть особая последовательность, представляющая собой элементы арифметической прогрессии — range. Её конструктор может быть вызван тремя способами:

range(‹предел›)
range(‹старт›, ‹предел›)
range(‹старт›, ‹предел›, ‹шаг›)

‹предел› — предельное значение, элементы последовательности всегда меньше предела,
‹старт› — начальное значение, если отстутствует, то подразумевается равным 0,
‹шаг› — разность между двумя соседними элементами, если отсутствует, то подразумевается равной 1.

Параметры конструктора могут быть только целыми числами.

range является итерируемым объектом, поэтому её можно преобразовать, например, в список.

Примеры:

>>> range(10)
range(10)
>>> list(range(10))
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> list(range(2, 10))
[2, 3, 4, 5, 6, 7, 8, 9]
>>> list(range(2, 10, 2))
[2, 4, 6, 8]
>>> list(range(1, 10, 2))
[1, 3, 5, 7, 9]

Последовательность range не хранит элементы явно, а порождает их налету при необходимости.

Последовательность range часто используется в сочетании с циклом for.

В Python встроенного в язык цикла со счётчиком (вроде того, который есть в Паскале) нету. Но в задачах часто требуется перебор последовательных целых чисел. Это в Python можно делать либо при помощи цикла while, вручную записывая условия и инкремент счётчика (что несколько решение), или использовать цикл for, но при этом источником должна быть требуемая последовательность целых чисел.

Такую последовательность как раз и порождает range.

Типичное использование for + range:

Перебор целых чисел от a до b, включая a и не включая b:
```
for i in range(a, b):
    ...
```
Перебор всех индексов последовательности (списка, строки или кортежа):
```
for i in range(len(xs)):
    ...
```
Индексы последовательности находятся в диапазоне от 0 до len(xs) − 1, range(len(xs)) их как раз порождает.

Пример. Напишем свой аналог функции range:

def myrange(*args):
    assert 1 <= len(args) <= 3

    if len(args) == 1:             # range(limit)
        start = 0
        limit = args[0]
        step = 1
    elif len(args) == 2:           # range(start, limit)
        start = args[0]
        limit = args[1]
        step = 1
    elif len(args) == 3:           # range(start, limit, step)
        start = args[0]
        limit = args[1]
        step = args[2]

    numbers = []

    if step > 0:
        current = start
        while current < limit:
            numbers.append(current)
            current += step
    else:
        current = start:
        while current > limit:
            numbers.append(current)
            current += step

    return numbers

Наш аналог myrange() принимает те же параметры, что и range() и создаёт итерируемый объект (у нас это список), элементы которого, что и в итерируемом объекте, создаваемом range.

Но наша реализация требует выделения памяти на список со всеми перебираемыми объектами, в то время как последовательность range объекты не хранит, а хранит только границы и шаг — итератор для неё порождает очередное число по запросу.

Поиск элемента при помощи цикла `for`

Мы рассматривали стандартный поиск элемента при помощи цикла while:

‹установка на начало›
while ‹элементы не кончились› and ‹текущий — не искомый›:
    ‹сдвинуться к следующему элементу›

if ‹элементы не кончились›:
    ‹обработать случай, когда текущий — искомый›
else:
    ‹обработать случай, когда искомого нет›

Часть «заполнителей» в этом шаблоне относятся к организации перебора, часть — к содержательной задаче поиска. К организации перебора относятся:

‹установка на начало›
‹элементы не кончились›
‹сдвинуться к следующему›

Остальные — это поиск элемента и действия для случая, когда объект найден и объект не найден.

Если мы используем итератор, то данный шаблон использовать не можем, т.к. у итератора нельзя просто так узнать, кончились элементы или нет. Функция next(it) одновременно проверкой конца считывает и следующий элемент.

Поэтому для поиска элемента с некоторым свойством используют цикл for. «Заполнители» в псевдокоде, осуществляющие перебор, в этом шаблоне гораздо проще, а «заполнители», относящиеся к поиску, остаются те же.

for ‹перем...› in ‹источник›:
    if ‹текущий объект — искомый›:
        ‹обработать случай, когда текущий — искомый›
        break
else:
    ‹обработать случай, когда текущий — не искомый›

Здесь:

‹перем...› — перемененная(ые), представляющая(ие) текущий просматриваемый объект.
‹источник› — итерируемый объект или итератор.

Пример. Мы писали функцию is_prime(n), проверающую простоту числа n с использования цикла while:

def is_prime(n):
    divisor = 2
    while (divisor <= n**0.5) and (n % divisor != 0):
        divisor += 1

    return divisor > n**0.5

Давайте её перепишем при помощи цикла for. Для начала, нам нужно подобрать источник перебираемых значений. Мы будем перебирать кандидаты в делители (как и раньше), кандидаты в делители растут с шагом 1, начинаются с 2 и продолжаются до √n включительно. Для построения последовательности кандидатов в делители воспользуемся range:

range(2, int(n**0.5) + 1)

+ 1 нужен, т.к. предельное значение не включается в последовательность.

def is_prime(n):
    for divisor in range(2, int(n**0.5) + 1):
        if n % divisor == 0:
            return False
            # break
    else:
        return True

Оператор break в этом примере не нужен, т.к. функция уже прерывается при помощи return’а.

Полезные встроенные функции, работающие с итераторами

Метод `str.join`

Мы говорили о том, что метод строки s.join(xs) принимает список строк и склеивает их при помощи строки s:

s.join(xs)  ≡  xs[0] + s + xs[1] + s + … + s + xs[len(xs) - 1]

На самом деле, параметром метода .join может быть любой итератор или итерируемый объект, содержащий строки.

Например, итерируемым объектом, перебирающим строки, является сама строка: её итератор будет перебирать символы в строке:

for c in 'Hello':
    print(c)

Напечатается:

H
e
l
l
o

Поэтому строку можно передать и в метод .join:

>>> '+'.join('Hello')
'H+e+l+l+o'

Функция map (о ней чуть позже) применяет функцию к каждому элементу итерируемого объекта, порождает итератор.

>>> ', '.join(map(str, [11, 22, 33, 44]))
'11, 22, 33, 44'

Функция `enumerate(xs)`

Функция enumerate(xs) принимает итерируемый объект и возвращает итератор пар (кортежей) (‹номер›, ‹элемент›), нумерация начинается с нуля.

Если мы попробуем в консоли посмотреть на результат вызова enumerate, то увидим, что она возвращает объект итератора:

>>> enumerate('abracadabra')
<объект итератора по адресу 1199248939742>

Поэтому, чтобы увидеть содержимое, мы будем оборачивать вызов enumerate в список — конструктор list(it) построит список из объектов итератора.

>>> list(enumerate('abracadabra'))
[(0, 'a'), (1, 'b'), (2, 'r'), (3, 'a'), ..., (9, 'r'), (10, 'a')]

В строке abracadabra 11 букв, поэтому приписанные номера будут от 0 до 10.

При помощи enumerate удобно перебирать элементы последовательности (списка, строки, кортежа) одновременно с их индексами:

for i, x in enumerate(xs):
    # Здесь i — индекс элемента, x — значение элемента

Этим использование enumerate для последовательностей похоже на метод .items для словаря:

for key, value in dictionary.items():
    # key — ключ, value — значение, связанное с ключом

Функцию enumerate можно сымитировать следующим образом:

def myenumerate(xs):
    res = []
    i = 0
    for x in xs:
        res.append((i, x))
        i += 1
    return res

Здесь точно также, как и в myrange, строится вспомогательный список, в то время как настоящая enumerate вспомогательных списков не строит, а формирует пары на лету по мере считывания.

Функция `reversed(it)`

Функция возвращает итератор для перебора итерируемого объекта it в обратном порядке. Просмотреть в обратном порядке можно далеко не все объекты. Можно просмотреть списки, строки, кортежи и range.

>>> list(reversed('Hello!'))
['!', 'o', 'l', 'l', 'e', 'H']
>>> list(reversed(range(10)))
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

Функция `sorted(xs)`

Функция sorted(xs) принимает итератор и формирует список, элементы которого упорядочены по возрастанию.

>>> sorted([13, 28, 6, 12, 20, 21])
[6, 12, 13, 20, 21, 28]
>>> sorted('abracadabra')
['a', 'a', 'a', 'a', 'a', 'b', 'b', 'c', 'd', 'r', 'r']

У функции sorted есть дополнительные именованные параметры, мы их обсудим, когда изучим работу с функциями как со значениями.

Функции `min(xs)` и `max(xs)`

Функции прининимают итерируемый объект и возвращают, соответственно, наименьший и наибольший элементы.

>>> min([13, 28, 6, 12, 20, 21])
6
>>> max([13, 28, 6, 12, 20, 21])
28
>>> min('abracadabra')
'a'
>>> max('abracadabra')
'r'

Дополнительные параметры, как и у функции sorted, обсудим позже.

Функция `sum(xs)`

Функция принимает итерируемый объект (внутри которого могут быть только числа), и находит их сумму.

>>> sum([13, 28, 6, 12, 20, 21])
100
>>> sum(range(10))
45
>>> sum(range(101))
5050

Функция `zip(xs, ...)`

Функция zip принимает n итерируемых объектов и возвращает итератор кортежей из n элементов, составленных из соответствующих элементов исходных итерируемых объектов. Результирующая последовательность имеет длину, равную длине наименьшей исходной последовательности:

>>> zip([2, 4, 6, 8, 10, 12], 'hello', range(100))
‹итератор›
>>> list(zip([2, 4, 6, 8, 10, 12], 'hello', range(100)))
[(2, 'h', 0), (4, 'e', 1), (6, 'l', 2), (8, 'l', 3), (10, 'o', 4)]

Материалы по курсу «Основы программирования»

Итераторы и цикл for

Итераторы и итерируемые объекты

Цикл for

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

Поиск элемента при помощи цикла for

Полезные встроенные функции, работающие с итераторами

Метод str.join

Функция enumerate(xs)

Функция reversed(it)

Функция sorted(xs)

Функции min(xs) и max(xs)

Функция sum(xs)

Функция zip(xs, ...)