Что такое генераторы в программировании

В про­грам­ми­ро­ва­нии есть инстру­мент, кото­рый поз­во­ля­ет эко­но­мить память и при этом обра­ба­ты­вать огром­ные мас­си­вы дан­ных. Это гене­ра­то­ры. Мы рас­смот­рим рабо­ту гене­ра­то­ров на при­ме­ре язы­ка Python, но они есть и в дру­гих языках.

Классический подход к обработке — итераторы

Допу­стим, мы хотим выве­сти чис­ла от 1 до 10 и для это­го пишем такой код:

for i in range(1,10):

    print(i)

Это один из вари­ан­тов реа­ли­за­ции цик­ла. Что дела­ет ком­пью­тер, когда обра­ба­ты­ва­ет такое:

  1. Создаст в памя­ти область для хра­не­ния данных.
  2. Запол­нит её чис­ла­ми от 1 до 10.
  3. На каж­дом шаге цик­ла ком­пью­тер возь­мёт новые дан­ные из этой обла­сти и выве­дет их на экран.

При этом ком­пью­тер точ­но зна­ет, какое зна­че­ние у пере­мен­ной i было на преды­ду­щем шаге и будет на сле­ду­ю­щем, пото­му что все они хра­нят­ся в памяти.

Но что, если нам пона­до­бит­ся несколь­ко пере­мен­ных с диа­па­зо­ном зна­че­ний? Напри­мер, так:

a = range(1,100)

b = range(1000,2000)

for i in a:

    print(a[i-1] + b[i])

Когда мы запу­стим этот код, то уви­дим, что ком­пью­тер выде­лил боль­шой кусок памя­ти для обе­их пере­мен­ных и что мож­но обра­тить­ся к отдель­ным ячей­кам в таких диа­па­зо­нах. Это удоб­но, когда нуж­но посто­ян­но дер­жать под рукой какие-то дан­ные. Но если пере­мен­ные со счёт­чи­ка­ми не пона­до­бят­ся, то память будет про­ста­и­вать зря.

👉 Ите­ра­тор в дан­ном слу­чае — это цикл, кото­рый обра­ща­ет­ся к диа­па­зо­ну зна­че­ний и берёт по оче­ре­ди отту­да дан­ные. При этом все дан­ные уже есть в памяти.

Ите­ра­то­ры хоро­ши сво­ей пред­ска­зу­е­мо­стью, но при обра­бот­ке боль­шо­го пото­ка дан­ных могут при­ве­сти к рас­хо­ду памя­ти и неопти­маль­ной рабо­те программы.

Генераторы — вычисление данных «на лету»

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

  1. Цикл выпол­ня­ет­ся нуж­ное коли­че­ство раз.
  2. На каж­дом шаге цик­ла гене­ра­тор полу­ча­ет какое-то зна­че­ние, отда­ёт его в нуж­ное место и забы­ва­ет всё напрочь.
  3. Гене­ра­тор не пом­нит зна­че­ние, кото­рое он отда­вал до это­го, и не зна­ет, что он будет отда­вать на сле­ду­ю­щем шаге. Всё, что у него есть, — дан­ные, кото­рые нуж­но обра­бо­тать на теку­щем шаге.
  4. Память под рабо­ту гене­ра­то­ра выде­ля­ет­ся, толь­ко когда он гене­ри­ру­ет новые дан­ные. Пока гене­ра­тор сто­ит или не выда­ёт дан­ные — память не выделяется.

Чаще все­го гене­ра­то­ры исполь­зу­ют как функ­ции. Каж­дый раз, когда обра­ща­ют­ся к такой функции-генератору, она дела­ет так:

  1. Берёт новую пор­цию дан­ных из ука­зан­но­го ей источника.
  2. Обра­ба­ты­ва­ет данные.
  3. Воз­вра­ща­ет результат.
  4. Забы­ва­ет про всё до сле­ду­ю­ще­го вызова.

Обыч­но функ­ции воз­вра­ща­ют резуль­тат сво­ей рабо­ты с помо­щью коман­ды return(), а для гене­ра­то­ров есть спе­ци­аль­ная коман­да — yield().

Yield() рабо­та­ет так же, как и return(), толь­ко функ­ция на ней не закан­чи­ва­ет­ся, а ста­вит­ся на пау­зу. При сле­ду­ю­щем вызо­ве гене­ра­тор возь­мёт новую пор­цию дан­ных, и един­ствен­ное, что он пом­нит, — на каком месте он оста­но­вил­ся в про­шлый раз. Всё осталь­ное гене­ра­тор каж­дый раз счи­та­ет заново.

Пример из практики

