Работа с последовательностями в Python [2.5]

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

Что такое iterable и iterator

Вы уже знаете структуры данных, которые содержат много элементов: списки, кортежи, словари, множества, строки. Такие объекты можно “перебирать” — они итерируемые (англ. iterable).

Один список можно перебирать много раз, а вот один конкретный итератор обычно “одноразовый”: как только он закончился, повторный перебор не начнётся автоматически.

Протокол итератора: __iter__() и __next__()

В Python итерация построена на двух методах:

• __iter__() — возвращает итератор (объект, который будет отдавать элементы).
• __next__() — возвращает следующий элемент; когда элементы закончились — вызывает исключение StopIteration.

Как работает for “под капотом”

Когда вы пишете цикл:

array = [1, 2, 3]
for a in array:
    pass

Python делает примерно следующее (упрощённо):

array = [1, 2, 3]
it = array.__iter__()     # или iter(array)

while True:
    try:
        a = it.__next__() # или next(it)
    except StopIteration:
        break
    # тело цикла for:
    pass

iter() и next(): “человеческие” функции вместо магических методов

Вы можете работать с итераторами напрямую через встроенные функции iter() и next().

array = (1, 2, 3)
it = iter(array)      # создаём итератор

print(next(it))       # 1
print(next(it))       # 2

StopIteration: что происходит на конце последовательности

Если вызвать next() больше раз, чем элементов в итераторе, будет исключение StopIteration.

it = iter([1, 2, 3])

print(next(it))  # 1
print(next(it))  # 2
print(next(it))  # 3
print(next(it))  # StopIteration

it = iter([1, 2, 3])

print(next(it, None))  # 1
print(next(it, None))  # 2
print(next(it, None))  # 3
print(next(it, None))  # None (вместо StopIteration)

Типичные ошибки с итераторами (с разбором)

nums = [1, 2, 3]
it = iter(nums)

print(list(it))  # [1, 2, 3]
print(list(it))  # []  итератор уже закончился

nums = [1, 2, 3]
# next(nums)   # TypeError: 'list' object is not an iterator

it = iter(nums)
print(next(it)) # 1

arr = [1, 2, 3, 4, 5]
for x in arr:
    if x % 2 == 0:
        arr.remove(x)

print(arr)
# часто неожиданно: [1, 3, 5] (или иной эффект на других кейсах)

arr = [1, 2, 3, 4, 5]
arr2 = [x for x in arr if x % 2 != 0]
print(arr2)  # [1, 3, 5]

2. Генераторы и ленивые вычисления

Зачем нужны генераторы

Генератор — это удобный способ создавать итераторы “на лету”. Он особенно полезен для больших последовательностей: значения вычисляются по мере необходимости, а не сохраняются сразу целиком в памяти. Это называют ленивыми вычислениями.

yield vs return: в чём разница

В обычной функции return завершает выполнение и возвращает значение. В генераторе yield “выдаёт” значение и приостанавливает функцию, чтобы продолжить с того же места при следующем next().

Пример: генератор факториалов

def factorial(N):
    a = 1
    for i in range(1, N + 1):
        a *= i
        yield a

my_gen = factorial(4)

print(next(my_gen))  # 1
print(next(my_gen))  # 2
print(next(my_gen))  # 6
print(next(my_gen))  # 24

Каждое значение вычисляется только в момент вызова next().

Почему range — не список

range(start, end, step) ведёт себя как “последовательность чисел”, но обычно не хранит все числа в памяти сразу. Он выдаёт значения по мере перебора, то есть работает лениво (как итератор/генераторная последовательность).

r = range(1, 10, 2)

for x in r:
    print(x)
# 1
# 3
# 5
# 7
# 9

Типичные ошибки с генераторами (с разбором)

gen = (x**2 for x in range(3))

print(list(gen))  # [0, 1, 4]
print(list(gen))  # [] генератор исчерпан

3. Списковые включения (list comprehensions)

Базовый синтаксис

Списковое включение — это компактный способ создать новый список на основе существующего итерируемого объекта.

numbers = [1, 2, 3, 4, 5]
squared_numbers = [x**2 for x in numbers]
print(squared_numbers)
# [1, 4, 9, 16, 25]

Условие if внутри включения (как filter)

Можно оставить только элементы, подходящие под условие — так же, как делает filter().

