Python 对积进行归约|极客教程

Python 对积进行归约，在关系数据库理论中，可以把表间的join操作看作带过滤条件的笛卡儿积。一条SQL语句中，如果SELECT语句后面没有WHERE从句，返回结果就是表中记录的笛卡儿积，或者说不带过滤条件的乘积运算是糟糕的算法。枚举所有的组合，再通过过滤保留符合条件的组合，可以通过itertools模块的product()函数实现。

可以通过下面的函数定义两个可迭代集合或者生成器间的join操作。

JT_ = TypeVar("JT_")
def join(
        t1: Iterable[JT_],
        t2: Iterable[JT_],
        where: Callable[[Tuple[JT_, JT_]], bool]
    ) -> Iterable[Tuple[JT_, JT_]]:
    return filter(where, product(t1, t2))

可迭代对象t1和t2的所有组合都参与计算。filter()函数通过给定的where()函数确定对类型为Tuple[JT_, JT_]的二元组的取舍。其中where()函数类型是Callable[[Tuple [JT_, JT_]], bool]，说明返回值是布尔值。当数据库中没有任何可用的索引或者顺序标记时，SQL查询只能在这种不理想的场景中低效运作。

这种算法实现虽然可用，但效率很低，通常需要仔细研究问题和数据，寻找更高效的算法。

首先稍微抽象一下问题，用多个数据项间最大/最小距离查找问题代替简单的布尔值匹配，比较的结果是一个实数。

假设有如下由Color对象组成的数据集：

from typing import NamedTuple
class Color(NamedTuple):
    rgb: Tuple[int, int, int]
    name: str
[Color(rgb=(239, 222, 205), name='Almond'),
 Color(rgb=(255, 255, 153), name='Canary'),
 Color(rgb=(28, 172, 120), name='Green'),...
 Color(rgb=(255, 174, 66), name='Yellow Orange')]

更多信息可参考前面介绍中解析颜色文件生成namedtuple对象的部分。这里保持数据的RGB三元组形式，不做进一步分解。

包含一组像素的图片可以表示为如下形式：

pixels = [(r, g, b), (r, g, b), (r, g, b), ...]

作为应用广泛的类库，PIL（Python Image Library）提供了多种像素呈现方式，包括从 (x, y) 形式的坐标值转换为RGB三元组。关于这个类库的更多信息，请参考Pillow项目文档（https://pypi.python.org/pypi/Pillow）。

对于一个给定的PIL Image对象，可使用如下脚本遍历其中每个元素：

from PIL import Image
from typing import Iterator, Tuple
Point = Tuple[int, int]
RGB = Tuple[int, int, int]
Pixel = Tuple[Point, RGB]
def pixel_iter(img: Image) -> Iterator[Pixel]:
    w, h = img.size
    return (
        (c, img.getpixel(c))
        for c in product(range(w), range(h))
    )