Question

我们要再次实现 __hash__ 方法。加上现有的 __eq__ 方法，这会把 Vector 实例变成可散列的对象。

示例 9-8 中的 __hash__ 方法简单地计算 hash(self.x) ^ hash(self.y)。这一次，我们要使用^（异或）运算符依次计算各个分量的散列值，像这样：v[0] ^ v[1] ^ v[2]...。这正是 functools.reduce 函数的作用。之前我说 reduce 没有以往那么常用，5 但是计算向量所有分量的散列值非常适合使用这个函数。reduce 函数的整体思路如图 10-1 所示。

5sum、any 和 all 涵盖了 reduce 的大部分用途。参见 5.2.1 节的讨论。

图 10-1：归约函数（reduce、sum、any、all）把序列或有限的可迭代对象变成一个聚合结果

我们已经知道 functools.reduce() 可以替换成 sum()，下面说说它的原理。它的关键思想是，把一系列值归约成单个值。reduce() 函数的第一个参数是接受两个参数的函数，第二个参数是一个可迭代的对象。假如有个接受两个参数的 fn 函数和一个 lst 列表。调用 reduce(fn, lst) 时，fn 会应用到第一对元素上，即 fn(lst[0], lst[1])，生成第一个结果 r1。然后，fn 会应用到 r1 和下一个元素上，即 fn(r1, lst[2])，生成第二个结果 r2。接着，调用 fn(r2, lst[3])，生成 r3……直到最后一个元素，返回最后得到的结果 rN。

使用 reduce 函数可以计算 5!（5 的阶乘）：

>>> 2 * 3 * 4 * 5  # 想要的结果是：5! == 120
120
>>> import functools
>>> functools.reduce(lambda a,b: a*b, range(1, 6))
120

回到散列问题上。示例 10-11 展示了计算聚合异或的 3 种方式：一种使用 for 循环，两种使用 reduce 函数。

示例 10-11　计算整数 0~5 的累计异或的 3 种方式

>>> n = 0
>>> for i in range(1, 6):  # ➊
...   n ^= i
...
>>> n
1
>>> import functools
>>> functools.reduce(lambda a, b: a^b, range(6))  # ➋
1
>>> import operator
>>> functools.reduce(operator.xor, range(6))  # ➌
1

❶ 使用 for 循环和累加器变量计算聚合异或。

❷ 使用 functools.reduce 函数，传入匿名函数。

❸ 使用 functools.reduce 函数，把 lambda 表达式换成 operator.xor。

示例 10-11 中的 3 种方式里，我最喜欢最后一种，其次是 for 循环。你呢？

5.10.1 节讲过，operator 模块以函数的形式提供了 Python 的全部中缀运算符，从而减少使用 lambda 表达式。

为了使用我喜欢的方式编写 Vector.__hash__ 方法，我们要导入 functools 和 operator 模块。Vector 类的相关变化如示例 10-12 所示。

示例 10-12　 vector_v4.py 的部分代码：在 vector_v3.py 中 Vector 类的基础上导入两个模块，添加 __hash__ 方法

from array import array
import reprlib
import math
import functools  # ➊
import operator  # ➋


class Vector:
  typecode = 'd'

  # 排版需要，省略了很多行...

  def __eq__(self, other):  # ➌
    return tuple(self) == tuple(other)

  def __hash__(self):
    hashes = (hash(x) for x in self._components)  # ➍
    return functools.reduce(operator.xor, hashes, 0)  # ➎

  # 省略了很多行...

❶ 为了使用 reduce 函数，导入 functools 模块。

❷ 为了使用 xor 函数，导入 operator 模块。

❸ __eq__ 方法没变；我把它列出来是为了把它和 __hash__ 方法放在一起，因为它们要结合在一起使用。

❹ 创建一个生成器表达式，惰性计算各个分量的散列值。

❺ 把 hashes 提供给 reduce 函数，使用 xor 函数计算聚合的散列值；第三个参数，0 是初始值（参见下面的警告框）。

　使用 reduce 函数时最好提供第三个参数，reduce(function, iterable, initializer)，这样能避免这个异常：TypeError: reduce() of empty sequence with no initial value（这个错误消息很棒，说明了问题，还提供了解决方法）。如果序列为空，initializer 是返回的结果；否则，在归约中使用它作为第一个参数，因此应该使用恒等值。比如，对 +、| 和 ^ 来说， initializer 应该是 0；而对 * 和 & 来说，应该是 1。

示例 10-12 中实现的 __hash__ 方法是一种映射归约计算（见图 10-2）。

图 10-2：映射归约：把函数应用到各个元素上，生成一个新序列（映射，map），然后计算聚合值（归约，reduce）

映射过程计算各个分量的散列值，归约过程则使用 xor 运算符聚合所有散列值。把生成器表达式替换成 map 方法，映射过程更明显：

def __hash__(self):
  hashes = map(hash, self._components)
  return functools.reduce(operator.xor, hashes)

