[Python-checkins] python/nondist/peps pep-0326.txt,1.4,1.5
goodger at users.sourceforge.net
goodger at users.sourceforge.net
Mon Feb 23 21:47:56 EST 2004
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 at uci.edu>,
Terry Reedy <tjreedy at 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 at uci.edu>,
Terry Reedy <tjreedy at 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.txt)
+
+ .. [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
More information about the Python-checkins
mailing list