Summer reading list

Discussion in 'Python' started by Raymond Hettinger, Aug 12, 2003.

  1. Found in a pamphlet at a pre-school:
    ---------------------------------------
    Reading improves vocabulary
    Reading raises cultural literacy through shared knowledge
    Reading develops writing skills
    Reading opens the mind to new ways of understanding
    Reading is fun


    Accordingly, I suggest the following works of literature:

    * heapq.py (255 lines)
    * sets.py (536 lines)
    * textwrap.py (355 lines)
    * csv.py (427 lines)

    These make enjoyable reading, cover interesting topics/algorithms,
    demonstrate superb modern python technique, and showcase
    effective use of Python's newer features.

    Learn from the masters:
    Pinard, O'Connor, Peters, Wilson, Martelli, van Rossum,
    Ward, Montanaro, Altis, Drake, and others

    have-you-read-any-good-code-lately-ly yours,


    Raymond Hettinger


    P.S. The unittests for sets.py are *not* as enjoyable reading; however,
    they are a highly instructive example of Greg's sophisticated use of the
    testing framework and his unusally thorough approach to deciding
    what and how to test. Lib/test/test_sets.py (692 lines)
    Learning from Greg's example enabled me to use similar ideas in
    developing Lib/test/test_random.py (298 lines).
    Raymond Hettinger, Aug 12, 2003
    #1
    1. Advertising

  2. Raymond Hettinger

    Joe Cheng Guest

    > Accordingly, I suggest the following works of literature:
    >
    > * heapq.py (255 lines)
    > * sets.py (536 lines)
    > * textwrap.py (355 lines)
    > * csv.py (427 lines)
    >
    > These make enjoyable reading, cover interesting topics/algorithms,
    > demonstrate superb modern python technique, and showcase
    > effective use of Python's newer features.


    I read heapq.py from here:
    http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/python/python/dist/src/Lib/he
    apq.py

    Quoting from the comments:

    """Usage:

    heap = [] # creates an empty heap
    heappush(heap, item) # pushes a new item on the heap
    item = heappop(heap) # pops the smallest item from the heap
    item = heap[0] # smallest item on the heap without popping it
    heapify(x) # transforms list into a heap, in-place, in linear time
    item = heapreplace(heap, item) # pops and returns smallest item, and adds
    # new item; the heap size is unchanged"""

    It might just be my Java background creeping in (I'm a Python newbie), but,
    wouldn't it be better if this was OO?

    heap = Heap()
    heap.push(item)
    item = heap.pop()
    item = heap[0]
    heapified = Heap(x)
    item = heap.replace(item)

    Otherwise the user could easily break the heap by doing something dumb to
    the list...
    Joe Cheng, Aug 12, 2003
    #2
    1. Advertising

  3. Raymond Hettinger

    Chad Netzer Guest

    On Tue, 2003-08-12 at 08:56, Joe Cheng wrote:

    > Quoting from the comments:
    >
    > """Usage:
    >
    > heap = [] # creates an empty heap
    > heappush(heap, item) # pushes a new item on the heap
    > item = heappop(heap) # pops the smallest item from the heap
    > item = heap[0] # smallest item on the heap without popping it
    > heapify(x) # transforms list into a heap, in-place, in linear time
    > item = heapreplace(heap, item) # pops and returns smallest item, and adds
    > # new item; the heap size is unchanged"""
    >
    > It might just be my Java background creeping in (I'm a Python newbie), but,
    > wouldn't it be better if this was OO?
    >
    > heap = Heap()
    > heap.push(item)
    > item = heap.pop()
    > item = heap[0]
    > heapified = Heap(x)
    > item = heap.replace(item)
    >
    > Otherwise the user could easily break the heap by doing something dumb to
    > the list...


    True. But the flexibility of using the builtin is also nice. For
    example, you can add a bunch of objects to the list, then heapify once,
    rather than having to call heap.push() a bunch of times (which may be
    slower, because you need to maintain the heap property after you push
    each new item.)

    I think the idea is that, if you want a real Heap class, you can build
    one very easily (see below). And if you don't need a heap class, you
    can gain some benefits from this approach because it is exposing and
    operating on lists directly.

    This probably comes under "practicality beats purity". (See 'The Zen of
    Python', or type "import this" into your Python interpreter)

    Quick heap class (any error corrections are appreciated):
    ---------------------------------------------------------

    import heapq

    class Heap:
    def __init__( self, heap=[] ):
    heapq.heapify( heap )
    self._heap = heap

    def __getitem__( self, i ):
    return self._heap[ i ]

    def push( self, item ):
    return heapq.heappush( self._heap, item )

    def pop( self ):
    return heapq.heappop( self._heap )

    def replace( self, item ):
    return heapq.heapreplace( self._heap, item )

    if __name__ == '__main__':
    # Tests
    heap = Heap()
    heap.push(3)
    heap.push(2)
    heap.push(1)
    item = heap.pop()

    assert item == 1

    item = heap[0]
    assert item == 2

    item = heap.replace(4)
    assert item == 2
    assert heap[0] == 3
    assert heap[1] == 4



    --
    Chad Netzer
    Chad Netzer, Aug 12, 2003
    #3
  4. Raymond Hettinger

    Andrew Dalke Guest

    Chad Netzer
    > Quick heap class (any error corrections are appreciated):
    > ---------------------------------------------------------


    > def __init__( self, heap=[] ):


    make that
    def __init__(self, heap = None):
    if heap is None:
    heap = []

    Otherwise, all Heaps created with default args will share the
    same data.

    Andrew
    Andrew Dalke, Aug 13, 2003
    #4
  5. Raymond Hettinger

    Andrew Dalke Guest

    Joe Cheng:
    > It might just be my Java background creeping in (I'm a Python newbie),

    but,
    > wouldn't it be better if this was OO?


    Here's perhaps the definitive statement on the topic, from Tim Peters:
    http://aspn.activestate.com/ASPN/Mail/Message/python-dev/1620162

    Summary: heapq is a concrete interface, not an abstract one. It doesn't
    try to encompass the different ways to do heaps. It's like bisect in that
    it works on an existing data type.

    Andrew
    Andrew Dalke, Aug 13, 2003
    #5
  6. Raymond Hettinger

    John J. Lee Guest

    "Andrew Dalke" <> writes:

    > Joe Cheng:
    > > It might just be my Java background creeping in (I'm a Python newbie), but,
    > > wouldn't it be better if this was OO?

    >
    > Here's perhaps the definitive statement on the topic, from Tim Peters:
    > http://aspn.activestate.com/ASPN/Mail/Message/python-dev/1620162
    >
    > Summary: heapq is a concrete interface, not an abstract one. It doesn't
    > try to encompass the different ways to do heaps. It's like bisect in that
    > it works on an existing data type.


    That URL comes up blank for me. Found this, though:

    http://www.python.org/dev/summary/2003-04-16_2003-04-30.html

    | The idea of turning the heapq module into a class came up, and later
    | led to the idea of having a more proper FIFO (First In, First Out)
    | data structure. Both ideas were shot down. The reason for this was
    | that the stdlib does not need to try to grow every single possible
    | data structure in programming. Guido's design philosophy is to have a
    | few very powerful data structures that other ones can be built off
    | of. This is why the bisect and heapq modules just work on standard
    | lists instead of defining a new class. Queue is an exception, but it
    | is designed to mediate messages between threads instead of being a
    | general implementation of a queue.


    John
    John J. Lee, Aug 13, 2003
    #6
  7. Andrew Dalke wrote:

    > Summary: heapq is a concrete interface, not an abstract one. It doesn't
    > try to encompass the different ways to do heaps. It's like bisect in that
    > it works on an existing data type.


    more importantly, it works on *any* existing data type, as long as the
    type behaves like a mutable sequence.

    </F>
    Fredrik Lundh, Aug 13, 2003
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Volkan Arslan
    Replies:
    0
    Views:
    327
    Volkan Arslan
    Mar 2, 2004
  2. Joe Cheng

    RE: Summer reading list

    Joe Cheng, Aug 12, 2003, in forum: Python
    Replies:
    3
    Views:
    331
    Michele Simionato
    Aug 16, 2003
  3. David Ascher
    Replies:
    0
    Views:
    236
    David Ascher
    Jun 2, 2005
  4. Neal Norwitz

    Summer of Code mailing list

    Neal Norwitz, Apr 28, 2006, in forum: Python
    Replies:
    0
    Views:
    275
    Neal Norwitz
    Apr 28, 2006
  5. Michael
    Replies:
    0
    Views:
    491
    Michael
    May 6, 2006
Loading...

Share This Page