生成器 (電腦編程)
来自维基百科,自由的百科全书
生成器(Generator),是電腦科學中特殊的子程式。實際上,所有生成器都是迭代器[1]。生成器非常類似於返回陣列的函數,都是具有參數、可被呼叫、產生一系列的值。但是生成器不是構造出陣列包含所有的值並一次性返回,而是每次產生一個值,因此生成器看起來像函數,但行為像迭代器。
生成器可以用更有表達力的控制流結構實現,如協程或頭等續體[2]。生成器,也被稱作半協程(semicoroutine)[3],是特殊的、能力更弱的協程,總是在傳回一個值時把控制交還給呼叫者,而不是像協程那樣指出另一個協程繼續執行。
使用
生成器通常在一個循環內部被呼叫。[4]生成器第一次被呼叫是在進入這個循環結構時,建立一個對象以封裝生成器的狀態、繫結的實參。生成器的實體接着被執行直至遇到一個特別的yield
動作,在這裏提供給yield
動作的值被返回給呼叫者。在下一次呼叫同一個生成器的時候,生成器從yield
動作之後恢復執行,直到遇上另一個yield
動作。生成器的執行也可以遇到finish
動作而終止。
由於生成器在需要的才計算它的要被yield
的值,因此可以用來代表一個串流,這種序列要一次性全部計算出來是昂貴的甚至是不可能的,這種情況還包括無窮序列或現場數據串流。
如果需要及早求值(主要是在序列是有限的時候,否則求值將永不終止),可以使用列表或使用並列結構來建立一個列表替代生成器。例如,Python的一個生成器g
,通過l = list(g)
,可被求值成列表l
。而在F♯中,序列表達式seq { ... }
,將除了[ ... ]
之外的惰性的(生成器或序列)求值為及早的(列表)。
在有生成器出現的情況下,語言的循環構造,比如for
和while
,可以歸約成一個單一的loop ... end loop
構造;可以用合適的生成器以正確的方式,順暢的模擬所有常見的循環構造。例如,一個按範圍的循環如for x = 1 to 10
,可以通過生成器而被實現為迭代,比如Python的for x in range(1, 10)
。進一步的,break
可以被實現為向生成器傳送finish
,而接着在循環中使用continue
。
歷史
生成器最早出現於CLU語言(1975年)[5],也是字串操縱語言Icon(1977年)的顯著特徵。它現在出現在Python[6]、C♯[7]、Ruby、最新版本的ECMAScript(ES6/ES2015)與其他語言之中。在CLU與C#中,生成器稱作迭代器,在Ruby稱作列舉元。
語言實例
CLU使用yield
陳述式來在用戶定義數據抽象上進行迭代[8]:
string_chars = iter (s: string) yields (char);
index: int := 1;
limit: int := string$size (s);
while index <= limit do
yield (string$fetch(s, index));
index := index + 1;
end;
end string_chars;
for c: char in string_chars(s) do
...
end;
在Icon中,所有表達式(包括循環)都是生成器。語言有很多內建生成器,甚至使用生成器機制實現某些邏輯語意(邏輯析取或OR
以此達成)。
列印從0
到20
的平方,可以如下這樣使用協程完成:
但是多數時候,客製化生成器是使用suspend
關鍵字來實現,它的功能完全類似CLU中的yield
關鍵字。
使用宏預處理的例子見[9]:
$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可用於任何具有begin
與end
成員函數的類。還需要有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♯ 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自2001年的2.2版開始支援生成器[6]。下面是生成器一個例子,它是個計數器:
def countfrom(n):
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():
yield 2
n = 3
p = []
while True:
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
表達式,允許生成器將它的一部份操作委託給另一個生成器。[10]
Python擁有建模於列表推導式的一種語法,叫做生成器表達式,用來輔助生成器的建立。下面的例子擴充了上面第一個例子,使用生成器表達式來計算來自countfrom
生成器函數的數的平方:
squares = (n*n for n in countfrom(2))
for j in squares:
if j <= 20:
print(j)
else:
break
ECMAScript 6介入了函數生成器。
使用函數生成器書寫一個無窮斐波那契序列:
function* fibonacci(limit) {
let [prev, curr] = [0, 1];
while (!limit || curr <= limit) {
yield curr;
[prev, curr] = [curr, prev + curr];
}
}
// 加上限10为边界
for (const n of fibonacci(10)) {
console.log(n);
}
// 没有上界的生成器
for (const n of fibonacci()) {
console.log(n);
if (n > 10000) break;
}
// 手动迭代
let fibGen = fibonacci();
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 1
console.log(fibGen.next().value); // 2
console.log(fibGen.next().value); // 3
console.log(fibGen.next().value); // 5
console.log(fibGen.next().value); // 8
// 从停止的地方继续
for (const n of fibGen) {
console.log(n);
if (n > 10000) break;
}
下面例子使用Pharo Smalltalk,黃金分割率生成器對goldenRatio next
呼叫,每次返回一個更加逼近的黃金分割率:
goldenRatio := Generator on: [ :g |
| x y z r |
x := 0.
y := 1.
[
z := x + y.
r := (z / y) asFloat.
x := y.
y := z.
g yield: r
] repeat
].
goldenRatio next.
下面的表達式返回的下次10
個逼近。
(1 to: 10) collect: [ :dummy | goldenRatio next].
參見
註釋
參考文獻
Wikiwand - on
Seamless Wikipedia browsing. On steroids.