The History of Python

2010年7月6日星期二

From List Comprehensions to Generator Expressions

英文原文链接: http://python-history.blogspot.com/2010/06/from-list-comprehensions-to-generator.html

原文作者: Guido van Rossum

From List Comprehensions to Generator Expressions

从 List Comprehension 到 Generator Expression

List comprehension 在 Python 2.0版本添加进来。这一特性始于Greg Ewing的一套补丁,Skip Montanaro 和 Thomas Wouters参与贡献。(如果我没记错,Tim Peters也很提倡这个想法。)本质上,可以看做众所周知的数学家采用的集合符号的Pythonic化解释。例如,通常认为如下

{x | x > 10}


代表所有满足x > 10的x组成的集合。数学里这种形式隐含了读者可接受的全集(例如根据上下文,可能是所有实数或者所有整数)。在Python中没有全集的概念,在 Python 2.0 时连集合的概念也没有。(Sets是一个有趣的故事,我将来会在另一篇博文讨论。)

基于此以及其它方面考虑,Python中采用如下语法形式来表示:

[f(x) for x in S if P(x)]


这条语句产生一个list(列表),包含的值来自 sequence (序列) S,满足 predicate (判定) P,且被function(函数) f map (映射)。if-从句是可选项,且可以存在多个for-从句(每个for-从句可以有自己可选的if-从句)来表示嵌套循环(多for-从句会把多维元素映射到一维列表中,这一需求比较少见,因此实用中不常用)。

List comprehension 提供了内置函数map() 和 filter() 的替代。 map(f, S) 等价于 [f(x) for x in S],filter(P, S) 等价于 [x for x in S if P(x)]。或许有人认为 map() 和 filter() 的语法形式更紧凑,所以 list comprehension 没有多少值得推荐的。然而,如果考察一个更加实际的例子,观点或许就会改变了。假设我们想对一个list中的每个元素增加1,生产一个新的list。list comprehension 的写法是 [x+1 for x in S] 。map() 的写法是 map(lambda x: x+1, S)。这儿的"lambda x: x+1" 部分是Python语法中用于内嵌的匿名函数。

两种形式(list comprehension和map()/reduce())孰优孰劣引起了争论,有人认为争论的关键在于 Python 的 lambda 语法过于繁琐,如果匿名函数能有更简洁的表示形式,那么map()就更有吸引力了。我不同意,我发觉 list comprehension 形式比函数式语法更易读,尤其是当映射函数变得复杂时。另外 list comprehension 比 map和lambda 执行速度更快。这是因为调用一个 lambda 函数就创建了一个新的堆栈结构(stack frame),而 list comprehension 中的表达式无需创建新的堆栈结构。

在list comprehension获得成功,在发明generator(关于generator,将来会在另外一篇展开)之后,Python 2.4 增加了一种近似的语法用以表示结果构成的序列(sequence),但是并不将它具体化(concrete)为一个实际的list。新特征称作 "generator expression"。例如:


sum(x**2 for x in range(1, 11))


这条语句调用内置函数 sum(),参数为一个generator expression, 它 yield 从1到10(包括10)的平方。 sum() 函数把参数中的值加和起来,得到答案385。该语句相对于 sum([x**2 for x in range(1, 11)]) 的优势应当是明显的。后者生成了一个包含所有平方数的list,然后再遍历一次,最后(得到结果后)丢弃该list。对于数量较大的数据,前者在内存方面的节省是一个重要考虑因素。

我还应该提到 list comprehension 和 generator expression 微妙的区别。例如,在Python 2,如下是一个有效的 list comprehension:


[x**2 for x in 1, 2, 3]


然而,这是一个无效的 generator expression:


(x**2 for x in 1, 2, 3)


我们可以通过给"1, 2, 3"部分添加括号来修复它:


(x**2 for x in (1, 2, 3))


在Python 3,你甚至对list comprehension也必须使用括号了:


[x**2 for x in (1, 2, 3)]


然而,对于"常规的"或者"显式的"for-循环,你仍然可以省略括号:


