Iterator and Generator

Ітератори та генератори⚑

Генератор vs Ітератор⚑

Різниця між генераторами та ітераторами в Python полягає в тому, що ітератори використовуються для перебору групи елементів (наприклад, у списку), тоді як генератори є способом реалізації ітераторів, і використовуються для генерації значень. Генератори використовують ключове слово yield для повернення значення з функції, але, за винятком цього, вони ведуть себе як звичайні функції.

Links

• Генераторы-итераторы Python
• Итерируемый объект, итератор и генератор
• https://pavel-karateev.gitbook.io/intermediate-python/struktury-dannykh/generators

Ітерабельний об'єкт⚑

Summary

Ітерабельний об'єкт (iterable) - це об'єкт, який підтримує ітерацію, тобто може повертати значення по одному за раз. Приклади: всі контейнери і послідовності (списки, рядки і т.д.), файли, а також екземпляри будь-яких класів, в яких визначений метод __iter__().

Коли потрібно виконати ітерацію об’єкта у формі for i in myobject: ..., Python перевіряє на дуже високому рівні наступні дві речі: - Чи об’єкт містить один із методів ітератора — __next__ або __iter__ - Чи об’єкт є послідовністю та має __len__ та __getitem__

Тобто, ітерабельний об'єкт - це будь-який об'єкт, від якого вбудована функція iter() може отримати ітератор, тобто який реалізує метод __iter__.

Ітерабельні об'єкти можна використовувати у циклі for, а також в багатьох інших випадках, коли очікується послідовність (функції sum(), zip(), map() і т.д.).

Розглянемо ітерабельний об'єкт (Iterable). У стандартній бібліотеці він оголошений як абстрактний клас collections.abc.Iterable:

class Iterable(metaclass=ABCMeta):

    __slots__ = ()

    @abstractmethod
    def __iter__(self):
        while False:
            yield None

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Iterable:
            return _check_methods(C, "__iter__")
        return NotImplemented

Він має абстрактний метод __iter__, який повинен повернути об'єкт ітератора. І метод __subclasshook__, який перевіряє наявність у класу методу __iter__.

class SomeIterable1(collections.abc.Iterable):
    def __iter__(self):
        pass

class SomeIterable2:
    def __iter__(self):
        pass

print(isinstance(SomeIterable1(), collections.abc.Iterable))  # True

print(isinstance(SomeIterable2(), collections.abc.Iterable))  # True

Але є один момент - це функція iter(). Наприклад, цю функцію використовує цикл for для отримання ітератора. Функція iter() спочатку намагається отримати ітератор з об'єкта, викликаючи його метод __iter__. Якщо метод не реалізовано, то вона перевіряє наявність метода __getitem__, і якщо він реалізований, то на його основі створюється ітератор. __getitem__ повинен приймати індекс з нуля. Інтерпретатор надаватиме значення по черзі, доки не буде викликано виняток IndexError, який, аналогічно до StopIteration, також сигналізує про завершення ітерації. Якщо ж жоден з цих методів не реалізовано, то виникає виключення TypeError.

from string import ascii_letters

class SomeIterable3:
    def __getitem__(self, key):
        return ascii_letters[key]

for item in SomeIterable3():
    print(item)

Наприклад, по list можна ітеруватися, але сам list ніяк не стежить, де ми зупинилися в проході по ньому. А стежить об'єкт на ім'я ListIterator, який повертається методом iter() і використовується, наприклад, циклом for.

Ітератор⚑

Summary

Ітератор - об'єкт, який знає, як повертати свої елементи по одному за раз, підтримує ітерацію по послідовності. З точки зору Python він повинен мати метод __iter__(), який повертає сам об'єкт ітератора, і метод __next__(), який повертає наступний елемент послідовності або викидає виняток StopIteration, якщо більше немає елементів.

Ітератори використовуються в циклі for для ітерації по колекції. Кожен об'єкт, який підтримує ітератор, є ітерабельним, але не кожен ітерабельний об'єкт є ітератором. Наприклад рядки та словники - оскільки вони не мають методу __next__, натомість ітерабельність забезпечується наявністю методу __getitem__, який дозволяє отримувати доступ до елементів за їхніми індексами чи ключами.

