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] 이에 의존해서는 안 됩니다.
두 싱글턴 상수 Max와 Min을 도입하면 None을 절대 최솟값으로 사용하던 방식을 대체하고 절대 최댓값도 새로 마련할 수 있습니다. 동시에 상수의 이름만으로 그 의미가 드러나야 한다는 요구도 충족합니다.
절대 최솟값이나 최댓값을 다룰 때 흔히 쓰는 방법은 입력이 도달하리라고 스크립트 작성자가 예상하는 것보다 더 큰 값을 설정한 뒤, 입력이 그 값에 도달하지 않기를 바라는 것입니다.
Guido는 당분간 최댓값으로 사용할 수 있는 상수가 두 가지 있다고 언급했습니다 [2]. 바로 sys.maxint와 부동 소수점 양의 무한대입니다(1e309는 양의 무한대로 평가됩니다). 하지만 두 방법 모두 단점이 있습니다.
- 대부분의 아키텍처에서 sys.maxint는 임의로 정해진 작은 값(2**31-1 또는 2**63-1)이어서 큰 ‘long’ 정수나 부동 소수점 수보다 쉽게 작아질 수 있습니다.
- 표현할 수 있는 가장 큰 부동 소수점 수보다 큰 long 정수를 float와 비교하면 예외가 발생합니다:
>>> 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를 사용하면 최소한의 노력으로 테스트 서버를 프로덕션 서버로 바꿀 수 있습니다.
또 다른 예로, 가중치가 있는 간선(모두 양수)으로 이루어진 그래프에서 다익스트라 최단 경로 알고리즘을 들 수 있습니다.
- 그래프의 모든 노드까지의 거리를 무한대로 설정합니다.
- 시작 노드까지의 거리를 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]는 노드 간 거리 정보를 저장할 때 튜플보다 더 Python다운 자료 구조를 사용하면 가독성이 높아진다고 지적합니다. 동등한 두 가지 노드 구조(하나는 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 중 하나를 사용할 수 있습니다. NoneNode의 __cmp__ 메서드에서 None을 센티널로 사용하기 위해 추가로 필요한 특수한 경우 처리에 주목하십시오.
이 예제는 표준 배포판에서 None 자체는 다른 어떤 객체보다도 작게 비교되는데도, “실제 환경에서” None을 최댓값의 센티널 값으로 사용할 때 필요한 특수한 경우 처리를 잘 보여 줍니다.
덧붙이자면, 튜플 대신 Node를 사용한 것이 가독성을 크게 높였는지, 아니 조금이라도 높였는지 저자로서는 확실하지 않습니다.
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 코드와 두 버전의 다익스트라 알고리즘 모두
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이 PEP 326을 거부했습니다 [8].
Copyright
This document has been placed in the public domain.