Генератор (компьютерное программирование)

Чтобы узнать о других значениях, см. Генератор (значения) § Вычисления .

В информатике генератор — это процедура , которую можно использовать для управления итерационным поведением цикла . Все генераторы также являются итераторами . Генератор очень похож на функцию , возвращающую массив , тем, что генератор имеет параметры , может вызываться и генерирует последовательность значений. Однако вместо того, чтобы создавать массив, содержащий все значения, и возвращать их все сразу, генератор выдает значения по одному, что требует меньше памяти и позволяет вызывающей стороне немедленно приступить к обработке первых нескольких значений. Короче говоря, генератор выглядит как функция, но себя как итератор ведет .

Генераторы могут быть реализованы в виде более выразительных конструкций потока управления , таких как сопрограммы или первоклассные продолжения . Генераторы, также известные как полукорутины, являются особым случаем (и более слабым) сопрограмм, поскольку они всегда возвращают управление вызывающей стороне (при обратной передаче значения), а не указывают сопрограмму для перехода; см. сравнение сопрограмм с генераторами .

Использует

Генераторы обычно вызываются внутри циклов. При первом вызове генератора в цикле создается объект -итератор , который инкапсулирует состояние процедуры генератора в его начале, с аргументами, привязанными к соответствующим параметрам . Затем тело генератора выполняется в контексте этого итератора до тех пор, пока доходности не встретится специальное действие ; в этот момент значение, предоставленное действием выхода , используется в качестве значения выражения вызова. В следующий раз, когда в следующей итерации будет достигнут тот же вызов генератора, выполнение тела генератора возобновляется после действия выхода еще одно действие выхода до тех пор, пока не встретится . Помимо действия выхода , выполнение тела генератора также может быть прекращено действием завершения , при котором завершается самый внутренний цикл, включающий вызов генератора. В более сложных ситуациях генератор можно использовать вручную вне цикла для создания итератора, который затем можно использовать различными способами.

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

Когда желательно быстрое вычисление (в первую очередь, когда последовательность конечна, поскольку в противном случае вычисление никогда не завершится), можно либо преобразовать его в список , либо использовать параллельную конструкцию, которая создает список вместо генератора. Например, в Python генератор g может быть оценен в виде списка l с помощью l = list(g), а в F# выражение последовательности seq { ... } оценивает лениво (генератор или последовательность), но [ ... ] жадно оценивает (список).

При наличии генераторов конструкции цикла языка, такие как for и while, могут быть сведены к одной конструкции цикла... конца цикла; все обычные конструкции циклов затем можно удобно смоделировать, правильно используя подходящие генераторы. Например, диапазонный цикл типа for x = 1 to 10 может быть реализовано как итерация через генератор, как в Python for x in range(1, 10). Дальше, break может быть реализовано как отправка завершения генератору, а затем использование continue в петле.

Хронология

Генераторы впервые появились в CLU (1975). были важной особенностью языка манипулирования строками Icon (1977 г.) и теперь доступны в Python (2001 г.), С# , Руби , PHP , ECMAScript (начиная с ES6/ES2015 ) и другие языки. В CLU и C# генераторы называются итераторами , а в Ruby — перечислителями .

Лисп

Окончательный стандарт Common Lisp изначально не предоставляет генераторы, однако существуют различные реализации библиотек, такие как SERIES , документированные в CLtL2 или pygen .

КЛУ

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

string_chars = iter (s: string) дает (char);
   индекс: интервал: = 1;
   предел: int:= string$size (s);
   пока индекс <= предел делать
     выход (строка $fetch(s, index));
     индекс:= индекс + 1;
     конец;
 конец string_chars;

 для c: char в string_chars(s) do
    ...
 конец;
 

Значок

Каждое выражение (включая циклы) является генератором. Язык имеет множество встроенных генераторов и даже реализует некоторую логическую семантику с использованием механизма генератора ( логическая дизъюнкция таким образом выполняется или «ИЛИ»).

Печать квадратов от 0 до 20 может быть достигнута с помощью сопрограммы, написав:

   локальные   квадраты  ,   j 
    квадраты   :=   create   (  seq  (  0  )   ^   2  ) 
    каждые   j   :=   |@  квадраты   делать 
       , если   j   <=   20   , затем 
          писать  (  j  ) 
       , иначе 
          сломать 

