Update of /cvsroot/python/python/nondist/peps In directory sc8prcvs1.sourceforge.net:/tmp/cvsserv26739 Modified Files: pep0326.txt Log Message: update from Josiah Carlson Index: pep0326.txt =================================================================== RCS file: /cvsroot/python/python/nondist/peps/pep0326.txt,v retrieving revision 1.4 retrieving revision 1.5 diff C2 d r1.4 r1.5 *** pep0326.txt 1 Feb 2004 19:40:14 0000 1.4  pep0326.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 ContentType: text/xrst Created: 20Dec2003 PythonVersion: 2.4 ! PostHistory: 20Dec2003, 03Jan2004, 05Jan2004, 07Jan2004  5,26  Author: Josiah Carlson <jcarlson@uci.edu>, Terry Reedy <tjreedy@udel.edu> ! Status: Rejected Type: Standards Track ContentType: text/xrst Created: 20Dec2003 PythonVersion: 2.4 ! PostHistory: 20Dec2003, 03Jan2004, 05Jan2004, 07Jan2004, ! 21Feb2004 ! ! Results ! ======= ! ! This PEP has been rejected by the BDFL [12]_. As per the ! pseudosunset 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". Userbased 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 builtin ``max`` and ``min`` appropriate ``__cmp__`` ! methods to allow them to double as ``Min``/``Max``. ! 2. Attach them to attributes of the ``cmp()`` builtin. ! 3. Attach them to attributes of an appropriate type object. ! 4. Make them an appropriate module object. ! 5. Create two new builtins 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] [PythonDev] Re: PEP 326 now online, Niemeyer, Gustavo + (http://mail.python.org/pipermail/pythondev/2004January/042261.html); + [PythonDev] Re: PEP 326 now online, Carlson, Josiah + (http://mail.python.org/pipermail/pythondev/2004January/042272.html) + + .. [10] PEP0326 CVS, Carlson, Josiah + (http://cvs.sourceforge.net/viewcvs.py/python/python/nondist/peps/pep0326.tx...) + + .. [11] [PythonDev] PEP 326 (quick location possibility), Carlson, Josiah + (http://mail.python.org/pipermail/pythondev/2004January/042275.html) + + .. [12] [PythonDev] PEP 326 (quick location possibility), van Rossum, Guido + (http://mail.python.org/pipermail/pythondev/2004January/042306.html) + + .. [13] [PythonDev] PEP 326 (quick location possibility), Carlson, Josiah + (http://mail.python.org/pipermail/pythondev/2004January/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
participants (1)

goodger＠users.sourceforge.net