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.