Однако в большинстве случаев пользовательские генераторы реализуются с ключевым словом «suspend», которое действует точно так же, как ключевое слово «yield» в CLU.

С

В C нет функций-генераторов в качестве языковой конструкции, но, поскольку они являются подмножеством сопрограмм , их легко реализовать с помощью любой среды, реализующей стековые сопрограммы, например libdill. На платформах POSIX, когда стоимость переключения контекста на итерацию не является проблемой или полный параллелизм , а не просто параллелизм требуется , можно реализовать очень простую структуру функций генератора с использованием pthreads и Pipes .

С++

В C++ можно внедрить генераторы с помощью макросов препроцессора. Результирующий код может иметь аспекты, сильно отличающиеся от собственного кода C++, но синтаксис генератора может быть очень лаконичным. Набор макросов препроцессора, определенный в этом источнике, позволяет использовать генераторы, определенные с синтаксисом, как в следующем примере:

$генератор  (  спуск  ) 
 { 
    int   я  ; 

     // размещаем конструктор нашего генератора, например 
    // descent(int minv, int maxv) {...} 
   
    // от $emit до $stop — это тело нашего генератора: 
    
    $emit  (  int  )   // выдаст int ценности.   Начало корпуса генератора. 
        для   (  я   знак равно   10  ;   я   >   0  ;   --  я  ) 
          $ доход  (  я  );    // аналогично выходу в Python, 
                     // возвращает следующее число в [1..10] в обратном порядке. 
     $ стоп  ;    // остановка, конец последовательности.   Конец корпуса генератора. 
  }; 

Затем это можно повторить, используя:

int   main  (  int   argc  ,   char  *   argv  []) 
 { 
   descent   gen  ; 
    for   (  int   n  ;   gen  (  n  );)   // вызов генератора «получить следующий» 
     printf  (  «следующий номер — %d  \n  «  ,   n  ); 
    вернуть   0  ; 
  } 

Более того, C++11 позволяет циклы foreach к любому классу, предоставляющему применять begin и endфункции. Тогда можно написать классы, подобные генератору, определив оба итерируемых метода ( begin и end) и методы итератора ( operator!=, operator++ и operator*) в том же классе. Например, можно написать следующую программу:

#include   <iostream> 
 int   main  () 
 { 
     for   (  int   i  :   range  (  10  )) 
     { 
         std  ::  cout   <<   i   <<   std  ::  endl  ; 
      } 
     вернуть   0  ; 
  } 

Базовая реализация диапазона будет выглядеть так:

 классов  диапазон 
 { 
 частное  : 
     int   последний  ; 
      интервал   итер  ; 

  public  : 
     range  (  int   end  )  : 
         Last  (  end  ), 
         iter  (  0  ) 
     {} 

     // Итерируемые функции 
     const   range  &   Begin  ()   const   {   return   *  this  ;    } 
     Const   range  &   end  ()   const   {   return   *  this  ;    } 

     // Функции итератора 
     bool   оператор  !=  (  const   range  &  )   const   {   return   iter   <   last  ;    } 
     void   оператор  ++  ()   {   ++  iter  ;    } 
     int   оператор  *  ()   const   {   return   iter  ;    } 
 }; 

Перл

Perl изначально не предоставляет генераторы, но поддержка обеспечивается модулем Coro::Generator , который использует Coro структуру сопрограмм . Пример использования:

используйте   строгий  ; 
  использовать   предупреждения  ; 
  # Включить генератор { BLOCK } и дать команду 
 использовать   Coro::Generator  ; 
  # Ссылка на массив для перебора 
 моих   $chars   =   [  'A'  ...  'Z'  ]; 

  # Новый генератор, который можно вызвать как ссылку на код. 
  мои   $letters   =   генератор   { 
     мой   $i   =   0  ; 
      for   my   $letter   (  @$chars  )   { 
         # получить следующее письмо из $chars 
         yield   $letter  ; 
      } 
 }; 

  # Вызовите генератор 15 раз. 
  напечатайте   $letters  ->  (),   «\n»   для   (  0  ..  15  ); 

