PEP 326 – 顶值与底值案例

作者:: Josiah Carlson <jcarlson at uci.edu>, Terry Reedy <tjreedy at udel.edu>
状态:: 已拒绝
类型:: 标准跟踪
创建日期:: 2003年12月20日
Python 版本:: 2.4
发布历史:: 2003年12月20日，2004年1月3日，2004年1月5日，2004年1月7日，2004年2月21日

结果
摘要
基本原理
动机
参考实现
未解决的问题
参考资料
更改
版权

结果

此PEP已被BDFL拒绝 [8]。根据伪日落条款 [9]，PEP 326 正在最后一次更新，其中包含最新的建议、代码修改等，并包含一个指向实现了PEP中所述行为的模块的链接 [10]。建议需要此PEP中列出的行为的用户使用该模块，原因列在独立实现？中。

摘要

此PEP提出了两个表示顶值和底值 [3] 的单例常量：Max 和 Min（或两个相似暗示性的名称 [4]；请参阅未决问题）。

正如其名称所示，Max 和 Min 将分别与任何其他对象比较出更高或更低的值。这种行为使得代码更容易理解，并减少了需要临时最小或最大值且实际最小或最大数值不受限制的特殊情况。

基本原理

虽然 None 可以用作任何值都能达到的绝对最小值 [1]，但这在Python 3.0中可能会被弃用 [4]，不应依赖。

作为 None 用作绝对最小值的替代方案，以及引入绝对最大值，引入两个单例常量 Max 和 Min 解决了常量自文档化的担忧。

处理绝对最小或最大值的常见做法是设置一个比脚本作者预期输入值更大的值，并希望它永远不会达到。

Guido曾提出 [2] 存在两个可用于最大值的临时常量：sys.maxint和浮点正无穷大（1e309将评估为正无穷大）。然而，它们各有缺点。

在大多数架构上，sys.maxint任意小（2**31-1或2**63-1），并且很容易被大的“长”整数或浮点数超越。

将大于最大可表示浮点数的长整数与任何浮点数进行比较将导致异常。

>>> cmp(1.0, 10**309)
Traceback (most recent call last):
File "<stdin>", line 1, in ?
OverflowError: long int too large to convert to float

即使当大整数与正无穷大进行比较时

>>> cmp(1e309, 10**309)
Traceback (most recent call last):
File "<stdin>", line 1, in ?
OverflowError: long int too large to convert to float

当数字为负数时，也存在相同的缺点。

引入如上所述工作的 Max 和 Min 不需要太多努力。其中一个Python 参考实现已包含在内。

动机

有数百种算法通过将一组值初始化为逻辑（或数值）无穷大或负无穷大来开始。Python 缺乏能够始终如一地工作或真正达到最极端值的无穷大。通过添加 Max 和 Min，Python 将拥有真正的最大值和最小值，并且由于特殊情况的减少，此类算法可以变得更清晰。

`Max` 示例

在测试各种服务器时，有时需要仅在退出前服务一定数量的客户端，这会产生如下代码

count = 5

def counts(stop):
    i = 0
    while i < stop:
        yield i
        i += 1

for client_number in counts(count):
    handle_one_client()

当使用 Max 作为分配给计数的值时，我们的测试服务器可以以最小的努力成为生产服务器。

另一个例子是Dijkstra的带权有向图最短路径算法（所有权重均为正）。

将图中每个节点的距离设为无穷大。
将到起始节点的距离设为零。
将visited设为空映射。
当尚未访问的节点的ι短距离小于无穷大且目标节点尚未访问时。
1. 获取距离最短的节点。
2. 访问该节点。
3. 如有必要，更新尚未访问的邻居的邻居距离和父指针。
如果目标节点已被访问，则通过父指针回溯以找到要走的路径的反向。

下面是Dijkstra最短路径算法在带权重图上使用表格的示例（可以使用堆的更快版本，但由于其与上述描述的相似性，这里提供了此版本；堆版本可通过本文档的旧版本获取）。

def DijkstraSP_table(graph, S, T):
    table = {}                                                 #3
    for node in graph.iterkeys():
        #(visited, distance, node, parent)
        table[node] = (0, Max, node, None)                     #1
    table[S] = (0, 0, S, None)                                 #2
    cur = min(table.values())                                  #4a
    while (not cur[0]) and cur[1] < Max:                       #4
        (visited, distance, node, parent) = cur
        table[node] = (1, distance, node, parent)              #4b
        for cdist, child in graph[node]:                       #4c
            ndist = distance+cdist                             #|
            if not table[child][0] and ndist < table[child][1]:#|
                table[child] = (0, ndist, child, node)         #|_
        cur = min(table.values())                              #4a
    if not table[T][0]:
        return None
    cur = T                                                    #5
    path = [T]                                                 #|
    while table[cur][3] is not None:                           #|
        path.append(table[cur][3])                             #|
        cur = path[-1]                                         #|
    path.reverse()                                             #|
    return path                                                #|_