Гене­ра­то­ры часто при­ме­ня­ют для одно­ра­зо­вой обра­бот­ки дан­ных по каким-то пра­ви­лам. Напри­мер, в про­ек­те с гене­ра­то­ром тек­ста на цепях Мар­ко­ва у нас был такой фраг­мент кода:

# отправляем в переменную всё содержимое текстового файла
text = open('che.txt', encoding='utf8').read()

# разбиваем текст на отдельные слова (знаки препинания останутся рядом со своими словами)
corpus = text.split()

# делаем новую функцию-генератор, которая определит пары слов
def make_pairs(corpus):
    # перебираем все слова в корпусе, кроме последнего
    for i in range(len(corpus)-1):
        # генерируем новую пару и возвращаем её как результат работы функции
        yield (corpus[i], corpus[i+1])
        
# вызываем генератор и получаем все пары слов
pairs = make_pairs(corpus)

А вот что про­изо­шло здесь по шагам:

  1. Мы откры­ли файл и запи­са­ли всё его содер­жи­мое в пере­мен­ную text. 
  2. С помо­щью встро­ен­ной функ­ции split() мы раз­би­ли текст на отдель­ные сло­ва и поме­сти­ли все сло­ва в отдель­ный мас­сив. На этом эта­пе в мас­си­ве при­мер­но 150 тысяч слов — для хра­не­ния тако­го коли­че­ства дан­ных ком­пью­тер выде­лил мно­го памяти.
  3. Мы пишем функцию-генератор. Каж­дый раз, когда к ней будут обра­щать­ся, она вер­нёт пару слов — теку­щее и сле­ду­ю­щее за ним. 
  4. В самом кон­це мы созда­ём новую пере­мен­ную — pairs. Может пока­зать­ся, что в ней сра­зу будут хра­нить­ся все пары слов, но на самом деле это переменная-генератор. При каж­дом обра­ще­нии к ней она вер­нёт новую пару слов и забу­дет о них.

В ито­ге у нас все сло­ва хра­нят­ся в пере­мен­ной corpus, а пары воз­вра­ща­ют­ся «на лету» при каж­дом обра­ще­нии к этой переменной.

👉 Глав­ный плюс гене­ра­то­ров — их мож­но ука­зы­вать в каче­стве диа­па­зо­на в цик­лах. На каж­дом шаге цикл полу­ча­ет новое зна­че­ние от гене­ра­то­ра и рабо­та­ет уже с ним. Как толь­ко у гене­ра­то­ра закан­чи­ва­ют­ся вари­ан­ты и он оста­нав­ли­ва­ет­ся — цикл тоже останавливается.

Вот как мы рабо­та­ем с этой пере­мен­ной дальше:

# словарь, на старте пока пустой
word_dict = {}

# перебираем все слова попарно из нашего списка пар
for word_1, word_2 in pairs:
    # если первое слово уже есть в словаре
    if word_1 in word_dict.keys():
        # то добавляем второе слово как возможное продолжение первого
        word_dict[word_1].append(word_2)

Здесь алго­ритм рабо­та­ет так:

  1. Дела­ем пустую пере­мен­ную для словаря.
  2. Запус­ка­ем цикл for и ука­зы­ва­ем переменную-генератор в каче­стве диа­па­зо­на цикла.
  3. Теперь на каж­дом шаге цик­ла он будет полу­чать новую пару от гене­ра­то­ра и обра­ба­ты­вать её внут­ри цик­ла. При этом сами пары физи­че­ски нигде не хра­нят­ся — их гене­ра­тор каж­дый раз соби­ра­ет на ходу.

❌ Если бы мы не зна­ли про гене­ра­то­ры, нам бы при­шлось делать отдель­ный мас­сив с пара­ми слов и выде­лять под него память. В нашем про­ек­те так сде­лать мож­но, но в реаль­ных зада­чах с пере­бо­ром боль­шо­го коли­че­ства дан­ных такой под­ход может съесть всю память.

И что, всё теперь нужно делать на генераторах?

Нет, нуж­но про­сто знать, что есть такая воз­мож­ность — соби­рать дан­ные на ходу и при этом не тра­тить на это память. Если вам в про­ек­те не нуж­ны гене­ра­то­ры или эко­но­мия памя­ти будет мизер­ная — рабо­тай­те без них. Но если нуж­но обра­бо­тать огром­ный мас­сив дан­ных, из кото­рых нуж­на толь­ко часть, то гене­ра­то­ры могут реаль­но выручить. 

Текст:

Миха­ил Полянин

Редак­ту­ра:

Мак­сим Ильяхов

Худож­ник:

Даня Бер­ков­ский

Кор­рек­тор:

Ири­на Михеева

Вёрст­ка:

Мария Дро­но­ва

Соц­се­ти:

Олег Веш­кур­цев