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))
    )

通过图像尺寸确定坐标范围，利用product(range(w), range(h))得到所有可能的像素坐标组合，实际上相当于两个嵌套的for循环。

这种处理方法的优点是每个像素都有各自的坐标位置，所以按照任意顺序处理像素都能还原整个图像，从而可以利用多进程技术或者多线程技术将计算负载分散到多个内核或者处理器上。Python的concurrent.futures模块支持基于多核（处理器）的分布式计算。