读者应该注意，在上述代码中用任意大的数字替换 Max 并不能保证到节点的ι短路径距离永远不会超过该数字。嗯，有一个例外：当然可以将图中每条边的权重相加，并将“任意大的数字”设置为该总和。然而，这样做并不能使算法更容易理解，并且存在数值溢出的潜在问题。

Gustavo Niemeyer [7] 指出，使用比元组更具Pythonic风格的数据结构来存储节点距离信息，可以提高可读性。下面给出了两种等效的节点结构（一种使用 None，另一种使用 Max）及其在适当修改的Dijkstra最短路径算法中的使用。

class SuperNode:
    def __init__(self, node, parent, distance, visited):
        self.node = node
        self.parent = parent
        self.distance = distance
        self.visited = visited

class MaxNode(SuperNode):
    def __init__(self, node, parent=None, distance=Max,
                 visited=False):
        SuperNode.__init__(self, node, parent, distance, visited)
    def __cmp__(self, other):
        return cmp((self.visited, self.distance),
                   (other.visited, other.distance))

class NoneNode(SuperNode):
    def __init__(self, node, parent=None, distance=None,
                 visited=False):
        SuperNode.__init__(self, node, parent, distance, visited)
    def __cmp__(self, other):
        pair = ((self.visited, self.distance),
                (other.visited, other.distance))
        if None in (self.distance, other.distance):
            return -cmp(*pair)
        return cmp(*pair)

def DijkstraSP_table_node(graph, S, T, Node):
    table = {}                                                 #3
    for node in graph.iterkeys():
        table[node] = Node(node)                               #1
    table[S] = Node(S, distance=0)                             #2
    cur = min(table.values())                                  #4a
    sentinel = Node(None).distance
    while not cur.visited and cur.distance != sentinel:        #4
        cur.visited = True                                     #4b
        for cdist, child in graph[node]:                       #4c
            ndist = distance+cdist                             #|
            if not table[child].visited and\                   #|
               ndist < table[child].distance:                  #|
                table[child].distance = ndist                  #|_
        cur = min(table.values())                              #4a
    if not table[T].visited:
        return None
    cur = T                                                    #5
    path = [T]                                                 #|
    while table[cur].parent is not None:                       #|
        path.append(table[cur].parent)                         #|
        cur = path[-1]                                         #|
    path.reverse()                                             #|
    return path                                                #|_

在上述代码中，传入NoneNode或MaxNode足以将 None 或 Max 用作节点距离的“无穷大”。请注意，在__cmp__方法中，None 作为NoneNode中的哨兵值需要额外的特殊情况处理。

此示例突出显示了在“野外”将 None 用作最大值的哨兵值时的特殊情况处理，即使None本身在标准发行版中比较小于任何其他对象。

顺便说一句，作者不清楚使用节点代替元组是否显著增加了可读性，如果有的话。

一个 `Min` 示例

使用 Min 的一个例子是解决以下问题的算法 [5]

假设您有一个有向图，表示一个通信网络。顶点是网络中的节点，每条边都是一个通信信道。每条边 (u, v) 都有一个关联值 r(u, v)，其中 0 <= r(u, v) <= 1，它表示从 u 到 v 的信道的可靠性（即，从 u 到 v 的信道**不**会失败的概率）。假设信道的可靠性概率是独立的。（这意味着任何路径的可靠性是路径上所有边的可靠性的乘积。）现在假设您在图中给定两个节点，A 和 B。

这样的算法是上述 DijkstraSP_table 算法的7行修改（修改的行前缀为 *）

def DijkstraSP_table(graph, S, T):
    table = {}                                                 #3
    for node in graph.iterkeys():
        #(visited, distance, node, parent)
*       table[node] = (0, Min, node, None)                     #1
*   table[S] = (0, 1, S, None)                                 #2
*   cur = max(table.values())                                  #4a
*   while (not cur[0]) and cur[1] > Min:                       #4
        (visited, distance, node, parent) = cur
        table[node] = (1, distance, node, parent)              #4b
        for cdist, child in graph[node]:                       #4c
*           ndist = distance*cdist                             #|
*           if not table[child][0] and ndist > table[child][1]:#|
                table[child] = (0, ndist, child, node)         #|_
*       cur = max(table.values())                              #4a
    if not table[T][0]:
        return None
    cur = T                                                    #5
    path = [T]                                                 #|
    while table[cur][3] is not None:                           #|
        path.append(table[cur][3])                             #|
        cur = path[-1]                                         #|
    path.reverse()                                             #|
    return path                                                #|_

