Update of /cvsroot/python/python/nondist/peps In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv26739 Modified Files: pep-0326.txt Log Message: update from Josiah Carlson Index: pep-0326.txt =================================================================== RCS file: /cvsroot/python/python/nondist/peps/pep-0326.txt,v retrieving revision 1.4 retrieving revision 1.5 diff -C2 -d -r1.4 -r1.5 *** pep-0326.txt 1 Feb 2004 19:40:14 -0000 1.4 --- pep-0326.txt 24 Feb 2004 02:47:53 -0000 1.5 *************** *** 5,14 **** Author: Josiah Carlson <jcarlson@uci.edu>, Terry Reedy <tjreedy@udel.edu> ! Status: Draft Type: Standards Track Content-Type: text/x-rst Created: 20-Dec-2003 Python-Version: 2.4 ! Post-History: 20-Dec-2003, 03-Jan-2004, 05-Jan-2004, 07-Jan-2004 --- 5,26 ---- Author: Josiah Carlson <jcarlson@uci.edu>, Terry Reedy <tjreedy@udel.edu> ! Status: Rejected Type: Standards Track Content-Type: text/x-rst 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 ! ! Results ! ======= ! ! This PEP has been rejected by the BDFL [12]_. As per the ! pseudo-sunset clause [13]_, PEP 326 is being updated one last time ! with the latest suggestions, code modifications, etc., and includes a ! link to a module [14]_ that implements the behavior described in the ! PEP. Users who desire the behavior listed in this PEP are encouraged ! to use the module for the reasons listed in ! `Independent Implementations?`_. *************** *** 68,72 **** OverflowError: long int too large to convert to float ! - These same drawbacks exist when numbers are small. Introducing ``Max`` and ``Min`` that work as described above does not --- 80,84 ---- OverflowError: long int too large to convert to float ! - These same drawbacks exist when numbers are negative. Introducing ``Max`` and ``Min`` that work as described above does not *************** *** 88,142 **** --------------------- ! Take for example, finding the minimum in a sequence:: ! ! def findmin_Num(seq): ! BIG = 0 ! cur = BIG ! for obj in seq: ! if cur == BIG: ! cur = obj ! BIG = max(cur, BIG) + 1 ! else: ! cur = min(cur, obj) ! return cur ! ! :: ! ! def findmin_None(seq): ! cur = None ! for obj in seq: ! if obj < cur or (cur is None): ! cur = obj ! if cur is None: ! return cur ! return cur ! ! :: ! ! def findmin_Max(seq): ! cur = Max ! for obj in seq: ! cur = min(obj, cur) ! return cur ! Please note that there are an arbitrarily large number of ways to find ! the minimum (or maximum) of a sequence, these seek to show a simple ! example where using ``Max`` makes the algorithm easier to understand ! and results in the simplification of code. ! Guido brought up the idea of just negating everything and comparing ! [2]_. Certainly this does work when using numbers, but it does not ! remove the special case (actually adds one) and results in the code ! being less readable. :: ! #we have Max available ! a = min(a, b) ! #we don't have Max available ! if a is not None: ! if b is None: ! a = b ! else: ! a = -max(-a, -b) As another example, in Dijkstra's shortest path algorithm on a graph --- 100,120 ---- --------------------- ! When testing various kinds of servers, it is sometimes necessary to ! only serve a certain number of clients before exiting, which results ! in code like the following:: ! count = 5 ! def counts(stop): ! i = 0 ! while i < stop: ! yield i ! i += 1 ! for client_number in counts(count): ! handle_one_client() ! When using ``Max`` as the value assigned to count, our testing server ! becomes a production server with minimal effort. As another example, in Dijkstra's shortest path algorithm on a graph *************** *** 157,217 **** pointers to find the reverse of the path to be taken. ! To be complete, below are two versions of the algorithm, one using a ! table (a bit more understandable) and one using a heap (much faster):: def DijkstraSP_table(graph, S, T): ! #runs in O(N^2) time using a table ! #find the shortest path ! table = {} for node in graph.iterkeys(): #(visited, distance, node, parent) ! table[node] = (0, Max, node, None) ! table[S] = (0, 0, S, None) ! cur = min(table.values()) ! while (not cur[0]) and cur[1] < Max: (visited, distance, node, parent) = cur ! table[node] = (1, distance, node, parent) ! for cdist, child in graph[node]: ! ndist = distance+cdist ! if not table[child][0] and ndist < table[child][1]: ! table[child] = (0, ndist, child, node) ! cur = min(table.values()) ! #backtrace through results if not table[T][0]: return None ! cur = T ! path = [T] ! while table[cur][3] is not None: ! path.append(table[cur][3]) ! cur = path[-1] ! path.reverse() ! return path ! ! :: ! ! def DijkstraSP_heap(graph, S, T): ! #runs in O(NlgN) time using a minheap ! #find the shortest path ! import heapq ! Q = [(Max, i, None) for i in graph.iterkeys()] ! heapq.heappush(Q, (0, S, None)) ! V = {} ! while Q[0][0] < Max and T not in V: ! dist, node, parent = heapq.heappop(Q) ! if node in V: ! continue ! V[node] = (dist, parent) ! for next, dest in graph[node]: ! heapq.heappush(Q, (next+dist, dest, node)) ! #backtrace through results ! if T not in V: ! return None ! cur = T ! path = [T] ! while V[cur][1] is not None: ! path.append(V[cur][1]) ! cur = path[-1] ! path.reverse() ! return path Readers should note that replacing ``Max`` in the above code with an --- 135,170 ---- pointers to find the reverse of the path to be taken. ! .. _DijkstraSP_table: ! ! Below is an example of Dijkstra's shortest path algorithm on a graph ! with weighted edges using a table (a faster version that uses a heap ! is available, but this version is offered due to its similarity to the ! description above, the heap version is available via older versions of ! this document through CVS [10]_). :: 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 #|_ Readers should note that replacing ``Max`` in the above code with an *************** *** 223,226 **** --- 176,252 ---- potential problems with numeric overflows. + .. _DijkstraSP_table_node: + + Gustavo Niemeyer [9]_ points out that using a more Pythonic data + structure than tuples, to store information about node distances, + increases readability. Two equivalent node structures (one using + ``None``, the other using ``Max``) and their use in a suitably + modified Dijkstra's shortest path algorithm is given below. :: + + 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 #|_ + + In the above, passing in either NoneNode or MaxNode would be + sufficient to use either ``None`` or ``Max`` for the node distance + 'infinity'. Note the additional special case required for ``None`` + being used as a sentinel in NoneNode in the __cmp__ method. + + This example highlights the special case handling where ``None`` is + used as a sentinel value for maximum values "in the wild", even though + None itself compares smaller than any other object in the standard + distribution. + + As an aside, it is not clear to to the author that using Nodes as a + replacement for tuples has increased readability significantly, if at + all. + A ``Min`` Example *************** *** 242,272 **** and ``B``. ! Such an algorithm is a 7 line modification to the DijkstraSP_table ! algorithm given above:: ! ! #only showing the changed to lines with the proper indentation ! table[node] = (0, Min, node, None) ! table[S] = (0, 1, S, None) ! cur = max(table.values()) ! while (not cur[0]) and cur[1] > Min: ! ndist = distance*cdist ! if not table[child][0] and ndist > table[child][1]: ! cur = max(table.values()) ! ! Or a 6 line modification to the DijkstraSP_heap algorithm given above ! (if we assume that ``maxheapq`` exists and does what it is supposed ! to):: ! #only showing the changed to lines with the proper indentation ! import maxheapq ! Q = [(Min, i, None) for i in graph.iterkeys()] ! maxheapq.heappush(Q, (1, S, None)) ! while Q[0][0] > Min and T not in V: ! dist, node, parent = maxheapq.heappop(Q) ! maxheapq.heappush(Q, (next*dist, dest, node)) ! Note that there is an equivalent way of translating the graph to ! produce something that can be passed unchanged into the original ! Dijkstra shortest path algorithm. --- 268,304 ---- and ``B``. ! Such an algorithm is a 7 line modification to the `DijkstraSP_table`_ ! algorithm given above (modified lines prefixed with `*`):: ! 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 #|_ ! Note that there is a way of translating the graph to so that it can be ! passed unchanged into the original `DijkstraSP_table`_ algorithm. ! There also exists a handful of easy methods for constructing Node ! objects that would work with `DijkstraSP_table_node`_. Such ! translations are left as an exercise to the reader. *************** *** 334,337 **** --- 366,380 ---- ``Max``. + It has been pointed out [9]_ that the reference implementation given + below would be incompatible with independent implementations of + ``Max``/``Min``. The point of this PEP is for the introduction of + "The One True Implementation" of "The One True Maximum" and "The One + True Minimum". User-based implementations of ``Max`` and ``Min`` + objects would thusly be discouraged, and use of "The One True + Implementation" would obviously be encouraged. Ambiguous behavior + resulting from mixing users' implementations of ``Max`` and ``Min`` + with "The One True Implementation" should be easy to discover through + variable and/or source code introspection. + Reference Implementation *************** *** 378,390 **** =========== ! Current options for the naming and namespace for ``Min``/``Max``, in ! no particular order: ! 1. Give the built-in ``max`` and ``min`` appropriate ``__cmp__`` ! methods to allow them to double as ``Min``/``Max``. ! 2. Attach them to attributes of the ``cmp()`` built-in. ! 3. Attach them to attributes of an appropriate type object. ! 4. Make them an appropriate module object. ! 5. Create two new built-ins with appropriate names. --- 421,432 ---- =========== ! As the PEP was rejected, all open issues are now closed and ! inconsequential. The module will use the names ``UniversalMaximum`` ! and ``UniversalMinimum`` due to the fact that it would be very ! difficult to mistake what each does. For those who require a shorter ! name, renaming the singletons during import is suggested:: ! from extremes import UniversalMaximum as uMax, ! UniversalMinimum as uMin *************** *** 417,420 **** --- 459,484 ---- (http://www.livejournal.com/users/chouyu_31/138195.html?thread=274643#t274643) + .. [9] [Python-Dev] Re: PEP 326 now online, Niemeyer, Gustavo + (http://mail.python.org/pipermail/python-dev/2004-January/042261.html); + [Python-Dev] Re: PEP 326 now online, Carlson, Josiah + (http://mail.python.org/pipermail/python-dev/2004-January/042272.html) + + .. [10] PEP-0326 CVS, Carlson, Josiah + (http://cvs.sourceforge.net/viewcvs.py/python/python/nondist/peps/pep-0326.tx...) + + .. [11] [Python-Dev] PEP 326 (quick location possibility), Carlson, Josiah + (http://mail.python.org/pipermail/python-dev/2004-January/042275.html) + + .. [12] [Python-Dev] PEP 326 (quick location possibility), van Rossum, Guido + (http://mail.python.org/pipermail/python-dev/2004-January/042306.html) + + .. [13] [Python-Dev] PEP 326 (quick location possibility), Carlson, Josiah + (http://mail.python.org/pipermail/python-dev/2004-January/042300.html) + + .. [14] Recommended standard implementation of PEP 326, extremes.py, + Carlson, Josiah + (http://www.ics.uci.edu/~jcarlson/pep326/extremes.py) + + Changes ======= *************** *** 426,431 **** - Changed markup to reStructuredText. - - Concept gets a possible name and location. [5]_ - - Clarified Abstract_, Motivation_, `Reference Implementation`_ and `Open Issues`_ based on the simultaneous concepts of ``Max`` and --- 490,493 ---- *************** *** 437,442 **** - Added an example of use for ``Min`` to Motivation_. - - Added some `Open Issues`_ and clarified some others. - - Added an example and `Other Examples`_ subheading. --- 499,502 ---- *************** *** 447,450 **** --- 507,517 ---- of this PEP. + - Replaced an example from `Max Examples`_, changed an example in + `A Min Example`_. + + - Added some `References`_. + + - BDFL rejects [12]_ PEP 326 + Copyright