Data Structures in Python

Question

All the books I've read on data structures so far seem to use C/C++, and make heavy use of the "manual" pointer control that they offer. Since Python hides that sort of memory management and garbage collection from the user is it even possible to implement efficient data structures in this language, and is there any reason to do so instead of using the built-ins?

Solution 1

Python gives you some powerful, highly optimized data structures, both as built-ins and as part of a few modules in the standard library (lists and dicts, of course, but also tuples, sets, arrays in module array, and some other containers in module collections).

Combinations of these data structures (and maybe some of the functions from helper modules such as heapq and bisect) are generally sufficient to implement most richer structures that may be needed in real-life programming; however, that's not invariably the case.

When you need something more than the rich library provides, consider the fact that an object's attributes (and items in collections) are essentially "pointers" to other objects (without pointer arithmetic), i.e., "reseatable references", in Python just like in Java. In Python, you normally use a None value in an attribute or item to represent what NULL would mean in C++ or null would mean in Java.

So, for example, you could implement binary trees via, e.g.:

class Node(object):

  __slots__ = 'payload', 'left', 'right'

  def __init__(self, payload=None, left=None, right=None):
    self.payload = payload
    self.left = left
    self.right = right

plus methods or functions for traversal and similar operations (the __slots__ class attribute is optional -- mostly a memory optimization, to avoid each Node instance carrying its own __dict__, which would be substantially larger than the three needed attributes/references).

Other examples of data structures that may best be represented by dedicated Python classes, rather than by direct composition of other existing Python structures, include tries (see e.g. here) and graphs (see e.g. here).

Solution 2

For some simple data structures (eg. a stack), you can just use the builtin list to get your job done. With more complex structures (eg. a bloom filter), you'll have to implement them yourself using the primitives the language supports.

You should use the builtins if they serve your purpose really since they're debugged and optimised by a horde of people for a long time. Doing it from scratch by yourself will probably produce an inferior data structure.

If however, you need something that's not available as a primitive or if the primitive doesn't perform well enough, you'll have to implement your own type.

The details like pointer management etc. are just implementation talk and don't really limit the capabilities of the language itself.

Solution 3

C/C++ data structure books are only attempting to teach you the underlying principles behind the various structures - they are generally not advising you to actually go out and re-invent the wheel by building your own library of stacks and lists.

Whether you're using Python, C++, C#, Java, whatever, you should always look to the built in data structures first. They will generally be implemented using the same system primitives you would have to use doing it yourself, but with the advantage of having been tried and tested.

Only when the provided data structures do not allow you to accomplish what you need, and there isn't an alternative and reliable library available to you, should you be looking at building something from scratch (or extending what's provided).

Solution 4

How Python handles objects at a low level isn't too strange anyway. This document should disambiguate it a tad; it's basically all the pointer logic you're already familiar with.

Solution 5

With Python you have access to a vast assortment of library modules written and debugged by other people. Odds are very good that somewhere out there, there is a module that does at least part of what you want, and odds are even good that it might be implemented in C for performance.

For example, if you need to do matrix math, you can use NumPy, which was written in C and Fortran.

Python is slow enough that you won't be happy if you try to write some sort of really compute-intensive code (example, a Fast Fourier Transform) in native Python. On the other hand, you can get a C-coded Fourier Transform as part of SciPy, and just use it.

I have never had a situation where I wanted to solve a problem in Python and said "darn, I just can't express the data structure I need."

If you are a pioneer, and you are doing something in Python for which there just isn't any library module out there, then you can try writing it in pure Python. If it is fast enough, you are done. If it is too slow, you can profile it, figure out where the slow parts are, and rewrite them in C using the Python C API. I have never needed to do this yet.

View more solutions

Comments

[Noufal Ibrahim]

I'm not familiar with the implementation of the C++ vector but the Python list type is implemented as an array (bytes.com/topic/python/answers/101848-list-implementation) rather than a linked list. Isn't that what a vector basically is?

[Ed_WFerreira]

Yes, a Python is implemented as an array (same as a C++ vector). What I'm saying is you couldn't implement your own list in Python, except on top of the existing one.

[Greg Rogers]

Well, the python list type is really more like Java's ArrayList (ie. an array of pointers to Object).

[Ed_WFerreira]

True, but that's because Python and Java have reference semantics (ignoring Java's handling of primitives).