Раку

В примере, параллельном Icon, используется класс Range Raku (ранее известный как Perl 6) как один из нескольких способов создания генераторов с помощью языка.

Напечатать квадраты от 0 до 20 можно, написав:

для  (  0  .. *).   карта  (* **  2  ) ->  $i  { 
      последний   , если   $i  >  20  ; 
      скажи   $я 
  } 
 

Однако в большинстве случаев пользовательские генераторы реализуются с ключевыми словами «собрать» и «взять» в ленивом контексте.

ТКЛ

В Tcl 8.6 механизм генератора основан на именованных сопрограммах .

procgenerator   info   {  body  }   { 
     coroutine   gen  [  incr   ::  disambiguator  ]   apply   {{  script  }   { 
         # Создаем результат [generator], имя генератора 
         yield   [  ]   coroutine  # Завершаем 
         # Выполняем генерацию 
         eval   $script 
         цикл вызывающего абонента, использующего 
         возврат   исключения «break» -  кода   разрыв 
      }}   $body 
 } 

 # Используйте простой цикл for, чтобы подсчитать фактическое количество генерируемых 
 [   наборов   generator  {   for 
     {   set   i   10  }   {  $i   <=   20  }   {  incr   i  }   { 
         yield   $i 
     } 
 }] 

 # Извлекаем значения от генератора, пока он не исчерпается, 
 пока   1   { 
     puts   [  $count  ] 
 } 

Хаскелл

В Haskell с его моделью отложенного вычисления каждое значение, созданное с помощью нестрогого конструктора данных, генерируется по требованию. Например,

countFrom   ::   Integer   ->   [  Integer  ] 
 countFrom   n   =   n   :   countFrom   (  n   +   1  ) 

 from10to20   ::   [  Integer  ] 
 from10to20   =   takeWhile   (  <=   20  )   $   countFrom   10 

 простых чисел   ::   [  Integer  ] 
 primes   =   2   :   3   :   nextPrime   5 
   где 
     следующийPrime   n 
         |    notDivisible   n   =   n   :   nextPrime   (  n   +   2  ) 
         |    иначе   =   nextPrime   (  n   +   2  ) 
     notDivisible   n   = 
         all   ((  /=   0  )   .   (  rem   n  ))   $   takeWhile   ((  <=   n  )   .   (  ^   2  ))   $   хвостовые   простые числа 

где (:) — конструктор нестрогого списка, cons и $это просто оператор «вызывается с» , используемый для заключения в круглые скобки. При этом используется стандартная функция адаптера,

takeWhile   p   []   =   [] 
 takeWhile   p   (  x  :  xs  )   |    p   x   =   x   :   takeWhile   p   xs 
                    |    в противном случае   =   [] 

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

SquaresUnder20   =   takeWhile   (  <=   20  )   [  x   *   x   |    x   <-   countFrom   10  ] 
 SquaresForNumbersUnder20   =   [  x   *   x   |    x   <-   takeWhile   (  <=   20  )   $   countFrom   10  ] 

Ракетка

Racket предоставляет несколько сопутствующих возможностей для генераторов. Во-первых, его формы цикла for работают с последовательностями , которые являются своего рода производителем:

(  for   ([  i   (  in-range   10   20  )]) 
   (  printf   "i = ~s  \n  "   i  )) 

и эти последовательности также являются значениями первого класса:

(  определить   от 10 до 20   (  в диапазоне   10   20  )) 
 (  for   ([  i   от 10 до 20  ]) 
   (  printf   "i = ~s  \n  "   i  )) 

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

Но если говорить более конкретно, Racket поставляется с библиотекой генераторов для более традиционной спецификации генератора. Например,

#lang  Racket 
 (  require   Racket/generator  ) 
 (  define   (  ints-from   from  ) 
   (  generator   () 
     (  for   ([  i   (  in-naturals   from  )])   ; бесконечная последовательность целых чисел от 0 
       (  выход   i  )))) 
 (  define   g   (  ints-from   10  )) 
 (  list   (  g  )   (  g  )   (  g  ))   ;   -> '(10 11 12) 