请注意，有一种方法可以转换图，使其可以不加改变地传入原始 DijkstraSP_table 算法。还有一些简单的方法可以构造与 DijkstraSP_table_node 配合使用的Node对象。这些转换留给读者作为练习。

其他示例

Andrew P. Lentvorski, Jr. [6] 指出，涉及范围搜索的各种数据结构立即可以使用 Max 和 Min 值。更具体地说：线段树、范围树、k-d树和数据库键。

...问题在于一个范围可以在一侧开放，并且并不总是有一个初始化的案例。
我看到的解决方案要么是重载 None 作为极值，要么是使用一个任意大的数值。重载 None 意味着内置函数不能真正使用，除非进行特殊情况检查以规避 None 的未定义（或“错误定义”）排序。这些检查往往会淹没 max() 和 min() 等内置函数的良好性能。

选择一个大数值会丧失Python处理任意大整数的能力，并引入潜在的溢出/下溢错误源。

在图算法、范围搜索算法、计算几何算法等领域，Max 和 Min 还有更多使用示例。

独立实现？

希望实现此类功能的用户独立实现的 Min/Max 概念不太可能兼容，并且肯定会产生不一致的排序。以下示例旨在展示它们可能有多么不一致。

让我们假设我们已经使用示例实现中给出的相同代码（并进行了一些小的重命名）创建了MyMax、MyMin、YourMax和YourMin的正确独立实现
```
>>> lst = [YourMin, MyMin, MyMin, YourMin, MyMax, YourMin, MyMax,
YourMax, MyMax]
>>> lst.sort()
>>> lst
[YourMin, YourMin, MyMin, MyMin, YourMin, MyMax, MyMax, YourMax,
MyMax]
```
请注意，虽然所有“Min”都在“Max”之前，但不能保证YourMin的所有实例都在MyMin之前，反之亦然，或等效的MyMax和YourMax。

在使用heapq模块时，这个问题也很明显。

>>> lst = [YourMin, MyMin, MyMin, YourMin, MyMax, YourMin, MyMax,
YourMax, MyMax]
>>> heapq.heapify(lst)  #not needed, but it can't hurt
>>> while lst: print heapq.heappop(lst),
...
YourMin MyMin YourMin YourMin MyMin MyMax MyMax YourMax MyMax

此外，findmin_Max代码和Dijkstra的两个版本都可能通过传入 Max 的次要版本而导致不正确的输出。

有人指出 [7]，下面给出的参考实现将与 Max/Min 的独立实现不兼容。此PEP的目的是引入“唯一真实实现”的“唯一最大值”和“唯一最小值”。因此，将不鼓励用户基于 Max 和 Min 对象的实现，并且显然鼓励使用“唯一真实实现”。通过变量和/或源代码自省，应该很容易发现混合用户 Max 和 Min 实现与“唯一真实实现”所导致的模糊行为。

参考实现

class _ExtremeType(object):

    def __init__(self, cmpr, rep):
        object.__init__(self)
        self._cmpr = cmpr
        self._rep = rep

    def __cmp__(self, other):
        if isinstance(other, self.__class__) and\
           other._cmpr == self._cmpr:
            return 0
        return self._cmpr

    def __repr__(self):
        return self._rep

Max = _ExtremeType(1, "Max")
Min = _ExtremeType(-1, "Min")

测试运行结果

>>> max(Max, 2**65536)
Max
>>> min(Max, 2**65536)
20035299304068464649790...
(lines removed for brevity)
...72339445587895905719156736L
>>> min(Min, -2**65536)
Min
>>> max(Min, -2**65536)
-2003529930406846464979...
(lines removed for brevity)
...072339445587895905719156736L

未解决的问题

由于PEP被拒绝，所有未决问题现已关闭且无关紧要。该模块将使用名称 UniversalMaximum 和 UniversalMinimum，因为它们的作用很难被误解。对于需要更短名称的用户，建议在导入时重命名单例

from extremes import UniversalMaximum as uMax,
                     UniversalMinimum as uMin

参考资料

更改

添加了此部分。
添加了动机部分。
将标记更改为 reStructuredText。
根据 Max 和 Min 的同时概念，澄清了摘要、动机、参考实现和开放问题。
添加了Dijkstra最短路径算法的两个实现，展示了 Max 如何用于消除特殊情况。
在动机中添加了 Min 的使用示例。
添加了一个示例和其他示例子标题。
修改了参考实现，使其从单个类/类型实例化这两个项。
删除了许多不在本PEP范围内的开放问题。
替换了 Max 示例中的一个示例，更改了 Min 示例中的一个示例。
添加了一些参考文献。
BDFL 拒绝了 [8] PEP 326

版权

本文档已置于公共领域。

来源：https://github.com/python/peps/blob/main/peps/pep-0326.rst

上次修改：2025-02-01 08:59:27 GMT