buffersort

Provide a variety of sorting algorithms that operate in-place on types that implement the Python buffer protocol.


Keywords
cython, memoryview, sorting, fused-types
License
Other
Install
pip install buffersort==0.0.5

Documentation

Build Status

buffersort

Provide a variety of sorting algorithms that operate in-place on types that implement the Python buffer protocol.

install

buffersort requires Cython >= 0.22 and NumPy >= 1.10.1. buffersort builds are tested with travis-ci for Python 2.7.11 and Python 3.5.0 on 64-bit Ubuntu 14.04.

basic

Clone the repo, navigate to the top-level directory where you can find setup.py and use

python setup.py install

If you'd like to preserve a copy of the files affected by installation so that you can manually uninstall later, add the --record option:

python setup.py install --record install-files.txt

pip

buffersort is available at PyPI. The following command also works when you have activated a conda environment, should you prefer to install from PyPI under conda.

pip install buffersort

conda

conda install -c http://conda.anaconda.org/spearsem buffersort

To install from source with conda navigate to the project directory and use

conda build info

This will download the code and prepare a build within the internal package directories maintained by conda. It will not affect your local copy of the source code.

After conda build finishes, the built packages must be installed to be available.

conda install --use-local buffersort

conda will refer to the local build it maintains after the execution of conda build for the installation.

usage

Assuming you have installed the package, everything can be accessed by importing buffersort:

>>> import buffersort
>>> from array import array
>>> a = array('l', [-1, -50, 10, -3, 27, 14])
>>> a
array('l', [-1, -50, 10, -3, 27, 14])

>>> buffersort.heap_sort(a)
>>> a
array('l', [-50, -3, -1, 10, 14, 27])

testing

buffersort provides unit tests as a built package so that you may execute them more conveniently. The test subpackage, buffersort.test, may be imported directly:

>>> import buffersort.test as test

Alternatively, the buffersort.test.test_buffersort module, which contains the unit tests, is provided as part of the top-level buffersort package import, and you may run the full suite of unit tests as follows.

>>> import buffersort
>>> buffersort.test_buffersort.run_tests()

If tests fail due to type signature errors or unsupported type errors, feel free to create an issue with your platform information. The type support is controlled by the Ord fused type found in buffersort.pxd. Cython states that support for fused types is experimental, so some bugs may be unavoidable due to Cython fused type support. Other bugs may be fixable by extending the library to include additional types in the Ord fused type definition.

motivation

buffersort makes use of Cython fused types and typed memoryviews to enable writing concise functions in simple Cython syntax from which many overloaded versions are automatically generated and correctly dispatched in the compiled code.

buffersort is meant to be an educational library for the task of writing Python modules that include functions which are both performant and polymorphic. Traditionally, with Python's dynamic type model, there is often a trade-off between writing a generic function accepting of many different Python objects and writing specialized functions that are tightly compiled and optimized to handle a narrow type. But with Cython fused types, it is possible to make functions more generic without sacrificing any of their static type specialization.

The use of Ord as a Cython fused type is not accidental. This motif is inspired by the Ord type class in the Haskell programming language. Part of the goal of buffersort is to demonstrate how, at least for a limited set of situations, Cython fused types enable designs that are similarly easy to work with and expressive as Haskell type classes.

For example, we can see from a small section of the Cython source code how a C-level function is defined with static type information, yet corresponds to autogenerated functions that cover all necessary static type signatures from all constituent types of Ord:

cdef void _swap(Ord[:] buf, int i, int j):
    """
    Swap elements i and j in buffer buf.
    """
    cdef Ord temp = buf[i]
    buf[i] = buf[j]
    buf[j] = temp

In this case, _swap is a simple helper function to swap the elements residing at positions i and j of an array. The array argument buf has a static type of Ord[:] -- a typed memoryview of a one-dimensional array of Ord values.

In the body of the function, we can work with the array without caring whether it is an array of int or an array of double -- the overloaded versions specific to these types will be autogenerated since those base types are part of the Ord fused type. We can even create a temporary value, temp with type Ord that will be correctly resolved for each distinct compiled overload of the function.