Python Grouper Idiom

by Xueqiao Xu

at 2012-01-28 22:50:36

original http://typedef.me/2012/01/28/python-grouper-idiom

在 StackOverflow 上有人问了这样一个问题：

在 Python 中，如何将形如 "00163e2fbab7" 这样的一个 MAC 地址转换成 "00:16:3e:2f:ba:b7" 的形式。

面对这个简单的问题，普通青年给出的答案或许是：

':'.join([address[i:i+2] for i in range(0, 12, 2)])

但是，文艺青年 @unutbu 却给出了一个不同寻常的解法：

':'.join(''.join(pair) for pair in zip(*[iter(addr)]*2))

这个解法第一眼看上去似乎不是那么好理解，但是一旦细细琢磨进去，发现了其中的巧妙之处，就不由得大呼精彩。

这个答案中总共有两点精彩之处，分别为：

Generator Expression
Grouper Idiom

Generator Expression

也许很多人第一眼看到那个答案，疑惑的一点是那个列表解析两旁怎么没有方括号[]。其实这是利用了一个从 Python2.4 开始就存在，却经常为人所忽略的技巧： Generator Expression (生成器表达式)。

在语法层面，生成器表达式的与列表解析相同，唯一的不同之处在于其是被()括起来而不是[]。
在底层的实现层面，生成器表达式不像列表解析那般需要在内存中生成完整的列表，而是使用生成器的形式按需访问元素。

以求平方和的语句为例：

sum([x * x for x in range(10)])

在上面这个例子中，普通的列表解析版本会先生成一个完整的平方数列表： [1, 4, 9, 16 ...]，然后再将 sum 函数应用在这个列表上。

生成器表达式的版本是这样:

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

在这个版本中，sum 括号里面产生的是一个生成器，而非一个列表。sum 函数使用这个生成器来逐个获取元素并进行求和。

我们也可以直接对这个生成器进行操作，如下：

>>> g = (x * x for x in range(10))
>>> g
<generator object <genexpr> at 0x92d1324>
>>> g.next()
0
>>> g.next()
1
>>> g.next()
4
>>> g.next()
9

生成器会记住上次返回时的位置，在每次调用 next 方法后继续计算下一个需要的值。

因此，当数据规模很大时，使用列表解析将产生不可忽视的内存开销。而此时使用生成器表达式则可以避免这个问题。

Grouper Idiom

关于一开始所说的字符串问题，其核心便在于如何将原始的字符串按照两个字符一组的分开来，Grouper Idiom 的应用则是这个答案的精华所在。

再看一眼一开始时的代码：

addr = "00163e2fbab7"
':'.join(''.join(pair) for pair in zip(*[iter(addr)]*2))

我们将这个代码中 zip 的那段提取出来：

zip(*[iter(addr)]*2)

它产生的是这样的一个列表，完美的解决了分组问题：

[('0', '0'), ('1', '6'), ('3', 'e'), ('2', 'f'), ('b', 'a'), ('b', '7')]

那这一步到底是如何工作的呢？

对于熟悉函数式编程的同学肯定对 zip 不会陌生，它可以将一个或多个可迭代的容器像拉链一般组合：

>>> zip([1,2,3], [4,5,6], [7,8,9])
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

而括号内部的第一个星号*用于分拆一个列表(unpack a list)。当作用于函数参数上时，其效果类似于函数式编程里面的apply，亦即 f(*[a,b,c]) 与 f(a,b,c) 等价。

>>> zip(*[[1,2,3], [4,5,6], [7,8,9]])
[(1, 4, 7), (2, 5, 8), (3, 6, 9)]

于是，zip(*[it]*2) 等价于 zip(*[it, it]) 等价于 zip(it, it)

>>> it = iter("00163e2fbab7")
>>> zip(it, it)
[('0', '0'), ('1', '6'), ('3', 'e'), ('2', 'f'), ('b', 'a'), ('b', '7')]

我们先要了解一个事实：zip 从两个列表中取值时，是同真的“拉链”类似，按需取值，亦即每次分别从两个列表取一个值加到一起生成一个元组，再分别从两个列表取一个值生成一个元组，如此下去。

再注意此处 zip 的两个参数都是同一个迭代器，因此这里 zip 的时候每次会取出相邻的两个值。

关于这里zip和迭代器的组合用法，我们可以推而广之，提炼出来一个通用的过程：

先用 `iter` 函数生成原始容器的一个迭代器，将这个迭代器放入一个列表中，并将列表变为原先的 n 倍(n 为每个分组的长度)，然后分拆列表并将其应用于`zip`函数上，用于生成分组。

这便是 Grouper Idiom。我们再将其变成 Python 代码，如下（取自 itertools文档）：

from itertools import *

def grouper(n, iterable, fillvalue=None):
    args = [iter(iterable)] * n
    return izip_longest(fillvalue=fillvalue, *args)

这里使用 izip_longest 而不是 zip，使其可以设置默认填充值，并返回迭代器而不是列表。

示例：将 "ABCDEFG" 这个字符串以每组长度为 3 分组，不足时填充 'x' ：

>>> list(grouper(3, 'ABCDEFG', 'x'))
[('A', 'B', 'C'), ('D', 'E', 'F'), ('G', 'x', 'x')]

Google Reader