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設為空對映。
- 當尚未訪問的節點的ι短距離小於無窮大且目標節點尚未訪問時。
- 獲取距離最短的節點。
- 訪問該節點。
- 如有必要，更新尚未訪問的鄰居的鄰居距離和父指標。
- 如果目標節點已被訪問，則透過父指標回溯以找到要走的路徑的反向。
下面是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
參考資料
更改
版權
本文件已置於公共領域。
來源：https://github.com/python/peps/blob/main/peps/pep-0326.rst