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 正在进行最后一次更新，包含最新的建议、代码修改等，并包含指向一个模块的链接 [10]，该模块实现了 PEP 中描述的行为。希望使用此 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 作为分配给 count 的值时，我们的测试服务器将变得最小的努力成为生产服务器。

另一个例子是，在具有加权边（全部为正）的图上的 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] 指出，使用比元组更具 Python 风格的数据结构来存储有关节点距离的信息可以提高可读性。下面给出了两个等效的节点结构（一个使用 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 本身与标准发行版中的任何其他对象相比都更小。

顺便说一句，作者不清楚使用 Nodes 替换元组是否显着提高了可读性，如果有的话。

一个 `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

上次修改时间：2023-09-09 17:39:29 GMT