Data Structures Versus Python Built-ins

Now that I've shown you all these complicated algorithms, I need to also tell you that at least in some cases, they may not be an optimal approach. Built-in types like lists and dictionaries are often a simpler and more efficient way to represent data. For instance:

Binary trees

These may be useful in many applications, but Python dictionaries already provide a highly optimized, C-coded, search table tool. Indexing a dictionary by key is likely to be faster than searching a Python-coded tree structure:

>>> x = {}
>>> for i in [3,1,9,2,7]: x[i] = None  # insert
>>> for i in range(10): print (i, x.has_key(i)), # lookup
(0, 0) (1, 1) (2, 1) (3, 1) (4, 0) (5, 0) (6, 0) (7, 1) (8, 0) (9, 1)

Because dictionaries are built in to the language, they are always available, and will usually be faster than Python-based data structure implementations.

Graph algorithms

These serve many purposes, but a purely Python-coded implementation of a very large graph might be less efficient than you want in some applications. Graph programs tend to require peak performance; using dictionaries instead of class instances to represent graphs may boost performance some, but using linked-in compiled extensions may as well.

Sorting algorithms

These are an important part of many programs too, but Python's built-in list sort method is so fast that you would be hard pressed to beat it in Python in most scenarios. In fact, it's generally better to convert sequences to lists first just so you can use the built-in:

temp = list(sequence)
temp.sort( )
...use items in temp...

For custom sorts, simply pass in a comparison function of your own:

>>> L = [{'n':3}, {'n':20}, {'n':0}, {'n':9}] 
>>> L.sort( lambda x, y: cmp(x['n'], y['n']) ) 
>>> L  
[{'n': 0}, {'n': 3}, {'n': 9}, {'n': 20}]

Reversal algorithms

These are generally superfluous by the same token -- because Python lists provide a fast reverse method, you may be better off converting a non-list to a list first, just so that you can run the built-in list method.

Don't misunderstand: 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, add tools not directly supported by Python today, and the tuple-tree stack implementation was actually faster than one based upon built-in lists for common usage patterns. Permutations are something you need to add on your own too.

Moreover, class encapsulations make it possible to change and extend object internals without impacting the rest of your system. They also support reuse much better than built-in types -- types are not classes today, and cannot be specialized directly without wrapper class logic.

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 languages such as C or C++. Before you code that new datatype, be sure to ask yourself if a built-in type or call might be more in line with the Python way of thinking.

Introducing Python

Part I: System Interfaces

System Tools

Parallel System Tools

Larger System Examples I

Larger System Examples II

Part II: GUI Programming

Graphical User Interfaces

A Tkinter Tour, Part 1

A Tkinter Tour, Part 2

Larger GUI Examples

Part III: Internet Scripting

Network Scripting

Client-Side Scripting

Server-Side Scripting

Larger Web Site Examples I

Larger Web Site Examples II

Advanced Internet Topics

Part IV: Assorted Topics

Databases and Persistence

Data Structures

Text and Language

Part V: Integration

Extending Python

Embedding Python

VI: The End

Conclusion Python and the Development Cycle



Programming Python
Python Programming for the Absolute Beginner, 3rd Edition
ISBN: 1435455002
EAN: 2147483647
Year: 2000
Pages: 245

Flylib.com © 2008-2020.
If you may any questions please contact us: flylib@qtcs.net