%load_ext watermark
%watermark -d -m -v -p cython
06/07/2014 CPython 3.4.1 IPython 2.1.0 cython 0.20.2 compiler : GCC 4.2.1 (Apple Inc. build 5577) system : Darwin release : 13.2.0 machine : x86_64 processor : i386 CPU cores : 2 interpreter: 64bit
More information about the watermark
magic command extension.
First, we will write a simple implementation of the bubble sort algorithm in regular (C)Python
def python_bubblesort(a_list):
""" Bubblesort in Python for list objects. """
length = len(a_list)
swapped = 1
for i in range(0, length):
if swapped:
swapped = 0
for ele in range(0, length-i-1):
if a_list[ele] > a_list[ele + 1]:
temp = a_list[ele + 1]
a_list[ele + 1] = a_list[ele]
a_list[ele] = temp
swapped = 1
return a_list
python_bubblesort([6,3,1,5,6])
[1, 3, 5, 6, 6]
Next, we will speed things up a little bit via Cython's C-extensions for Python. Cython is basically a hybrid between C and Python and can be pictured as compiled Python code with type declarations.
Since we are working in an IPython notebook here, we can make use of the very convenient *IPython magic*: It will take care of the conversion to C code, the compilation, and eventually the loading of the function.
%load_ext cythonmagic
First, we will take the initial Python code as is and use Cython for the compilation. Cython is capable of auto-guessing types, however, we can make our code way more efficient by adding static types.
%%cython
def cython_bubblesort_untyped(a_list):
""" Bubblesort in Python for list objects. """
length = len(a_list)
swapped = 1
for i in range(0, length):
if swapped:
swapped = 0
for ele in range(0, length-i-1):
if a_list[ele] > a_list[ele + 1]:
temp = a_list[ele + 1]
a_list[ele + 1] = a_list[ele]
a_list[ele] = temp
swapped = 1
return a_list
%%cython
import numpy as np
cimport numpy as np
cimport cython
@cython.boundscheck(False)
@cython.wraparound(False)
cpdef cython_bubblesort_typed(np.ndarray[long, ndim=1] inp_ary):
""" The Cython implementation of Bubblesort with NumPy memoryview."""
cdef unsigned long length, i, swapped, ele, temp
cdef long[:] np_ary = inp_ary
length = np_ary.shape[0]
swapped = 1
for i in xrange(0, length):
if swapped:
swapped = 0
for ele in xrange(0, length-i-1):
if np_ary[ele] > np_ary[ele + 1]:
temp = np_ary[ele + 1]
np_ary[ele + 1] = np_ary[ele]
np_ary[ele] = temp
swapped = 1
return inp_ary
Below, we will do a quick speed comparison of our 3 implementations of the bubble sort algorithm by sorting a list (or numpy array) of 1000 random digits. Here, we have to make copies of the lists/numpy arrays, since our bubble sort implementation is sorting in place.
import random
import numpy as np
import copy
list_a = [random.randint(0,1000) for num in range(1000)]
list_b = copy.deepcopy(list_a)
ary_a = np.asarray(list_a)
ary_b = copy.deepcopy(ary_a)
ary_c = copy.deepcopy(ary_a)
import timeit
times = []
times.append(min(timeit.Timer('python_bubblesort(list_a)',
'from __main__ import python_bubblesort, list_a').repeat(repeat=3, number=1000)))
times.append(min(timeit.Timer('python_bubblesort(ary_a)',
'from __main__ import python_bubblesort, ary_a').repeat(repeat=3, number=1000)))
times.append(min(timeit.Timer('cython_bubblesort_untyped(list_b)',
'from __main__ import cython_bubblesort_untyped, list_b').repeat(repeat=3, number=1000)))
times.append(min(timeit.Timer('cython_bubblesort_untyped(ary_b)',
'from __main__ import cython_bubblesort_untyped, ary_b').repeat(repeat=3, number=1000)))
times.append(min(timeit.Timer('cython_bubblesort_typed(ary_c)',
'from __main__ import cython_bubblesort_typed, ary_c').repeat(repeat=3, number=1000)))
%matplotlib inline
from matplotlib import pyplot as plt
import numpy as np
bar_labels = ('(C)Python on list',
'(C)Python on numpy array',
'untyped Cython on list',
'untyped Cython on numpy array',
'typed Cython with memoryview on numpy array')
fig = plt.figure(figsize=(10,8))
# plot bars
y_pos = np.arange(len(times))
plt.yticks(y_pos, bar_labels, fontsize=14)
bars = plt.barh(y_pos, times,
align='center', alpha=0.4, color='g')
# annotation and labels
for b,d in zip(bars, times):
plt.text(max(times)+0.1, b.get_y() + b.get_height()/2.5,
'{:.2} ms'.format(d),
ha='center', va='bottom', fontsize=12)
t = plt.title('Bubblesort on 1000 random integers', fontsize=18)
plt.ylim([-1,len(times)+0.5])
plt.vlines(min(times), -1, len(times)+0.5, linestyles='dashed')
plt.grid()
plt.show()
IPython's notebook is really great for explanatory analysis and documentation, but what if we want to compile our Python code via Cython without letting IPython's magic doing all the work?
These are the steps you would need.
%%file cython_bubblesort_nomagic.pyx
cimport numpy as np
cimport cython
@cython.boundscheck(False)
@cython.wraparound(False)
cpdef cython_bubblesort_nomagic(np.ndarray[long, ndim=1] inp_ary):
""" The Cython implementation of Bubblesort with NumPy memoryview."""
cdef unsigned long length, i, swapped, ele, temp
cdef long[:] np_ary = inp_ary
length = np_ary.shape[0]
swapped = 1
for i in xrange(0, length):
if swapped:
swapped = 0
for ele in xrange(0, length-i-1):
if np_ary[ele] > np_ary[ele + 1]:
temp = np_ary[ele + 1]
np_ary[ele + 1] = np_ary[ele]
np_ary[ele] = temp
swapped = 1
return inp_ary
Writing cython_bubblesort_nomagic.pyx
%%file setup.py
import numpy as np
from distutils.core import setup
from distutils.extension import Extension
from Cython.Distutils import build_ext
setup(
cmdclass = {'build_ext': build_ext},
ext_modules = [
Extension("cython_bubblesort_nomagic",
["cython_bubblesort_nomagic.pyx"],
include_dirs=[np.get_include()])
]
)
Writing setup.py
!python3 setup.py build_ext --inplace
running build_ext cythoning cython_bubblesort_nomagic.pyx to cython_bubblesort_nomagic.c building 'cython_bubblesort_nomagic' extension /usr/bin/clang -fno-strict-aliasing -Werror=declaration-after-statement -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -I/Users/sebastian/miniconda3/envs/py34/include -arch x86_64 -I/Users/sebastian/miniconda3/envs/py34/lib/python3.4/site-packages/numpy/core/include -I/Users/sebastian/miniconda3/envs/py34/include/python3.4m -c cython_bubblesort_nomagic.c -o build/temp.macosx-10.5-x86_64-3.4/cython_bubblesort_nomagic.o In file included from cython_bubblesort_nomagic.c:352: In file included from /Users/sebastian/miniconda3/envs/py34/lib/python3.4/site-packages/numpy/core/include/numpy/arrayobject.h:4: In file included from /Users/sebastian/miniconda3/envs/py34/lib/python3.4/site-packages/numpy/core/include/numpy/ndarrayobject.h:17: In file included from /Users/sebastian/miniconda3/envs/py34/lib/python3.4/site-packages/numpy/core/include/numpy/ndarraytypes.h:1761: /Users/sebastian/miniconda3/envs/py34/lib/python3.4/site-packages/numpy/core/include/numpy/npy_1_7_deprecated_api.h:15:2: warning: "Using deprecated NumPy API, disable it by " "#defining NPY_NO_DEPRECATED_API NPY_1_7_API_VERSION" [-W#warnings] #warning "Using deprecated NumPy API, disable it by " \ ^ In file included from cython_bubblesort_nomagic.c:352: In file included from /Users/sebastian/miniconda3/envs/py34/lib/python3.4/site-packages/numpy/core/include/numpy/arrayobject.h:4: In file included from /Users/sebastian/miniconda3/envs/py34/lib/python3.4/site-packages/numpy/core/include/numpy/ndarrayobject.h:26: /Users/sebastian/miniconda3/envs/py34/lib/python3.4/site-packages/numpy/core/include/numpy/__multiarray_api.h:1629:1: warning: unused function '_import_array' [-Wunused-function] _import_array(void) ^ In file included from cython_bubblesort_nomagic.c:353: In file included from /Users/sebastian/miniconda3/envs/py34/lib/python3.4/site-packages/numpy/core/include/numpy/ufuncobject.h:327: /Users/sebastian/miniconda3/envs/py34/lib/python3.4/site-packages/numpy/core/include/numpy/__ufunc_api.h:241:1: warning: unused function '_import_umath' [-Wunused-function] _import_umath(void) ^ cython_bubblesort_nomagic.c:18981:32: warning: unused function '__Pyx_PyUnicode_FromString' [-Wunused-function] static CYTHON_INLINE PyObject* __Pyx_PyUnicode_FromString(const char* c_str) { ^ cython_bubblesort_nomagic.c:19132:33: warning: unused function '__Pyx_PyInt_FromSize_t' [-Wunused-function] static CYTHON_INLINE PyObject * __Pyx_PyInt_FromSize_t(size_t ival) { ^ cython_bubblesort_nomagic.c:16538:1: warning: unused function '__pyx_add_acquisition_count_locked' [-Wunused-function] __pyx_add_acquisition_count_locked(__pyx_atomic_int *acquisition_count, ^ cython_bubblesort_nomagic.c:16548:1: warning: unused function '__pyx_sub_acquisition_count_locked' [-Wunused-function] __pyx_sub_acquisition_count_locked(__pyx_atomic_int *acquisition_count, ^ cython_bubblesort_nomagic.c:17017:26: warning: unused function '__Pyx_PyBytes_Equals' [-Wunused-function] static CYTHON_INLINE int __Pyx_PyBytes_Equals(PyObject* s1, PyObject* s2... ^ cython_bubblesort_nomagic.c:17298:32: warning: unused function '__Pyx_GetItemInt_List_Fast' [-Wunused-function] static CYTHON_INLINE PyObject *__Pyx_GetItemInt_List_Fast(PyObject *o, P... ^ cython_bubblesort_nomagic.c:17312:32: warning: unused function '__Pyx_GetItemInt_Tuple_Fast' [-Wunused-function] static CYTHON_INLINE PyObject *__Pyx_GetItemInt_Tuple_Fast(PyObject *o, ... ^ cython_bubblesort_nomagic.c:17491:38: warning: unused function '__Pyx_PyInt_From_unsigned_long' [-Wunused-function] static CYTHON_INLINE PyObject* __Pyx_PyInt_From_unsigned_long(unsi... ^ cython_bubblesort_nomagic.c:17538:36: warning: function '__Pyx_PyInt_As_unsigned_long' is not needed and will not be emitted [-Wunneeded-internal-declaration] static CYTHON_INLINE unsigned long __Pyx_PyInt_As_unsigned_long(PyObject *x) { ^ cython_bubblesort_nomagic.c:17644:48: warning: unused function '__pyx_t_float_complex_from_parts' [-Wunused-function] static CYTHON_INLINE __pyx_t_float_complex __pyx_t_float_complex_fro... ^ cython_bubblesort_nomagic.c:17654:30: warning: unused function '__Pyx_c_eqf' [-Wunused-function] static CYTHON_INLINE int __Pyx_c_eqf(__pyx_t_float_complex a, __pyx_... ^ cython_bubblesort_nomagic.c:17657:48: warning: unused function '__Pyx_c_sumf' [-Wunused-function] static CYTHON_INLINE __pyx_t_float_complex __Pyx_c_sumf(__pyx_t_floa... ^ cython_bubblesort_nomagic.c:17663:48: warning: unused function '__Pyx_c_difff' [-Wunused-function] static CYTHON_INLINE __pyx_t_float_complex __Pyx_c_difff(__pyx_t_flo... ^ cython_bubblesort_nomagic.c:17675:48: warning: unused function '__Pyx_c_quotf' [-Wunused-function] static CYTHON_INLINE __pyx_t_float_complex __Pyx_c_quotf(__pyx_t_flo... ^ cython_bubblesort_nomagic.c:17682:48: warning: unused function '__Pyx_c_negf' [-Wunused-function] static CYTHON_INLINE __pyx_t_float_complex __Pyx_c_negf(__pyx_t_floa... ^ cython_bubblesort_nomagic.c:17688:30: warning: unused function '__Pyx_c_is_zerof' [-Wunused-function] static CYTHON_INLINE int __Pyx_c_is_zerof(__pyx_t_float_complex a) { ^ cython_bubblesort_nomagic.c:17691:48: warning: unused function '__Pyx_c_conjf' [-Wunused-function] static CYTHON_INLINE __pyx_t_float_complex __Pyx_c_conjf(__pyx_t_flo... ^ cython_bubblesort_nomagic.c:17705:52: warning: unused function '__Pyx_c_powf' [-Wunused-function] static CYTHON_INLINE __pyx_t_float_complex __Pyx_c_powf(__pyx_t_... ^ cython_bubblesort_nomagic.c:17764:49: warning: unused function '__pyx_t_double_complex_from_parts' [-Wunused-function] static CYTHON_INLINE __pyx_t_double_complex __pyx_t_double_complex_f... ^ cython_bubblesort_nomagic.c:17774:30: warning: unused function '__Pyx_c_eq' [-Wunused-function] static CYTHON_INLINE int __Pyx_c_eq(__pyx_t_double_complex a, __pyx_... ^ cython_bubblesort_nomagic.c:17777:49: warning: unused function '__Pyx_c_sum' [-Wunused-function] static CYTHON_INLINE __pyx_t_double_complex __Pyx_c_sum(__pyx_t_doub... ^ cython_bubblesort_nomagic.c:17783:49: warning: unused function '__Pyx_c_diff' [-Wunused-function] static CYTHON_INLINE __pyx_t_double_complex __Pyx_c_diff(__pyx_t_dou... ^ cython_bubblesort_nomagic.c:17795:49: warning: unused function '__Pyx_c_quot' [-Wunused-function] static CYTHON_INLINE __pyx_t_double_complex __Pyx_c_quot(__pyx_t_dou... ^ cython_bubblesort_nomagic.c:17802:49: warning: unused function '__Pyx_c_neg' [-Wunused-function] static CYTHON_INLINE __pyx_t_double_complex __Pyx_c_neg(__pyx_t_doub... ^ cython_bubblesort_nomagic.c:17808:30: warning: unused function '__Pyx_c_is_zero' [-Wunused-function] static CYTHON_INLINE int __Pyx_c_is_zero(__pyx_t_double_complex a) { ^ cython_bubblesort_nomagic.c:17811:49: warning: unused function '__Pyx_c_conj' [-Wunused-function] static CYTHON_INLINE __pyx_t_double_complex __Pyx_c_conj(__pyx_t_dou... ^ cython_bubblesort_nomagic.c:17825:53: warning: unused function '__Pyx_c_pow' [-Wunused-function] static CYTHON_INLINE __pyx_t_double_complex __Pyx_c_pow(__pyx_t_... ^ cython_bubblesort_nomagic.c:18247:27: warning: function '__Pyx_PyInt_As_char' is not needed and will not be emitted [-Wunneeded-internal-declaration] static CYTHON_INLINE char __Pyx_PyInt_As_char(PyObject *x) { ^ cython_bubblesort_nomagic.c:18347:27: warning: function '__Pyx_PyInt_As_long' is not needed and will not be emitted [-Wunneeded-internal-declaration] static CYTHON_INLINE long __Pyx_PyInt_As_long(PyObject *x) { ^ cython_bubblesort_nomagic.c:2955:32: warning: unused function '__pyx_f_5numpy_PyArray_MultiIterNew1' [-Wunused-function] static CYTHON_INLINE PyObject *__pyx_f_5numpy_PyArray_MultiIterNew1(PyOb... ^ cython_bubblesort_nomagic.c:3005:32: warning: unused function '__pyx_f_5numpy_PyArray_MultiIterNew2' [-Wunused-function] static CYTHON_INLINE PyObject *__pyx_f_5numpy_PyArray_MultiIterNew2(PyOb... ^ cython_bubblesort_nomagic.c:3055:32: warning: unused function '__pyx_f_5numpy_PyArray_MultiIterNew3' [-Wunused-function] static CYTHON_INLINE PyObject *__pyx_f_5numpy_PyArray_MultiIterNew3(PyOb... ^ cython_bubblesort_nomagic.c:3105:32: warning: unused function '__pyx_f_5numpy_PyArray_MultiIterNew4' [-Wunused-function] static CYTHON_INLINE PyObject *__pyx_f_5numpy_PyArray_MultiIterNew4(PyOb... ^ cython_bubblesort_nomagic.c:3155:32: warning: unused function '__pyx_f_5numpy_PyArray_MultiIterNew5' [-Wunused-function] static CYTHON_INLINE PyObject *__pyx_f_5numpy_PyArray_MultiIterNew5(PyOb... ^ cython_bubblesort_nomagic.c:3909:27: warning: unused function '__pyx_f_5numpy_set_array_base' [-Wunused-function] static CYTHON_INLINE void __pyx_f_5numpy_set_array_base(PyArrayObject *_... ^ cython_bubblesort_nomagic.c:3997:32: warning: unused function '__pyx_f_5numpy_get_array_base' [-Wunused-function] static CYTHON_INLINE PyObject *__pyx_f_5numpy_get_array_base(PyArrayObje... ^ 39 warnings generated. /usr/bin/clang -bundle -undefined dynamic_lookup -L/Users/sebastian/miniconda3/envs/py34/lib -arch x86_64 build/temp.macosx-10.5-x86_64-3.4/cython_bubblesort_nomagic.o -L/Users/sebastian/miniconda3/envs/py34/lib -o /Users/sebastian/github/python_reference/tutorials/cython_bubblesort_nomagic.so
import cython_bubblesort_nomagic
cython_bubblesort_nomagic.cython_bubblesort_nomagic(np.array([4,6,2,1,6]))
array([1, 2, 4, 6, 6])
from cython_bubblesort_nomagic import cython_bubblesort_nomagic
list_a = [random.randint(0,100000) for num in range(100000)]
ary_a = np.asarray(list_a)
ary_b = np.asarray(list_a)
times = []
times.append(min(timeit.Timer('cython_bubblesort_typed(ary_a)',
'from __main__ import cython_bubblesort_typed, ary_a').repeat(repeat=3, number=1000)))
times.append(min(timeit.Timer('cython_bubblesort_nomagic(ary_b)',
'from __main__ import cython_bubblesort_nomagic, ary_b').repeat(repeat=3, number=1000)))
from matplotlib import pyplot as plt
import numpy as np
bar_labels = ('Cython with IPython magic',
'Cython without IPython magic')
fig = plt.figure(figsize=(10,8))
# plot bars
y_pos = np.arange(len(times))
plt.yticks(y_pos, bar_labels, fontsize=14)
bars = plt.barh(y_pos, times,
align='center', alpha=0.4, color='g')
# annotation and labels
for b,d in zip(bars, times):
plt.text(max(times)+0.02, b.get_y() + b.get_height()/2.5,
'{:.2} ms'.format(d),
ha='center', va='bottom', fontsize=12)
t = plt.title('Bubblesort on 100,000 random integers', fontsize=18)
plt.ylim([-1,len(times)+0.5])
plt.vlines(min(times), -1, len(times)+0.5, linestyles='dashed')
plt.grid()
plt.show()