Обратите внимание, что ядро ​​Racket реализует мощные функции продолжения, предоставляя общие (реентерабельные) продолжения, которые можно компоновать, а также продолжения с разделителями. Используя это, в Racket реализована библиотека генератора.

PHP

Сообщество PHP реализовало генераторы в PHP 5.5. Подробности можно найти в оригинальном Запросе комментариев: Генераторы .

Бесконечная последовательность Фибоначчи:

функция   Фибоначчи  ()  :   Генератор 
 { 
     $last   =   0  ; 
      $ текущий   =   1  ; 
      выход   1  ; 
      while   (  истина  )   { 
         $current   =   $last   +   $current  ; 
          $last   =   $current   -   $last  ; 
          выход   $текущий  ; 
      } 
 } 

 foreach   (  fibonacci  ()   as   $number  )   { 
     echo   $number  ,   "  \n  "  ; 
  } 

Последовательность Фибоначчи с пределом:

функция   Фибоначчи  (  int   $limit  )  :   Генератор  
 { 
     доходность   $a   =   $b   =   $i   =   1  ; 
 
      while   (  ++  $i   <   $limit  )   { 
         доходность   $a   =   (  $b   =   $a   +   $b  )   -   $a  ; 
      } 
 } 

 foreach   (  fibonacci  (  10  )   as   $number  )   { 
     echo   "  $number  \n  "  ; 
  } 

Любая функция, содержащая оператор доходности , автоматически является функцией-генератором.

Руби

Ruby поддерживает генераторы (начиная с версии 1.9) в виде встроенного класса Enumerator.

# Генератор из объекта Enumerator 
 chars   =   Enumerator  .   новый  (  [  'A'  ,   'B'  ,   'C'  ,   'Z'  ]  ) 

 4  .   раз   {   ставит   символы  .   next   } 

 блоков 
 # Генератор из счетчика   =   Enumerator  .   новый   делать   |   урожай  | 
    я   =   0 
   цикл   {   уступающий  .   выход   я   +=   1   } 
 конец 

 100  .   раз   {   ставит   кол  .   следующий   } 

Ява

Java имеет стандартный интерфейс для реализации итераторов с самого начала, а начиная с Java 5 конструкция foreach позволяет легко перебирать объекты, предоставляющие java.lang.Iterableинтерфейс. ( Структура коллекций Java и другие платформы коллекций обычно предоставляют итераторы для всех коллекций.)

запись   Пара  (  int   a  ,   int   b  )   {}; 

  Iterable  <Integer> ​ ​   myIterable   =   Stream  .   итерация  (  новая   пара  (  1  ,   1  ),   p   ->   новая   пара  (  p  .  b  ,   p  .  a   +   p  .  b  )) 
         .   предел  (  10  ) 
         .   карта  (  p   -   p.a  итератор  >  ::  ;  ) 

  мойИтерабельный  .   forEach  (  System.out ​  ::  println  )  ; 

Или получите итератор из Java 8 суперинтерфейса BaseStream of Stream.

запись   Пара  (  int   a  ,   int   b  )   {}; 

  // Сохраняем итератор потока, который генерирует последовательность Fib. 
 Iterator  <  Integer  >   myGenerator   =   Stream 
         // Генерирует последовательность Fib 
         .   итерация  (  новая   пара  (  1  ,   1  ),   p   ->   новая   пара  (  p  .  b  ,   p  .  a   +   p  .  b  )) 
         .   карта  (  п   ->   п  .  а  ).   итератор  (); 

  // Выводим первые 5 элементов 
 for   (  int   i   =   0  ;   i   <   5  ;   i  ++  )   { 
     System  .   вне  .   println  (  myGenerator  .  next  ()); 
  } 

 Система  .   вне  .   println  (  "сделано с первой итерацией"  ); 

  // Выводим следующие 5 элементов 
 for   (  int   i   =   0  ;   i   <   5  ;   i  ++  )   { 
     System  .   вне  .   println  (  myGenerator  .  next  ()); 
  } 

Выход:

1 
 1 
 2 
 3 
 5 
 выполнено с первой итерацией 
 8 
 13 
 21 
 34 
 55 

