Summer reading list

[Raymond Hettinger]

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).

[Joe Cheng]

Re: Summer reading list

> Accordingly, I suggest the following works of literature:[color=blue]
>
> * 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.[/color]

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(hea p, 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(it em)

Otherwise the user could easily break the heap by doing something dumb to
the list...

[Chad Netzer]

Re: Summer reading list

On Tue, 2003-08-12 at 08:56, Joe Cheng wrote:
[color=blue]
> 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(hea p, 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(it em)
>
> Otherwise the user could easily break the heap by doing something dumb to
> the list...[/color]

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 "practicali ty 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.heaprepla ce( 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

[Andrew Dalke]

Re: Summer reading list

Chad Netzer[color=blue]
> Quick heap class (any error corrections are appreciated):
> ---------------------------------------------------------[/color]
[color=blue]
> def __init__( self, heap=[] ):[/color]

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
dalke@dalkescie ntific.com

[Andrew Dalke]

Re: Summer reading list

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

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
dalke@dalkescie ntific.com

[John J. Lee]

Re: Summer reading list

"Andrew Dalke" <adalke@mindspr ing.com> writes:
[color=blue]
> Joe Cheng:[color=green]
> > It might just be my Java background creeping in (I'm a Python newbie), but,
> > wouldn't it be better if this was OO?[/color]
>
> Here's perhaps the definitive statement on the topic, from Tim Peters:
> http://aspn.activestate.com/ASPN/Mai...on-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.[/color]

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

[Fredrik Lundh]

Re: Summer reading list

Andrew Dalke wrote:
[color=blue]
> 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.[/color]

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

</F>