Ітерабельність - це властивість об'єкта підтримувати ітерацію. Всі послідовності в Python є ітерабельними, оскільки вони підтримують ітерацію через свої елементи.

Ітератори представлені абстрактним класом collections.abc.Iterator:

class Iterator(Iterable):

    __slots__ = ()

    @abstractmethod
    def __next__(self):
        """Return the next item from the iterator. When exhausted, raise StopIteration"""
        raise StopIteration

    def __iter__(self):
        return self

    @classmethod
    def __subclasshook__(cls, C):
        if cls is Iterator:
            return _check_methods(C, '__iter__', '__next__')
        return NotImplemented

• __next__ повертає наступний доступний елемент і викликає виняток StopIteration, коли елементів не залишилося.
• __iter__ повертає self. Це дозволяє використовувати ітератор там, де очікується ітерабельний об'єкт, наприклад, в циклі for.
• __subclasshook__ перевіряє наявність у класу методів __iter__ і __next__

По ітератору можна пройтись тільки один раз.

my_list = [1, 2, 3, 4, 5]
my_iterator = iter(my_list)

print(next(my_iterator))  # 1
print(next(my_iterator))  # 2
print(next(my_iterator))  # 3

for item in my_iterator:
    print(item)  # 4, 5

try:
    print(next(my_iterator))  # raises StopIteration
except StopIteration:
    print("Iteration is done")

Генератор⚑

В залежності від контексту, може означати або функцію-генератор, або ітератор генератора (зазвичай останнє). Методи __iter__ і __next__ для генераторів створюються автоматично.

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

Тобто ідея генератора полягає в тому, щоб створити об'єкт, який є ітерованим і під час ітерації створює елементи, які він містить, по одному за раз. Основна мета генераторів — заощадити пам'ять: замість того, щоб зберігати великий список елементів у пам'яті одночасно, ми маємо об'єкт, який знає, як створити кожен окремий елемент, коли це необхідно. Ця функція дає змогу виконувати "ліниві обчислення" важких об'єктів у пам'яті. Це дозволяє працювати з нескінченними послідовностями, оскільки "лінивий" характер генераторів відкриває таку можливість.

Переваги використання генераторів - Економія пам'яті- генератори працюють ліниво, генеруючи значення за вимогою. Можуть використовуватися для завантаження даних у міру необхідності, що корисно при роботі з великими файлами або мережевими ресурсами, що дозволяє економити пам'ять - Ефективна обробка даних - генератори полегшують обробку великих наборів даних, тому що вони можуть обробляти дані поелементно, що може бути більш ефективним, ніж завантаження та обробка всіх даних одразу.

З точки зору реалізації, генератор в Python - це мовна конструкція, яку можна реалізувати двома способами: як функцію з ключовим словом yield або як генераторний вираз. При виклику функції або обчисленні виразу отримуємо об'єкт-генератор типу types.GeneratorType. Класичний приклад - генератор, який породжує послідовність чисел Фібоначчі, яка, будучи нескінченною, не могла б поміститися в будь-яку колекцію. Іноді термін використовується для самої генераторної функції, а не тільки для об'єкта, який повертається.

Оскільки в об'єкті-генераторі визначені методи __next__ і __iter__, тобто реалізований протокол ітератора, то в Python будь-який генератор є ітератором.

Коли виконання функції-генератора завершується (за допомогою ключового слова return або досягненням кінця функції), виникає виняток StopIteration.

Що таке генераторна функція⚑

Генераторна функція - це спеціальний тип функції, в тілі якої зустрічається ключове слово yield. При виклику такої функції повертається об'єкт-генератор (generator object). Генератори використовуються для створення ітерабельних об'єктів, що генерують значення "на льоту", зазвичай без зберігання їх у пам'яті. Якщо звичайна функція має одну точку входу та одне значення, яку повертається, то генераторна може мати кілька точок входу і виходу.

def generate_numbers(n):
    i = 0
    while i < n:
        yield i
        i += 1

generator = generate_numbers(5)  # <generator object iterate at 0x...>
for number in generator:
    print(number)

Важливо пам'ятати, що генератор можна пройти тільки один раз.

Що робить yield⚑