С#

Пример генератора C# 2.0 (файл yieldдоступен начиная с версии C# 2.0): В обоих этих примерах используются дженерики, но это не обязательно. Ключевое слово выход также помогает в реализации пользовательских итераций с отслеживанием состояния коллекции, как обсуждалось в этом обсуждении.

// Метод, который принимает итеративные входные данные (возможно, массив) 
 // и возвращает все четные числа. 
  public   static   IEnumerable  <int>  foreach  )   GetEven  (  IEnumerable  <int>  число  Numbers   числах  ) 
 { 
     ;   (  int  ​   в  ​  { 
    ​ 
         if   (  number   %   2  )   ==   0  ) 
         { 
             доходность   возвращаемого   числа  ( 
          } 
     } 
 } 

Возможно использование нескольких yield return операторы и они применяются последовательно на каждой итерации:

общественный   класс   CityCollection   :   IEnumerable  <  строка  > 
 { 
     общественный   IEnumerator  <  строка  >   GetEnumerator  () 
     { 
         доходность   возврата   "Нью-Йорк"  ; 
          доходность   возврата   "Париж"  ; 
          доходность   возврата   «Лондон»  ; 
      } 
 } 

XL

В XL итераторы являются основой циклов for:

импорт ввода-вывода = XL.UI.CONSOLE

 итератор IntegerIterator (var out Counter: целое число; Low, High: целое число), записанный Counter в Low..High, равен
     Счетчик:= Низкий
     while Counter <= Высокий цикл
         урожай
         Счетчик += 1

 // Обратите внимание, что I не нужно объявлять, поскольку в итераторе объявлено 'var out'
 // Поэтому здесь делается неявное объявление I как целого числа
 для меня в 1..5 петле
     IO.WriteLn "I=", я
 

Ф#

Дополнительная информация: выражение последовательности.

F# предоставляет генераторы через выражения последовательности , начиная с версии 1.9.1. Они могут определять последовательность (лениво оцениваемая, последовательный доступ) через seq { ... }, список (быстро оцениваемый, последовательный доступ) через [ ... ] или массив (быстро оцениваемый, индексированный доступ) через [| ... |]которые содержат код, генерирующий значения. Например,

seq   {   for   b   in   0   ..   25   do 
           if   b   <   15   , то 
               получим   b   *   b   } 

формирует последовательность квадратов чисел от 0 до 14, отфильтровывая числа из диапазона чисел от 0 до 25.

Питон

Генераторы были добавлены в Python в версии 2.2 в 2001 году. Пример генератора:

от   ввода   import   Iterator 

 def   countfrom  (  n  :   int  )   ->   Iterator  [  int  ]: 
     while   True  : 
         yield   n 
         n   +=   1 

 # Пример использования: распечатка целых чисел от 10 до 20. 
 # Обратите внимание, что эта итерация завершается нормально, несмотря на 
 # countfrom() записан как бесконечный цикл. 

  for   i   in   countfrom  (  10  ): 
     if   i   <=   20  : 
         print  (  i  ) 
     else  : 
         Break 

 # Другой генератор, который генерирует простые числа бесконечно по мере необходимости. 
  import   itertools 

 def   primes  ()   ->   Iterator  [  int  ]: 
     """Генерировать простые числа бесконечно по мере необходимости.""" 
     выдает   2 
     n   =   3 
     p   =   [  2  ] 
     while   True  : 
         # При делении n на все числа в p, до sqrt(n) включительно, 
         # дает ненулевой остаток, тогда n является простым. 
          if   all  (  n   %   f   >   0   for   f   in   itertools  .  takeough  (  лямбда   f  :   f   *   f   <=   n  ,   p  )): 
             выход   n 
             p  .   добавить  (  п  ) 
         п   +=   2 

В Python генератор можно рассматривать как итератор , содержащий замороженный кадр стека . В любое время next() вызывается на итераторе, Python возобновляет замороженный кадр, который выполняется нормально до следующего yieldзаявление достигнуто. Затем кадр генератора снова замораживается, и полученное значение возвращается вызывающей стороне.

PEP 380 (реализован в Python 3.3) добавляет yield from выражение, позволяющее генератору делегировать часть своих операций другому генератору или итерируемому объекту.

Выражения-генераторы

В Python есть синтаксис, смоделированный на синтаксисе списков , называемый выражением генератора, который помогает в создании генераторов. Следующий пример расширяет первый приведенный выше пример, используя выражение-генератор для вычисления квадратов из countfrom функция генератора:

квадраты   =   (  n   *   n   для   n   в   countfrom  (  2  )) 

 для   j   в   квадратах  : 
     если   j   <=   20  : 
         напечатайте  (  j  ) 
     иначе  : 
         сломайте 

ECMAScript

ECMAScript 6 (он же Harmony) представил функции генератора.

Бесконечную последовательность Фибоначчи можно записать с помощью генератора функций:

function  *   fibonacci  (  limit  )   { 
     let   [  prev  ,   curr  ]   =   [  0  ,   1  ]; 
      while   (  !  предел   ||   Curr   <=   предел  )   { 
         доходность   Curr  ; 
          [  предыдущая  ,   текущая  ]   =   [  текущая  ,   предыдущая   +   текущая  ]; 
      } 
 } 

 // ограничено верхним пределом 10 
 for   (  const   n   of   fibonacci  (  10  ))   { 
     console  .   журнал  (  н  ); 
  } 

 // генератор без верхнего предела 
 for   (  const   n   of   fibonacci  ())   { 
     console  .   журнал  (  н  ); 
      если   (  n   >   10000  )   сломать  ; 
  } 

 // итерируем вручную 
 let   fibGen   =   fibonacci  (); 
  консоль  .   журнал  (  fibGen  .  next  ().  значение  );    // 1 
 консоль  .   журнал  (  fibGen  .  next  ().  значение  );    // 1 
 консоль  .   журнал  (  fibGen  .  next  ().  значение  );    // 2 
 консоли  .   журнал  (  fibGen  .  next  ().  значение  );    // 3 
 консоли  .   журнал  (  fibGen  .  next  ().  значение  );    // 5 
 консоль  .   журнал  (  fibGen  .  next  ().  значение  );    // 8 

 // возобновляется с того места, где вы 
 остановились   (  const   n   of   fibGen  )   { 
     console  .   журнал  (  н  ); 
      если   (  n   >   10000  )   сломать  ; 
  } 

Р

Для этой цели можно использовать пакет итераторов.

библиотека  (  итераторы  ) 

 # Пример ------------------ 
 abc   <-   iter  (  c  (  'a'  ,  'b'  ,  'c'  )) 
 nextElem  (  abc  ) 

Смолток

Пример в Pharo Smalltalk :

Приведенный ниже генератор золотого сечения возвращает при каждом вызове GoldenRatio next лучшее приближение к золотому сечению.

goldRatio   :=   Генератор   включен:  [  :  g   |    |   ксизр  |  
	  х   :=   0  . 
	  у   :=   1  . 
	  [   
		  г   :=   х   +   у  . 
		  r   :=  (  z   /   y  )  asFloat  . 
		  х   :=   у  . 
		  y   :=   z  . 
		  г   выход:   г 
	  ]  повторить 	
  ]  . 

  GoldenRatio   следующий  . 

Выражение ниже возвращает следующие 10 приближений.

Персонаж   cr   join:  ((  1   to:   10  )  Collect:  [  :  dummy   |   соотношение   следующее  ])  . 

Подробнее см. в разделе « Скрытый драгоценный камень в Pharo: Generator» .

См. также

• Понимание списка для другой конструкции, генерирующей последовательность значений.
• Итератор для концепции создания списка по одному элементу за раз
• Итератор для альтернативы
• Ленивая оценка для получения значений при необходимости
• Корекурсия для потенциально бесконечных данных посредством рекурсии вместо доходности
• Сопрограмма для еще большего обобщения подпрограммы
• Продолжение обобщения потока управления

Ссылки

• Стефан Мюрер, Стивен Омохундро , Дэвид Стаутамир и Клеменс Шиперски: Абстракция итерации в Сазере . Транзакции ACM по языкам и системам программирования , 18(1):1-15 (1996) [1]