Author: Magnus Lie Hetland
Pub Date: 2014
Size: 10 Mb
Python Algorithms, Second Edition explains the Python approach to algorithm analysis and design. Written by Magnus Lie Hetland, author of Beginning Python, this book is sharply focused on classical algorithms, but it also gives a solid understanding of fundamental algorithmic problem-solving techniques.
The book deals with some of the most important and challenging areas of programming and computer science in a highly readable manner. It covers both algorithmic theory and programming practice, demonstrating how theory is reflected in real Python programs. Well-known algorithms and data structures that are built into the Python language are explained, and the user is shown how to implement and evaluate others.
Pedal to the Metal: Accelerating Python
PyPy, Pyston, Parakeet, Psyco, and Unladen Swallow. One of the least intrusive approaches to speeding up your code is to use a just-in-time (JIT) compiler. In the olden days, you could use Psyco together with your Python installation. After installing Psyco, you would simply import the psycomodule and call psyco.full()to get a potentially quite noticeable speedup. Psyco would compile parts of your Python program into machine code while your program was running. Because it could watch what happens to your program at runtime, it could make optimizations that a static compiler could not. For example, a Python list can contain arbitrary values. If, however, Psyco noticed that a given list of yours only ever seems to contain integers, it could assume that this would be the case also in the future and compile that part of the code as if your list were an array of integers. Sadly, like several of the Python acceleration solutions, Psyco is, to quote its web site, “unmaintained and dead.” Its legacy lives on in PyPy, though.
PyPy is a more ambitious project: a reimplementation of Python in Python. This does not, of course, give a speedup directly, but the idea behind the platform is to put a lot of infrastructure in place for analyzing, optimizing, and translating code. Based on this framework, it is then possible to do JIT compilation (techniques used in Psyco are being ported to PyPy), or even translation to some high-performance language such as C. The core subset of Python used in implementing PyPy is called RPython (for restricted Python), and there are already tools for statically compiling this language into efficient machine code.
Unladen Swallow is also a JIT compiler for Python, in a way. More precisely, it’s a version of the Python interpreter that uses the so-called Low Level Virtual Machine (LLVM). The goal of the project has been a speedup factor of 5 compared to the standard interpreter. This target has not yet been reached, though, and the activity of the
project seems to have stopped.
Pyston is a similar, more recent LLVM-based JIT compiler for Python being developed by Dropbox. At the time of writing, Pyston is still a young project, supporting only a subset of the language, and there is as yet no support for Python 3. However, it already beats the standard Python implementation in many cases and is under active
development. Parakeet is also a rather young project, which, to quote the web page, “uses type inference, data parallel array operators, and a lot of black magic to make your code run faster.”
Other tools. Clearly there are plenty of other tools out there, which may be of more use to you than these, depending on your needs. For example, if you want to reduce memory use rather than time, a JIT is not for you—JITs generally need a lot of memory. Instead, you might want to check out Micro Python, which is designed to have a minimal memory footprint and to be suited for using Python on microcontrollers and in embedded devices. And, who knows, maybe you don’t even require the use of Python. Perhaps you’re working in a Python environment, and you want a high-level language, but you want all of your code to be really fast. Though it might be Pythonic heresy, I suggest looking at Julia. While it’s a different language, its syntax should be familiar enough to any Python programmer. It also has support for calling Python libraries, which means that the Julia team is cooperating with Python projects such as IPython, and it has even been the subject of a SciPy conference lecture already.