yield заморожує стан функції-генератора і повертає поточне значення. Після наступного виклику __next__() функція-генератор продовжує своє виконання з того місця, де вона була призупинена.

Що робить yield from⚑

Summary

Конструкція yield from бере генератор і передає ітерацію вниз по потоку. Але коли підгенератор завершує роботу, ця конструкція перехоплює виключення StopIteration, отримує його значення та повертає це значення викликаючій функції. Атрибут value виключення StopIteration стає результатом виразу.

В Python ключове слово yield from спрощує делегування генераторів. Воно використовується для передачі управління іншому генератору або ітерованому об'єкту з основного генератора. Це дозволяє зменшити обсяг коду та полегшити роботу з вкладеними генераторами. Він може отримувати значення, яке повертається підгенератором. Запис виду value = generator() не працює. Щоб він працював, потрібно переписати як value = yield from generator().

yield from автоматично ітерується по вказаному генератору чи ітерованому об'єкту і повертає всі його значення. При цьому усі send(), throw(), і close() команди передаються делегованому генератору. Якщо делегований генератор завершується з допомогою return, значення, яке повертається, можна отримати в основному генераторі через StopIteration.

yield from може використовуватись з будь-яким іншим ітератором, і це буде працювати так, ніби генератор верхнього рівня (той, який використовує yield from) генерує ці значення самостійно.

def subgen():
    yield 1
    yield 2
    return "Done"

def main_gen():
    result = yield from subgen()
    print(result)
    yield 3

for val in main_gen():
    print(val)  # 1 2 Done 3

У своїй найпростішій формі новий синтаксис yield from можна використовувати для об'єднання генераторів із вкладених циклів for в один, який у підсумку створить єдиний потік всіх значень у безперервному потоці.

Канонічний приклад — створення функції, подібної до itertools.chain() зі стандартної бібліотеки. Вона дозволяє передавати будь-яку кількість ітераторів і повертатиме їх усіх разом в одному потоці. Синтаксис yield from дозволяє уникнути вкладеного циклу, оскільки він може безпосередньо отримувати значення з підгенератора.

def chain(*iterables):  # naive implementation
    for it in iterables:
        for value in it:
            yield value

def chain(*iterables):  # implementation with yield from
    for it in iterables:
        yield from it

>>> list(chain("hello", ["world"], ("tuple", " of ", "values.")))
['h', 'e', 'l', 'l', 'o', 'world', 'tuple', ' of ', 'values.']

Для чого використовуються .close(), .throw() і .send() ?⚑

Python використовує генератори для створення корутин. Оскільки генератори можуть природним чином призупиняти виконання, вони є зручним відправним пунктом. Але генераторів виявилося недостатньо в їх початковій формі, тому були додані нові методи. Це пов'язано з тим, що зазвичай недостатньо лише призупинити виконання частини коду; часто необхідно взаємодіяти з ним (передавати дані та сигналізувати про зміни у контексті).

Методи .close(), .throw() і .send() використовуються для управління генераторами в Python, розширюючи їх стандартну функціональність і дозволяючи більш складну взаємодію з ними.

• .send(value) - дозволяє передати значення всередину генератора. Він відновлює виконання генератора і вставляє передане значення в місце, де знаходиться вираз yield. Це корисно, якщо генератор повинен реагувати на вхідні дані під час виконання. Перед передачею будь-яких значень у корутину потрібно викликати next(), щоб просунути її вперед.
• Цей метод фактично відрізняє генератор від корутини, оскільки під час його використання ключове слово yield з'являється у правій частині виразу, а його значення повернення буде призначено іншій змінній.
• yield у цьому випадку виконує дві функції. По-перше, він передає значення, що було згенероване, назад викликачу, який отримає його на наступному етапі ітерації (наприклад, після виклику next()). По-друге, він призупиняє виконання на цьому місці. Пізніше викликач може передати значення назад у корутину за допомогою методу send(). Це значення стане результатом виразу yield і буде призначено змінній.
• Передача значень до корутини працює тільки тоді, коли корутина призупинена на виразі yield і чекає якогось введення. Для цього корутина має досягти цього стану. Єдиний спосіб це зробити — викликати next() для корутини. Це означає, що перед передачею будь-чого в корутину, її потрібно хоча б раз просунути вперед за допомогою методу next(). Якщо цього не зробити, виникне виключення - TypeError: can't send non-None value to a just-started generator. Вперше при виклику next() генератор просунеться до рядка, що містить yield; він передасть значення викликачу і призупиниться на цьому місці.
• Виклик next() технічно еквівалентний виклику send(None).

