PEP 326 – 최댓값과 최솟값에 대한 제안
- Author:
- Josiah Carlson <jcarlson at uci.edu>, Terry Reedy <tjreedy at udel.edu>
- Status:
- Rejected
- Type:
- Standards Track
- Created:
- 20-Dec-2003
- Python-Version:
- 2.4
- Post-History:
- 20-Dec-2003, 03-Jan-2004, 05-Jan-2004, 07-Jan-2004, 21-Feb-2004
번역·라이선스 안내
이 비공식 한국어 번역은 원문 Copyright 절의 Public Domain 조건에 따라 제공합니다. 원저자와 공식 원문은 그대로 표시합니다. 수정되지 않은 기준 원문 · 공식 최신판
결과
이 PEP는 BDFL [8]에 의해 거부되었습니다. 의사 종료 조항 [9]에 따라 PEP 326은 최신 제안, 코드 수정 등을 반영하여 마지막으로 한 번 업데이트되며, PEP에 설명된 동작을 구현하는 모듈 [10]로 연결되는 링크를 포함합니다. 이 PEP에 나열된 동작을 원하는 사용자는 Independent Implementations?에 나열된 이유에 따라 해당 모듈을 사용하시기 바랍니다.
초록
이 PEP는 최댓값과 최솟값 [3]을 나타내는 두 개의 싱글턴 상수인 Max와 Min을 제안합니다(또는 이와 유사하게 의미를 드러내는 두 이름 [4]을 제안합니다. Open Issues를 참조하십시오).
이름에서 알 수 있듯이 Max와 Min은 각각 다른 어떤 객체보다 크거나 작게 비교됩니다. 이러한 동작을 사용하면 코드를 더 쉽게 이해할 수 있고, 임시 최솟값이나 최댓값이 필요한 특수한 경우가 줄어들며, 실제 최솟값이나 최댓값인 수치가 제한되지 않습니다.
근거
None은 모든 값이 도달할 수 있는 절대 최솟값 [1]으로 사용할 수 있지만, Python 3.0에서 더 이상 사용되지 않을 수 있으므로 [4]이에 의존해서는 안 됩니다.
None을 절대 최솟값으로 사용하는 것을 대체하고 절대 최댓값을 도입하기 위해 Max와 Min이라는 두 싱글턴 상수를 도입하면 상수가 스스로 의미를 설명해야 한다는 우려를 해결할 수 있습니다.
절대 최솟값이나 최댓값을 처리할 때 흔히 사용하는 방법은 스크립트 작성자가 입력이 도달하리라고 예상하는 값보다 큰 값을 설정하고, 실제로 그 값에 도달하지 않기를 바라는 것입니다.
Guido는 [2]중간 단계에서 최댓값으로 사용할 수 있는 두 상수가 존재한다는 사실을 언급했습니다: sys.maxint와 부동 소수점 양의 무한대입니다(1e309는 양의 무한대로 평가됩니다). 그러나 각각 단점이 있습니다.
- 대부분의 아키텍처에서 sys.maxint는 임의로 작으며(2**31-1 또는 2**63-1), 큰 ‘long’ 정수나 부동 소수점 수에 쉽게 추월될 수 있습니다.
- 표현 가능한 가장 큰 부동 소수점 수보다 큰 long 정수를 어떤 부동 소수점 수와 비교하면 예외가 발생합니다.:
>>> 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 샘플 Reference Implementation이 포함되어 있습니다.
동기
논리적(또는 수치적) 무한대나 음의 무한대로 일부 값 집합을 초기화하는 것으로 시작하는 알고리즘은 수백 가지에 달합니다. 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()
count에 할당할 값으로 Max를 사용하면 최소한의 노력으로 테스트 서버를 운영 서버로 전환할 수 있습니다.
또 다른 예로, 가중치가 있는 간선(모두 양수)으로 구성된 그래프에서의 Dijkstra 최단 경로 알고리즘이 있습니다.
- 그래프의 모든 노드까지의 거리를 무한대로 설정하십시오.
- 시작 노드까지의 거리를 0으로 설정하십시오.
- visited를 빈 매핑으로 설정하십시오.
- 방문하지 않은 노드의 최단 거리가 무한대보다 작고 목적지가 방문되지 않은 동안입니다.
- 최단 거리를 가진 노드를 가져옵니다.
- 노드를 방문합니다.
- 필요한 경우 이웃 거리와 부모 포인터를 업데이트합니다. 방문하지 않은 이웃에 대해 수행합니다.
- 목적지가 방문되었다면 부모 포인터를 따라 되짚어 가며 이동할 경로의 역순을 찾습니다.
아래에는 가중치가 있는 간선 그래프에서 테이블을 사용하는 다익스트라 최단 경로 알고리즘의 예가 나와 있습니다(힙을 사용하는 더 빠른 버전도 있지만, 위 설명과 유사하므로 이 버전을 제시합니다. 힙 버전은 이 문서의 이전 버전에서 사용할 수 있습니다).
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]는 노드 거리 정보를 저장할 때 튜플보다 더 파이썬다운 데이터 구조를 사용하면 가독성이 향상된다는 점을 지적합니다. 서로 동등한 두 노드 구조(하나는 None, 다른 하나는 Max를 사용하는 구조)와 이를 적절히 수정한 다익스트라 최단 경로 알고리즘에서 사용하는 방법이 아래에 제시되어 있습니다.
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)에는0 <= r(u, v) <= 1인 관련 값r(u, v)가 있으며, 이는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의 대체 버전을 전달하면 잘못된 출력을 생성할 수 있습니다.
아래에 제시된 참조 구현은 Max/Min의 독립적인 구현과 호환되지 않는다는 점이 지적되었습니다 [7]. 이 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
참고 자료
변경 사항
- 이 절을 추가했습니다.
- Motivation 섹션을 추가했습니다.
- 마크업을 reStructuredText로 변경했습니다.
Max와Min의 동시 개념을 바탕으로 Abstract, Motivation, Reference Implementation, Open Issues를 명확히 했습니다.Max를 사용해 특수한 경우를 제거할 수 있는 지점을 보여주는 데이크스트라 최단 경로 알고리즘의 두 가지 구현을 추가했습니다.- Motivation에
Min의 사용 예시를 추가했습니다. - 예시 하나와 Other Examples 하위 제목을 추가했습니다.
- Reference Implementation을 수정하여 하나의 클래스/타입에서 두 항목을 모두 인스턴스화하도록 했습니다.
- 이 PEP의 범위에 속하지 않는 다수의 미해결 이슈를 제거했습니다.
- Max Examples의 예시를 교체하고, A Min Example의 예시를 변경했습니다.
- References를 일부 추가했습니다.
- BDFL이 [8] PEP 326을 거부했습니다.
Copyright
This document has been placed in the public domain.