Перейти до змісту

Л14. Генератори, рекурсія й ефективність у Python

Коротко про лекцію

Повернемося до рекурсії та вартості обчислень. Потім введемо генератори як спосіб поступово виробляти значення без зайвої матеріалізації проміжних списків.

Ефективність має кілька вимірів. Алгоритм може виконувати багато операцій. Інший алгоритм може тримати забагато даних у пам’яті одночасно.

У C++ ми вже вивчали рекурсію та O-нотацію. Тепер перенесемо ці моделі у Python. Потім використаємо їх для мотивації лінивого опрацювання.

Практична мета. Після лекції ви повинні відрізняти кількість роботи від обсягу матеріалізованих даних і пояснювати поведінку генератора.

1. Рекурсія переноситься без зміни основної моделі

Рекурсивна функція має базовий випадок і крок до меншої задачі. Базовий випадок зупиняє подальші виклики. Рекурсивний крок наближає аргумент до нього.

def sum_to(n):
    if n == 0:
        return 0
    return n + sum_to(n - 1)

print(sum_to(4))

Для sum_to(4) утворюється ланцюжок задач 4, 3, 2, 1, 0. Потім результати повертаються у зворотному порядку.

flowchart TD
    A["sum_to(4)"] --> B["sum_to(3)"]
    B --> C["sum_to(2)"]
    C --> D["sum_to(1)"]
    D --> E["sum_to(0) = 0"]
    E --> F["повернення результатів угору"]

Синтаксис Python коротший за C++, але питання ті самі. Де база? Чи стає задача меншою? Скільки викликів виникає?

2. Правильна рекурсія може виконувати зайву роботу

Наявність базового випадку не гарантує ефективності. Рекурсивне рішення може багато разів обчислювати однакові підзадачі.

Наївне число Фібоначчі добре показує проблему. Щоб зробити її видимою, наступна функція повертає і значення, і кількість викликів.

def fibonacci_with_calls(n):
    if n <= 1:
        return n, 1

    left_value, left_calls = fibonacci_with_calls(n - 1)
    right_value, right_calls = fibonacci_with_calls(n - 2)
    return left_value + right_value, 1 + left_calls + right_calls

value, calls = fibonacci_with_calls(6)
print(value)
print(calls)

Збільшуйте n поступово та стежте за calls. Кількість викликів росте значно швидше за сам аргумент. Отже, красиве рекурсивне визначення ще треба оцінювати як алгоритм.

flowchart TD
    F6["fib(6)"] --> F5["fib(5)"]
    F6 --> F4a["fib(4)"]
    F5 --> F4b["fib(4) знову"]
    F5 --> F3["fib(3)"]
    F4a --> R["підзадачі повторюються"]
    F4b --> R

O-нотація описує зростання роботи зі збільшенням входу. Тут головна причина поганого зростання — повторні підзадачі.

3. Пам’ять ставить інше питання

Уявімо файл із мільйоном рядків. Один підхід спочатку створює список усіх оброблених значень. Потім інша частина програми проходить цей список.

Для деяких задач це зручно. Але іноді наступному етапу потрібен лише один черговий елемент. Тоді повний проміжний список може бути зайвим.

Потрібен механізм, який виробляє значення поступово. Він повинен зберігати лише стан продовження обчислення.

4. Генератор виробляє значення поступово

Генератор — це об’єкт, який може поступово виробляти значення для обходу. Він не зобов’язаний одразу створювати всю послідовність у пам’яті.

У функції-генераторі використовують інструкцію yield. Вона віддає одне значення та призупиняє функцію. Наступне продовження відновлює виконання після yield.

Терміни: генератор і yield

Генератор зберігає стан між кроками обходу. yield віддає поточне значення та залишає функцію готовою продовжити виконання пізніше.

Запис current -= 1 є скороченням current = current - 1. Він зменшує поточне значення на одиницю перед наступною перевіркою циклу.

def countdown(start):
    current = start
    while current > 0:
        yield current
        current -= 1

for value in countdown(3):
    print(value)

Перший крок віддає 3, а стан current зберігається. Наступний запит продовжує функцію та віддає 2. Так само отримуємо 1.

flowchart TD
    A["виклик countdown(3)"] --> B["обчислити до yield 3"]
    B --> C["призупинити й віддати 3"]
    C --> D["продовжити після yield"]
    D --> E["yield 2"]
    E --> F["yield 1"]
    F --> G["функція завершується"]

