Stack - A stack implementation for Python

mxStack - A stack implementation for Python

Version 0.2.2

Introduction

Though stacks can be emulated with Python lists, this type provides a simple interface to the data structure, both in Python and in C. Because of the function call overhead calling the methods from Python is only a tad faster than a corresponding list emulation. Called from within an C extension shows a more significant performance increase. The included stackbench.py gives an impression of how the different methods relate w/r to speed:

projects/mxStack> stackbench.py 1000 100 100
list:  1.25
tuples: 0.71
Stack: 0.82
Stack (pop all at once): 0.53
UserStack: 1.89

Note that the tuple version has a few disadvantages when used for big stacks: for one it uses lots of memory (20 bytes per entry slot; Stack uses 20 bytes + 4 bytes per entry slot) and deallocation can become a problem -- this is done using recursion with one level per stack element. For small stacks it still is unbeatable, though (it has no function call overhead). BTW, the UserStack uses the same technique: the figures shown mainly result from Python method call overhead.

Interface

Stack Constructors

There are two ways to construct a Stack from scratch:

Stack([initial_size]): Returns a new empty Stack instance allocating at least the given number of slots for stack elements. If the parameter is not given a reasonable default is chosen.
StackFromSequence(seq): Constructs a Stack instance from the given sequence. The instance is filled with all the elements found in the sequence by pushing the items from index 0 to len(seq)-1 in that order, i.e. popping all elements from the Stack results in a reversed sequence.

Instance Methods

A Stack instance has the following methods:

push(x): Pushes the object x onto the stack.
pop(): Pops the top element off of the stack.
pop_many(n): Pops the top n elements and returns them in form of a tuple. The order is top to bottom, i.e. s.pop_many(2) == (s.pop(),s.pop())
as_tuple(): Returns the stack's content as tuple, without modifying it.
as_list(): Returns the stack's content as list, without modifying it.

Note that no method for testing emtpyness is provided. Use len() for that or simply test for trueness, e.g. while s: print s.pop() will loop as long as there are elements left on the Stack s. This is much faster than going through the method calling process -- even when the method being called is written in C.

Examples of Use

Well, there's not much to show:

from mxStack import *
s = Stack()
for i in range(1000):
s.push(i)
while s:
print s.pop()
# which could also be done as:
s = StackFromSequence(range(1000))
while s:
print s.pop()
# or a little different
s = StackFromSequence(range(1000))
print s.as_tuple()
print s.as_list()

Supported Data Types in the C-API

Please have look at the file mxStack.h for details. Basically all of the above Python interfaces are also available in the C API.

To access the module, do the following (note the similarities with Python's way of accessing functions from a module):

#include "mxStack.h"

...
    PyObject *v;

    /* Import the mxStack module */
    if (mxStack_ImportModuleAndAPI())
	goto onError;

    /* Access functions from the exported C API through mxStack */
    v = mxStack.Stack(0);
    if (!v)
	goto onError;

    /* Type checking */
    if (mxStack_Check(v))
        printf("Works.\n");

    Py_DECREF(v);
...

Package Structure

[Stack]
	mxStack

Entries enclosed in brackets are packages (i.e. they are directories that include a __init__.py file). Ones without brackets are just simple subdirectories that are not accessible via import. These are used for compiling the C extension modules which will get installed in the same place where all your other site specific extensions live (e.g. /usr/local/lib/python-x.xx/site-packages).

The package Stack imports all symbols from the extension mxStack, so import Stack; s = Stack.Stack() gives you a Stack instance in s.

Installation

First, download the archive, unzip it to a directory on your Python path and then follow these steps (assuming you have already installed Python):

David Ascher has kindly provided a pre-compiled Windows version of the extension (version 0.2), so if you're running WinXX, you can skip the following and start using the package right away.

run make -f Makefile.pre.in boot in the mxStack directory
run make
get Python 1.5 or above running, and execute test.py; it should not report any errors.
if you like it, run make install.
give me feedback :-)

Though the module has been tested, there may still be some bugs left. Please post any bug reports, questions etc. directly to me.

What I'd like to hear from you...

Can you get the module to compile/work on other Unix platforms other than Linux ?

Copyright & Disclaimer

Permission to use, copy, modify, and distribute this software and its documentation for any purpose and without fee or royalty is hereby granted, provided that the above copyright notice appear in all copies and that both the copyright notice and this permission notice appear in supporting documentation or portions thereof, including modifications, that you make.

THE AUTHOR MARC-ANDRE LEMBURG DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE !

History & Future

Changes from 0.1 to 0.2:

Version 0.2.2: Fixed a bug that caused stack.push() to dump core when called without argument. Also added some minor speedups.
Version 0.2.1: added method pop_many().
Converted the module into a package called 'Stack'. This imports the C extension mxStack.