Programming Python (184 page)

Reversal of collections can be coded either recursively or
iteratively in Python, and as functions or class methods.
Example 18-23
is a first attempt
at two simple reversal functions.

def reverse(list):               # recursive
if list == []:
return []
else:
return reverse(list[1:]) + list[:1]
def ireverse(list):              # iterative
res = []
for x in list: res = [x] + res
return res

Both reversal functions work correctly on lists. But if we try
reversing nonlist sequences (strings, tuples, and so on), the
ireverse
function always returns a list for
the result regardless of the type of sequence passed:

>>>
ireverse("spam")
['m', 'a', 'p', 's']

Much worse, the recursive
reverse
version won’t work at all for
nonlists—it gets stuck in an infinite loop. The reason is subtle: when
reverse
reaches the empty string
(
""
), it’s not equal to the empty
list (
[]
), so the
else
clause is selected. But slicing an empty
sequence returns another empty sequence (indexes are scaled): the
else
clause recurs again with an
empty sequence, without raising an exception. The net effect is that
this function gets stuck in a loop, calling itself over and over again
until Python runs out of memory.

The versions in
Example 18-24
fix both problems by
using generic sequence handling techniques much like that of the prior
section’s permutation utilities:

def reverse(list):
if not list:                               # empty? (not always [])
return list                            # the same sequence type
else:
return reverse(list[1:]) + list[:1]    # add front item on the end
def ireverse(list):
res = list[:0]                             # empty, of same type
for i in range(len(list)):
res = list[i:i+1] + res                # add each item to front
return res

The combination of the changes allows the new functions to work on
any sequence, and return a new sequence of the same type as the sequence
passed in. If we pass in a string, we get a new string as the result. In
fact, they reverse any sequence object that responds to slicing,
concatenation, and
len
—even instances
of Python classes and C types. In other words, they can reverse any
object that has sequence interface protocols. Here they are working on
lists, strings, and tuples:

>>>
from rev2 import *
>>>
reverse([1, 2, 3]), ireverse([1, 2, 3])
([3, 2, 1], [3, 2, 1])
>>>
reverse("spam"), ireverse("spam")
('maps', 'maps')
>>>
reverse((1.2, 2.3, 3.4)), ireverse((1.2, 2.3, 3.4))
((3.4, 2.3, 1.2), (3.4, 2.3, 1.2))

Another staple of many systems is sorting: ordering items in a
collection according to some constraint. The script in
Example 18-25
defines a simple
sort routine in Python, which orders a list of objects on a field.
Because Python indexing is generic, the field can be an index or a
key—this function can sort lists of either sequences or mappings.

def sort(list, field):
res = []                                     # always returns a list
for x in list:
i = 0
for y in res:
if x[field] <= y[field]: break       # list node goes here?
i += 1
res[i:i] = [x]                           # insert in result slot
return res
if __name__ == '__main__':
table = [ {'name':'john', 'age':25}, {'name':'doe', 'age':32} ]
print(sort(table, 'name'))
print(sort(table, 'age'))
table = [ ('john', 25), ('doe', 32) ]
print(sort(table, 0))
print(sort(table, 1))

Here is this module’s self-test code in action; the first tests
sort dictionaries, and the last sort tuples:

C:\...\PP4E\Dstruct\Classics>
python sort1.py
[{'age': 32, 'name': 'doe'}, {'age': 25, 'name': 'john'}]
[{'age': 25, 'name': 'john'}, {'age': 32, 'name': 'doe'}]
[('doe', 32), ('john', 25)]
[('john', 25), ('doe', 32)]

def sort(seq, func=(lambda x,y: x <= y)):             # default: ascending
res = seq[:0]                                     # return seq's type
for j in range(len(seq)):
i = 0
for y in res:
if func(seq[j], y): break
i += 1
res = res[:i] + seq[j:j+1] + res[i:]          # seq can be immutable
return res
if __name__ == '__main__':
table = ({'name':'doe'}, {'name':'john'})
print(sort(list(table),  (lambda x, y: x['name'] > y['name'])))
print(sort(tuple(table), (lambda x, y: x['name'] <= y['name'])))
print(sort('axbyzc'))

C:\...\PP4E\Dstruct\Classics>
python sort2.py
[{'name': 'john'}, {'name': 'doe'}]
({'name': 'doe'}, {'name': 'john'})
abcxyz

But now that I’ve shown you these reversing and sorting
algorithms, I need to also tell you that they may not be an optimal
approach, especially in these specific cases.
Although
these examples serve an
educational role, built-in lists and functions generally accomplish what
we just did the hard way:

In fact, this has been a recurring theme of this chapter on
purpose, to underscore a key point in Python work: although there are
plenty of exceptions, you’re generally better off not reinventing the
data structure wheel unless you have to. Built-in functionality will
often prove a better choice in the end.

Make no mistake: sometimes you really do need objects that add
functionality to built-in types or do something more custom. The set
classes we met, for instance, can add custom tools not directly
supported by Python today, binary search trees may support some
algorithms better than dictionaries and sets can, and the tuple-tree
stack implementation was actually faster than one based on built-in
lists for common usage patterns. Moreover, graphs and permutations are
something you must code on your own.

As we’ve also seen, class encapsulations make it possible to
change and extend object internals without impacting the rest of your
system. Although subclassing built-in types can address much of the same
goals, the end result is still a custom data structure.

Yet because Python comes with a set of built-in, flexible, and
optimized datatypes, data structure implementations are often not as
important in Python as they are in lesser-equipped and lower-level
programming languages. Before you code that new datatype, be sure to ask
yourself whether a built-in type or call might be more in line with the
Python way of thinking.

For more on extended data structures for use in Python, see also
the relatively new
collections
module
in its standard library. As mentioned in the preceding chapter, this
module implements named tuples, ordered dictionaries, and more. It’s
described in Python’s library manual, but its source code, like much in
the standard library, can serve as a source of supplemental examples as
well.