for x in 1, 2, 3: print(x**2)


为何有这种区别,而且为何在Python 3 对 list comprehension 变得更严格了?影响设计包括反向兼容,避免歧义,注重等效,和语言的进化等因素。最初,Python(还没有版本号的时候:-)只有明确的for-循环形式。在'in'之后的部分不会带来歧义,因为它总是最后伴随着一个冒号。我清楚你要做的是对一些已知数值进行循环,因此,你不需要因为必须增加括号而烦恼。写到这里,又让我想起来在Algol-60,你可以这样写:


for i := 1, 2, 3 do Statement


Algol-60 还额外支持利用step-until从句决定表达式的步长,如下:


for i := 1 step 1 until 10, 12 step 2 until 50, 55 step 5 until 100 do Statement


(追忆往事,如果当初Python的foo-循环也能这样支持对多个序列的遍历,也挺酷的,哎。。。)

当我们在Python 2.0 中增加 list comprehension 时,原来的规则依然有效:序列表达式只可能被伴随的右中括号 ']' 或者 'for' 关键词或者 'if' 关键词结束。而且这是好事。

但是,到了 Python 2.4 增加 generator expression 时,我们遇到了歧义性方面的问题: 语法上看一个 generator expression 的括号部分并不是它语法上必须的部分。例如下面例子:


sum(x**2 for x in range(10))


外括号是属于被调用的函数sum()的一部分,里面的 "裸" generator expression 作为第一个参数。因此理论上,如下语句可以有两种解释:


sum(x**2 for x in a, b)


可以有意解释为这样:


sum(x**2 for x in (a, b))


也可以解释为:


sum((x**2 for x in a), b)


(如果我没记错)犹豫了一阵子之后,我决定这种情况不应该猜测,而是 generator comprehension 的 'in' 关键词之后必须是单个表达式(当然,它是 iterable 的)。但是当时我们也不想破坏已存在于 list comprehension 中的代码,因为它已经广为流行了。

设计 Python 3 时,我们决定 list comprehension:


[f(x) for x in S if P(x)]


完全等价于如下利用内置函数 list() 展开的 generator expression:


list(f(x) for x in S if P(x))


于是我们将稍微更严格的 generator expression 语法也同样适用于 list comprehension。

在 Python 3 我们还做了另外的变动,以增加 list comprehension 和 generator expression 的等效程度。Python 2时,list comprehension 会"泄露" 循环控制变量到外边:


x = 'before'
a = [x for x in 1, 2, 3]
print x # this prints '3', not 'before'


这是最初的 list comprehension 实现造成现象;也是数年间 Python 的"肮脏的小秘密"之一。开始由于这样可以使得 list comprehension 性能"越快越好"而作为折衷保留了,虽然偶然会刺痛人毕竟对新手来说算不上常见缺陷。然而对于 generator expression 我们不会再这样做了。 Generator expression 利用 generator 实现,执行 generator 时需要一个隔离的执行帧(separate execution frame)。由此还使得 generator expression (特别是在遍历比较短的序列时) 比 list comprehension 效率略低。

然而到了 Python 3,我们决心利用和 generator expression 的同样实现策略来修缮这个 list comprehension 的 "肮脏的小秘密"。 于是在 Python 3,上例(当然,最后一句修改为 print(x) :-) 将会打印 'before', 这证明 list comprehension 中的'x'只是暂时遮蔽而不是直接使用 list comprehension 之外的'x'。

在你开始担心 list comprehension 在 Python 3 中变慢之前要说的是:感谢大量的 Python 3 实现方面的努力,list comprehension 和 generator expressions 都比 Python 2 中更快了!(而且两者也不再有速度上的差别。)

更新: 当然,我忘了说 Python 3 还支持 set comprehension 和 dictionary comprehension。这是 list comprehension 思路的自然推广。

2 条评论:

y 说...

译的不错。谢谢

一个typo,“我还应该提到 list comprehension 和 enerator expression 微妙的区别”,[g]enerator

python3 说...

@y:感谢,修改了。