numbers = [1, 2, 3, 4, 5]
squared_even = [x**2 for x in numbers if x % 2 == 0]
print(squared_even)
# [4, 16]

Вложенные включения (как двойной цикл)

Если нужно создать комбинации “каждый с каждым”, можно вложить два цикла в одно включение.

list1 = [1, 2, 3]
list2 = [3, 4, 5]

new_list = [(x, y) for x in list1 for y in list2 if x + y == 6]
print(new_list)
# [(1, 5), (2, 4)]

Это эквивалентно вложенным циклам for + условие if.

Сравнение: for+append, map(), comprehension

Одна и та же задача “квадраты чисел” тремя способами:

Типичные ошибки списковых включений (и когда лучше не использовать)

# Плохо: список не нужен, а побочные эффекты есть
res = [print(x) for x in [1, 2, 3]]
print(res)
# 1
# 2
# 3
# [None, None, None]

4. Генераторы структур: dict и generator expressions

Dictionary comprehension (генератор словарей)

Словари тоже можно создавать компактно. Формула: {key_expression: value_expression for element in iterable if condition}.

my_dict = {x: x**2 for x in range(5)}
print(my_dict)
# {0: 0, 1: 1, 2: 4, 3: 9, 4: 16}

Словарь из двух списков через zip()

Частый практический приём: есть список ключей и список значений — “склеиваем” их через zip и строим словарь.

keys = ['a', 'b', 'c']
values = [1, 2, 3]

new_dict = {k: v for k, v in zip(keys, values)}
print(new_dict)
# {'a': 1, 'b': 2, 'c': 3}

Generator expression: “генераторное включение”

Если вместо списка вам нужен ленивый поток значений, используйте круглые скобки:

my_generator = (x**2 for x in range(5))

for value in my_generator:
    print(value)
# 0
# 1
# 4
# 9
# 16

Типичные ошибки dict/gen включений

data = [1, 2, 3, 4]
d = {x % 2: x for x in data}
print(d)
# {1: 3, 0: 4}  (1 перезаписался, 0 перезаписался)

5. Алгоритмы на последовательностях: поиск и сортировка

Поиск: линейный и бинарный

Линейный поиск

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

def linear_search(arr, x):
    for i, a in enumerate(arr):
        if a == x:
            return i
    return None

Бинарный поиск

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

def binary_search(arr, x):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (high + low) // 2

        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid

    return None

Сортировки: пузырёк, выбор, вставки

Сортировка пузырьком (bubble sort)

Сравнивает соседние элементы и меняет местами, если порядок неправильный. Повторяет проходы, пока всё не отсортируется.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

Сортировка выбором (selection sort)

На каждом шаге ищет минимальный элемент в неотсортированной части и ставит его в “следующую” позицию отсортированной части.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

Сортировка вставками (insertion sort)

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

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

“Разделяй и властвуй”: quick sort и merge sort

Быстрая сортировка (quick sort)

Выбирает опорный элемент (pivot), разбивает массив на элементы меньше/больше и рекурсивно сортирует части.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[0]
    less = [x for x in arr[1:] if x <= pivot]
    greater = [x for x in arr[1:] if x > pivot]
    return quick_sort(less) + [pivot] + quick_sort(greater)

Сортировка слиянием (merge sort)

Рекурсивно делит массив пополам до одноэлементных списков, а затем аккуратно “сливает” их обратно в правильном порядке.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

    return arr

Таблица: скорость/память/когда применять

Как сортирует Python (TimSort) — практический вывод

В реальном коде почти всегда используйте встроенные инструменты: sorted(iterable) (возвращает новый список) и list.sort() (сортирует список на месте). Внутри Python применяет гибридный алгоритм (TimSort), который обычно очень эффективен на “живых” данных.

Типичные ошибки в алгоритмах (с разбором)

arr = [3, 1, 2]

x = arr.sort()
print(x)    # None
print(arr)  # [1, 2, 3]

arr2 = sorted([3, 1, 2])
print(arr2) # [1, 2, 3]

6. Мини‑тесты по теме + разбор

new_list = [y + x for x in ['a','b','c'] for y in ['d','e','f']]
print(new_list)

lst = [x for x in range(10) if x % 2 == 0 or x % 3 == 0]
print(lst)
# ?

7. Чек‑лист самопроверки знаний

Отметьте пункты, которые вы действительно понимаете и можете воспроизвести без подсказок.