生成器 (计算机编程)

维基百科,自由的百科全书
跳到导航 跳到搜索

生成器计算机科学中特殊的子程序。实际上,所有生成器都是迭代器[1]生成器非常类似于返回数组的函数,都是具有参数、可被调用、产生一系列的值。但是生成器不是构造出数组包含所有的值并一次性返回,而是每次产生一个值,因此生成器看起来像函数,但行为像迭代器。

生成器可以用更有表达力的控制流结构实现,如协程或头等計算續體[2] 生成器,也被称作半协程(semicoroutine),[3]是特殊的、能力更弱的协程,总是在传回一个值时把控制交还给调用者,而不是像协程那样指出另一个协程继续执行。

使用[编辑]

生成器通常在一个循环内部被调用。[4] 生成器第一次被调用是在进入这个循环结构时,创建一个对象以封装生成器的状态、绑定的实参。生成器的实体接着被执行直至遇到一个特别的yield动作,在这里提供给yield动作的值被返回给调用者。在下一次调用同一个生成器的时候,生成器从yield动作之后恢复执行,直到遇上另一个yield动作。生成器的执行也可以遇到finish动作而终止。

由于生成器计算它的要被yield的值是按需的,因此可以用来代表一个,一次性全部计算出来是昂贵的甚至是不可能的,或是无穷序列或直播数据序列。

如果需要迅速求值,可以使用列表或使用并行结构来创建一个列表。例如,Python的一个生成器g可被求值到列表l通过l = list(g)

生成器可用于在表达式中完成传统的循环结构的功能。

历史[编辑]

生成器最早出现于CLU语言 (1975)。[5]

现在,Python,[6] C#,[7] Ruby, 最新版本的ECMAScript (ES6/ES2015)与其他语言。在CLU与C#,生成器称作iterators, 在Ruby称作enumerators.

C++[编辑]

使用宏预处理的例子见[8]:

$generator(descent)
{
   // place for all variables used in the generator
   int i; // our counter

   // place the constructor of our generator, e.g. 
   // descent(int minv, int maxv) {...}
   
   // from $emit to $stop is a body of our generator:
    
   $emit(int) // will emit int values. Start of body of the generator.
      for (i = 10; i > 0; --i)
         $yield(i); // a.k.a. yield in Python,
                    // returns next number in [1..10], reversed.
   $stop; // stop, end of sequence. End of body of the generator.
};

可迭代:

int main(int argc, char* argv[])
{
  descent gen;
  for(int n; gen(n);) // "get next" generator invocation
    printf("next number is %d\n", n);
  return 0;
}

C++11提供的foreach loop可用于任何具有beginend成员函数的类。还需要有operator!=, operator++operator*。例如:

#include <iostream>
int main()
{
    for (int i: range(10))
    {
        std::cout << i << std::endl;
    }
    return 0;
}

一个基本实现:

class range
{
private:
    int last;
    int iter;

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

    // Iterable functions
    const range& begin() const { return *this; }
    const range& end() const { return *this; }

    // Iterator functions
    bool operator!=(const range&) const { return iter < last; }
    void operator++() { ++iter; }
    int operator*() const { return iter; }
};

C#[编辑]

C# 2.0开始可以利用yield构造生成器。

// Method that takes an iterable input (possibly an array)
// and returns all even numbers.
public static IEnumerable<int> GetEven(IEnumerable<int> numbers) {
    foreach (int i in numbers) {
        if ((i % 2) == 0) {
            yield return i;
        }
    }
}

可以使用多个yield return语句:

public class CityCollection : IEnumerable<string> {
    public IEnumerator<string> GetEnumerator() {
        yield return "New York";
        yield return "Paris";
        yield return "London";
    }
}

Python[编辑]

2.2版开始支持生成器。[6]

def countfrom(n):
    while True:
        yield n
        n += 1

# Example use: printing out the integers from 10 to 20.
# Note that this iteration terminates normally, despite 
# countfrom() being written as an infinite loop.

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

# Another generator, which produces prime numbers indefinitely as needed.

def primes():
    yield 2
    n = 3
    p = []
    while True:
        # This works in Python 2.5+ 
        if not any(n % f == 0 for f in 
                     itertools.takewhile(lambda f: f*f <= n, p)): 
            yield n
            p.append(n)
        n += 2

Python的生成器可以认为是一个迭代器包含了冻结的栈帧。当用next()方法调用迭代器,Python恢复冻结的栈帧,继续执行至下一次的yield语句。生成器的栈帧再一次冻结,被yield的值返回给调用者。

PEP 380 (Python 3.3开始)增加了yield from表达式,允许生成器委托它的行为给另一个生成器。[9]

生成器表达式[编辑]

Python的一种语法模拟了列表推导英语list comprehension

squares = ( n*n  for n in countfrom(2) )

for j in squares:
    if j <= 20:
        print(j)
    else:
        break


参见[编辑]

参考文献[编辑]

  1. ^ https://stackoverflow.com/questions/1022564/what-is-the-difference-between-an-iterator-and-a-generator
  2. ^ Kiselyov, Oleg. General ways to traverse collections in Scheme. January 2004. 
  3. ^ Anthony Ralston. Encyclopedia of computer science. Nature Pub. Group. 2000 [11 May 2013]. ISBN 978-1-56159-248-7. 
  4. ^ The Icon Programming Language utilizes generators to implement its goal directed evaluation. In Icon, generators can be invoked in contexts outside of the normal looping control structures.
  5. ^ Liskov, Barbara. A History of CLU (PDF). April 1992 [2008-03-08]. (原始内容 (pdf)存档于2003-09-17). 
  6. ^ 6.0 6.1 Python Enhancement Proposals: PEP 255: Simple Generators, PEP 289: Generator Expressions, PEP 342: Coroutines via Enhanced Generators
  7. ^ yield (C# Reference)
  8. ^ http://www.codeproject.com/KB/cpp/cpp_generators.aspx
  9. ^ PEP 380 -- Syntax for Delegating to a Subgenerator
  • Stephan Murer, Stephen Omohundro, David Stoutamire and Clemens Szyperski: Iteration abstraction in Sather. ACM Transactions on Programming Languages and Systems, 18(1):1-15 (1996) [1]