Fast python library for jenks natural breaks
The history and intent of the Jenks natural breaks algorithm is well covered by
There are even a few python implementations:
However, it has been noted that the python implementations are tediously slow. There are two obvious reasons for this...
All the data is stored in python lists rather than optimized data structures. The fact that the variables are named "matrices" is perhaps some sort of practical joke given how bad lists are for matrix/array like data structures. Numpy arrays are your friend and I can't imagine doing any numeric computation in python without them.
There is a lot of looping. Like exponential-time looping. The algorithm makes this somewhat inevitable. Python sucks at iterating over simple math, exploding the runtime very quickly. Cython, through it's variable typing, allows us to write the algorithm in python-like syntax, compile it to a shared library that can be imported as a python module and run at near-C speeds.
Here's the benchmark against the jenks2.py implementation:
In : from jenks2 import jenks In : %timeit jenks(data, 5) 1 loops, best of 3: 8.16 s per loop In : from jenks import jenks In : %timeit jenks(data, 5) 10 loops, best of 3: 69.2 ms per loop
Yep that's 118X faster for just a little bit of static typing and using arrays instead of lists. It even makes the logic easier to read (for those of us who work with matrices/arrays often).
The only cost is that you need Cython and a C compiler to get it working.
sudo apt-get install build-essential cython python-numpy pip install -e "git+https://github.com/perrygeo/jenks.git#egg=jenks"
And then test it
In : import json In : from jenks import jenks In : # data should be 1-dimensional array, python list or iterable In : data = json.load(open('test.json')) In : print jenks(data, 5) [0.002810962, 2.0935481, 4.2054954, 6.1781483, 8.0917587, 9.997983]