　在 Python 2 中使用 map 函数效率低些，因为 map 函数要使用结果构建一个列表。但是在 Python 3 中，map 函数是惰性的，它会创建一个生成器，按需产出结果，因此能节省内存——这与示例 10-12 中使用生成器表达式定义 __hash__ 方法的原理一样。

既然讲到了归约函数，那就把前面草草实现的 __eq__ 方法修改一下，减少处理时间和内存用量——至少对大型向量来说是这样。如示例 9-2 所示，__eq__ 方法的实现可以非常简洁：

def __eq__(self, other):
  return tuple(self) == tuple(other)

Vector2d 和 Vector 都可以这样做，它甚至还会认为 Vector([1, 2]) 和 (1, 2) 相等。这或许是个问题，不过我们暂且忽略。6 可是，这样做对有几千个分量的 Vector 实例来说，效率十分低下。上述实现方式要完整复制两个操作数，构建两个元组，而这么做只是为了使用 tuple 类型的 __eq__ 方法。对 Vector2d（只有两个分量）来说，这是个捷径，但是对维数很多的向量来说情况就不同了。示例 10-13 中比较两个 Vector 实例（或者比较一个 Vector 实例与一个可迭代对象）的方式更好。

613.1 节会认真对待 Vector([1, 2]) == (1, 2) 这个问题。

示例 10-13　为了提高比较的效率，Vector.__eq__ 方法在 for 循环中使用 zip 函数

def __eq__(self, other):
  if len(self) != len(other):  # ➊
    return False
  for a, b in zip(self, other):  # ➋
    if a != b:  # ➌
      return False
  return True  # ➍

❶ 如果两个对象的长度不一样，那么它们不相等。

❷ zip 函数生成一个由元组构成的生成器，元组中的元素来自参数传入的各个可迭代对象。如果不熟悉 zip 函数，请阅读“出色的 zip 函数”附注栏。前面比较长度的测试是有必要的，因为一旦有一个输入耗尽，zip 函数会立即停止生成值，而且不发出警告。

❸ 只要有两个分量不同，返回 False，退出。

❹ 否则，对象是相等的。

示例 10-13 的效率很好，不过用于计算聚合值的整个 for 循环可以替换成一行 all 函数调用：如果所有分量对的比较结果都是 True，那么结果就是 True。只要有一次比较的结果是 False，all 函数就返回 False。使用 all 函数实现 __eq__ 方法的方式如示例 10-14 所示。

示例 10-14　使用 zip 和 all 函数实现 Vector.__eq__ 方法，逻辑与示例 10-13 一样

def __eq__(self, other):
  return len(self) == len(other) and all(a == b for a, b in zip(self, other))

注意，首先要检查两个操作数的长度是否相同，因为 zip 函数会在最短的那个操作数耗尽时停止。

我们选择在 vector_v4.py 中采用示例 10-14 中实现的 __eq__ 方法。

本章最后要像 Vector2d 类那样，为 Vector 类实现 __format__ 方法。

出色的 zip 函数

使用 for 循环迭代元素不用处理索引变量，还能避免很多缺陷，但是需要一些特殊的实用函数协助。其中一个是内置的 zip 函数。使用 zip 函数能轻松地并行迭代两个或更多可迭代对象，它返回的元组可以拆包成变量，分别对应各个并行输入中的一个元素。如示例 10-15 所示。

　zip 函数的名字取自拉链系结物（zipper fastener），因为这个物品用于把两个拉链边的链牙咬合在一起，这形象地说明了 zip(left, right) 的作用。zip 函数与文件压缩没有关系。

示例 10-15　zip 内置函数的使用示例

>>> zip(range(3), 'ABC')  # ➊
<zip object at 0x10063ae48>
>>> list(zip(range(3), 'ABC'))  # ➋
[(0, 'A'), (1, 'B'), (2, 'C')]
>>> list(zip(range(3), 'ABC', [0.0, 1.1, 2.2, 3.3]))  # ➌
[(0, 'A', 0.0), (1, 'B', 1.1), (2, 'C', 2.2)]
>>> from itertools import zip_longest  # ➍
>>> list(zip_longest(range(3), 'ABC', [0.0, 1.1, 2.2, 3.3], fillvalue=-1))
[(0, 'A', 0.0), (1, 'B', 1.1), (2, 'C', 2.2), (-1, -1, 3.3)]

❶ zip 函数返回一个生成器，按需生成元组。

❷ 为了输出，构建一个列表；通常，我们会迭代生成器。

❸ zip 有个奇怪的特性：当一个可迭代对象耗尽后，它不发出警告就停止。7

❹ itertools.zip_longest 函数的行为有所不同：使用可选的 fillvalue（默认值为 None）填充缺失的值，因此可以继续产出，直到最长的可迭代对象耗尽。

为了避免在 for 循环中手动处理索引变量，还经常使用内置的 enumerate 生成器函数。如果你不熟悉 enumerate 函数，一定要阅读“Build-in Functions”文档。内置的 zip 和 enumerate 函数，以及标准库中其他几个生成器函数在 14.9 节讨论。

7至少对我来说，这是奇怪的。我认为，当组合不同长度的可迭代对象时，zip 应该抛出 ValueError。