def counter():
    total = 0
    while True:
        value = yield total  # Yield current total and receive new value
        if value is not None:
            total += value

gen = counter()
print(next(gen))  # Start generator: output 0
print(gen.send(10))  # Add 10: output 10
print(gen.send(5))   # Add 5: output 15

• .throw(exc_type, value=None, traceback=None) - використовується для ін'єкції винятку в генератор у місце, де він знаходиться. Генератор може обробити цей виняток або дозволити його піднятися вище. Це корисно для тестування обробки помилок у генераторі.

def sample_gen():
    try:
        yield "Start"
    except ValueError:
        yield "Handled ValueError"
    yield "End"

gen = sample_gen()
print(next(gen))  # Start generator
print(gen.throw(ValueError))  # Inject exception: output "Handled ValueError"
print(next(gen))  # Output "End"

• .close() - завершує виконання генератора, піднімаючи виняток GeneratorExit.
• Цей метод призначений для очищення ресурсів, тому зазвичай його використовують для ручного звільнення ресурсів, коли це неможливо зробити автоматично (наприклад, якщо не можна використати менеджер контексту). Після виклику .close() генератор не можна більше відновити.
• Якщо корутина виконує управління ресурсами, можна перехопити це виключення та використати цей блок керування для звільнення всіх ресурсів, які утримуються корутиною. Це схоже на використання менеджера контексту або розміщення коду в блоці finally керування виключеннями, але обробка цього виключення робить це більш очевидним.

def example_gen():
    try:
        yield "Running"
    finally:
        print("Generator is closing.")

gen = example_gen()
print(next(gen))  # Start generator
gen.close()  # Close generator: triggers `finally` block

Приклад корутини, яка використовує об'єкт для обробки бази даних, що підтримує з'єднання з базою даних, і виконує запити через нього, передаючи дані сторінками фіксованої довжини (замість читання всього доступного одразу). Під час кожного виклику генератора він повертатиме 10 рядків, отриманих через обробник бази даних. Коли потрібно завершити ітерацію, викликається метод close(), який закриє з'єднання з базою даних.

def stream_db_records(db_handler):
    try:
        while True:
            yield db_handler.read_n_records(10)
    except GeneratorExit:
        db_handler.close()

>>> streamer = stream_db_records(DBHandler("testdb"))
>>> next(streamer)
[(0, 'row 0'), (1, 'row 1'), (2, 'row 2'), (3, 'row 3'), ...]
>>> next(streamer)
[(0, 'row 0'), (1, 'row 1'), (2, 'row 2'), (3, 'row 3'), ...]
>>> streamer.close()
INFO:...:closing connection to database 'testdb'

В чому відмінність [x for x in y] від (x for x in y)⚑

Перший вираз повертає список (списковий вираз), другий - генератор.

Як отримати список з генератора⚑

Передати його у конструктор списку: list(x for x in some_seq). Важливо, що після цього по генератору не можна буде ітеруватись.

Використання генератора для nested loops⚑

У деяких ситуаціях нам потрібно ітеруватися по декількох вимірах у пошуку значення, і першою ідеєю стають вкладені цикли. Коли значення знайдено, ми повинні припинити ітерацію, але ключове слово break не спрацює повністю, тому що нам потрібно вийти з двох (або більше) циклів for, а не лише з одного. Також можна використати flag або викинути виняток (але краще не використовувати, оскільки винятки не призначені для використання у логіці керування потоком). Також можна перенести код у меншу функцію і використовувати return для виходу.

Приклад nested loop.

def search_nested_bad(array, desired_value):
    coords = None
    for i, row in enumerate(array):
        for j, cell in enumerate(row):
            if cell == desired_value:
                coords = (i, j)
                break
        if coords is not None:
            break

    if coords is None:
        raise ValueError(f"{desired_value} not found")

    logger.info("value %r found at [%i, %i]", desired_value, *coords)
    return coords

