Programming Python, 3rd Edition

Data Structures Versus Python Built-Ins

Now that I’ve shown you all of 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 such as 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 into 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 rather than 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 ...