yield не завершує функцію остаточно, як return. Він створює точку призупинення для наступного кроку обходу.

5. Ліниве опрацювання відкладає роботу до потреби

Коли значення виробляються лише під час обходу, такий підхід називають лінивим опрацюванням. Робота відбувається в момент запиту чергового елемента.

Термін: ліниве опрацювання

Ліниве опрацювання відкладає обчислення до моменту потреби в наступному значенні. Воно може зменшити пікове використання пам’яті.

Замість нового списку функція може віддавати тільки значення, які пройшли умову.

def passing_scores(scores):
    for score in scores:
        if score >= 60:
            yield score

for score in passing_scores([45, 72, 60, 58, 91]):
    print(score)

Функція читає оцінку, перевіряє її й інколи віддає результат. Вона не створює окремий список усіх прохідних оцінок.

flowchart TD
    A["чергова оцінка"] --> B{"score >= 60?"}
    B -- ні --> A
    B -- так --> C["yield score"]
    C --> D["споживач обробляє одне значення"]
    D --> A

Ліниве виконання не робить алгоритм автоматично швидшим. Воно змінює момент роботи й обсяг одночасно матеріалізованих даних.

6. Генераторний вираз стискає простий генератор

Ми вже бачили спискове включення у Л12. Схожий запис у круглих дужках створює генераторний вираз:

(вираз for елемент in джерело if умова)

Він не створює готовий список. Значення виробляються під час споживання.

Стандартна функція sum(...) може споживати їх по одному та накопичувати суму.

numbers = [2, 4, 6, 8]
squares = (value * value for value in numbers)
print(sum(squares))

Порівняйте з [value * value for value in numbers]. Квадратні дужки створили б список квадратів. Круглі дужки тут створюють генератор.

7. Генератор зазвичай призначений для одного проходу

Генератор має поточну позицію. Після одного проходу значення генератора вже спожиті. Другий обхід не починається автоматично з початку.

values = (value for value in [2, 4, 6])
print(sum(values))
print(sum(values))

Перший sum забирає всі значення. Другому вже нічого споживати. Це важлива частина стану програми.

Якщо потрібен повторний обхід, можна знову створити генератор. Інший варіант — свідомо матеріалізувати дані у список.

8. Матеріалізація — це свідомий вибір

Матеріалізація означає створення й збереження всіх значень послідовності одночасно. Функція list(iterable) робить це для об’єкта, який можна обходити циклом for.

Термін: матеріалізація

Матеріалізація збирає всі елементи у готову структуру даних. Вона корисна для повторного обходу або індексації, але потребує пам’яті для всіх елементів.

def normalized_nonempty(lines):
    for line in lines:
        word = line.strip().lower()
        if word:
            yield word

lines = ["  Кіт ", "", "ПЕС", " кіт"]
print(list(normalized_nonempty(lines)))

Генератор нормалізує рядки по одному. list(...) наприкінці навмисно збирає всі результати. Тут матеріалізація потрібна для компактного виведення прикладу.

У великому конвеєрі наступний етап міг би одразу обробляти генератор. Тоді проміжний список не знадобився б.

9. Порівнюйте роботу й пам’ять окремо

Для кожного рішення ставте два різні питання:

  1. як росте кількість операцій зі збільшенням n;
  2. скільки даних треба зберігати одночасно.
flowchart TD
    A["алгоритмічне рішення"] --> B["час: скільки роботи?"]
    A --> C["пам’ять: скільки даних одночасно?"]
    B --> D["оцінка зростання"]
    C --> E["матеріалізація чи ліниве обчислення"]

Генератор може зменшити проміжну пам’ять. Він не усуває операції, які все одно потрібні для кожного елемента. Наївна рекурсія може бути дорогою через повторну роботу навіть без великих списків.

10. Коли генератор доречний

Генератор корисний, коли дані природно надходять послідовно. Він також підходить для довгих конвеєрів фільтрації та перетворення.

Список кращий, коли потрібен повторний обхід, індексація або незалежне зберігання всіх результатів. Вибір визначається контрактом наступного етапу.

Тому питання звучить не «що сучасніше?». Питайте: як дані споживаються, скільки разів і в якому обсязі?

11. Інтерактивна самоперевірка лекції

Самоперевірка порівнює рекурсивну роботу, генератори, матеріалізацію й повторний прохід. У кожному кодовому питанні спочатку відтворіть стан споживача.