Спрощена версія, яка не використовує прапори для сигналізації про завершення а використовує генератори, і має більш компактну структуру ітерації.

def _iterate_array2d(array2d):
    for i, row in enumerate(array2d):
        for j, cell in enumerate(row):
            yield (i, j), cell

def search_nested(array, desired_value):
    try:        
        coord = next(
            coord for (coord, cell) in _iterate_array2d(array) if cell == desired_value
        )
    except StopIteration as e:
        raise ValueError(f"{desired_value} not found") from e

    logger.info("value %r found at [%i, %i]", desired_value, *coord)
    return coord

Що таке підгенератор⚑

У Python 3 існують так звані підгенератори (subgenerators). Якщо у генераторній функції зустрічається пара ключових слів yield from, за якими слідує об'єкт-генератор, то цей генератор делегує доступ до підгенератора, доки він не завершиться (не закінчаться його значення), після чого продовжує своє виконання.

Насправді, yield є виразом. Він може приймати значення, які надсилаються у генератор. Якщо значення не надсилаються у генератор, результатом цього виразу є None.

yield from також є виразом. Результатом його є значення, яке підгенератор повертає у виключенні StopIteration (для цього значення повертається за допомогою ключового слова return).

Які методи є у генераторів⚑

• __next__() - починає або продовжує виконання функції-генератора. Результатом поточного виразу yield буде None. Виконання потім продовжується до наступного виразу yield, який передає значення до місця, де був викликаний __next__. Якщо генератор завершується без повернення значення за допомогою yield, виникає виключення StopIteration. Зазвичай метод викликається неявно, наприклад, циклом for або вбудованою функцією next().
• send(value) - продовжує виконання і надсилає значення у функцію-генератор. Аргумент value стає значенням поточного виразу yield. Метод send() повертає наступне значення, повернене генератором, або викликає виключення StopIteration, якщо генератор завершується без повернення значення. Якщо send() використовується для запуску генератора, єдиним допустимим значенням є None, оскільки ще не було виконано жодного виразу yield, якому можна присвоїти це значення.
• throw(type[, value[, traceback]]) - викликає виняток типу type у місці, де було призупинено генератор, і повертає наступне значення генератора (або викликає StopIteration). Якщо генератор не обробляє даний виняток (або викликає інший виняток), то він виникає у місці виклику.
• close() - викликає виняток GeneratorExit у місці, де було призупинено генератор. Якщо генератор викликає StopIteration (через нормальне завершення або через те, що він вже закритий) або GeneratorExit (через відсутність обробки цього винятку), close просто повертається до місця виклику. Якщо ж генератор повертає наступне значення, виникає виняток RuntimeError. Метод close() нічого не робить, якщо генератор вже завершений.

Чи можна отримати елемент генератора за індексом⚑

Ні, виникне помилка. Генератор не підтримує метод __getitem__.

Що таке співпрограма⚑

Співпрограма (coroutine) - це спеціальна функція, яка може призупиняти своє виконання та передавати управління іншим корутинам, а потім продовжувати з місця, де зупинилися. Маючи таку функцію, програма може призупинити частину коду, щоб відправити щось інше для обробки, а потім повернутися до початкової точки для відновлення.

Корутини можеть мати кілька точок входу та виходу, на відміну від звичайних підпрограм, які мають одну точку входу та одну точку виходу. Також вони можуть зупиняти своє виконання будь-якої миті за допомогою спеціального оператора (наприклад, yield в Python або await в Kotlin), зберігаючи свій стан (локальні змінні та стек викликів).

Корутини працюють кооперативно - віддають управління одне одному, не конкуруючи за ресурси.

Для реалізації співпрограм використовуються розширені можливості генераторів у Python (вирази yield і yield from, надсилання значень у генератори).

Співпрограми корисні для реалізації асинхронних неблокуючих операцій та кооперативної багатозадачності у одному потоці без використання зворотних викликів (callback-функцій) та написання асинхронного коду у синхронному стилі.

Python 3.5 включає підтримку співпрограм на рівні мови. Для цього використовуються ключові слова async і await.