<jupyter_start><jupyter_text>Demo of the increased efficiency of vectorized formsClosest 2D point location:http://nbviewer.ipython.org/github/rossant/ipython-minibook/blob/master/chapter3/301-vector-computations.ipynb Bubble sort bubble sort more [<NAME>](http://sebastianraschka.com)  last updated: 05/28/2014- [Open in IPython nbviewer](http://nbviewer.ipython.org/github/rasbt/One-Python-benchmark-per-day/blob/master/ipython_nbs/day4_2_cython_numba_parakeet.ipynb?create=1)  - [Link to this IPython notebook on Github](https://github.com/rasbt/One-Python-benchmark-per-day/blob/master/ipython_nbs/day4_2_cython_numba_parakeet.ipynb)  - [Link to the GitHub Repository One-Python-benchmark-per-day](https://github.com/rasbt/One-Python-benchmark-per-day) I would be happy to hear your comments and suggestions.  Please feel free to drop me a note via[twitter](https://twitter.com/rasbt), [email](mailto:<EMAIL>), or [google+](https://plus.google.com/118404394130788869227).  Day 4.2 - One Python Benchmark per Day  Comparing (C)Python compilers - Cython vs. Numba vs. Parakeet on Bubblesort **[-> skip to the results](Results)** I made some significant changes to the previous [Day 4 benchmark](http://nbviewer.ipython.org/github/rasbt/One-Python-benchmark-per-day/blob/master/ipython_nbs/day4_python_cython_numba.ipynb?create=1), thus I decided to make it a separate article:  - added the [parakeet](http://www.parakeetpython.com) compiler  - improved the Bubblesort algorithm to avoid comparing already-sorted pairs  - improved the Cython implementation (avoiding redundant conversion from memory view to array object)  - focussed on only the optimized ("best") Cython and Numba implementations of Bubblesort  - used Python 2.7.6 instead of Python 3.4.0 (because of parakeet)     Quick note about Bubblesort I don't want to get into the details about sorting algorithms here, but there is a great report  ["Sorting in the Presence of Branch Prediction and Caches - Fast Sorting on Modern Computers"](https://www.cs.tcd.ie/publications/tech-reports/reports.05/TCD-CS-2005-57.pdf) written by <NAME> and <NAME>, where they describe and analyze elementary sorting algorithms in very nice detail (see chapter 4).   And for a quick reference, [this website](http://www.sorting-algorithms.com/bubble-sort) has a nice animation of this algorithm. A long story short: The "worst-case" complexity of the Bubblesort algorithm (i.e., "Big-O")   $\Rightarrow \pmb O(n^2)$   Bubble sort implemented in (C)Python<jupyter_code>def python_bubblesort(a_list):
    """ Bubblesort in Python for list objects. """
    length = len(a_list)
    swapped = 1
    for i in xrange(0, length):
        if swapped: 
            swapped = 0
            for ele in xrange(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
def python_bubblesort_ary(np_ary):
    """ Bubblesort in Python for NumPy arrays. """
    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 np_ary
a = np.array[1,2,3,4,5])<jupyter_output><empty_output><jupyter_text>Bubble sort implemented in Cython Maybe we can speed things up a little bit via [Cython's C-extensions for Python](http://cython.org). 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.  Note that the static type declarations that we add via `cdef` are note required for Cython to work, but it will speed things up tremendously.<jupyter_code>%load_ext cythonmagic
%%cython
import numpy as np
cimport numpy as np
cimport cython
@cython.boundscheck(False) 
@cython.wraparound(False)
cpdef cython_bubblesort(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<jupyter_output><empty_output><jupyter_text>Bubble sort implemented in Numba Numba is using the [LLVM compiler infrastructure](http://llvm.org) for compiling Python code to machine code. Its strength is to work with NumPy arrays to speed-up the code. If you want to read more about Numba, please see refer to the original [website and documentation](http://numba.pydata.org/numba-doc/0.13/index.html).<jupyter_code>from numba import jit as numba_jit
@numba_jit
def numba_bubblesort(np_ary):
    """ The NumPy implementation of Bubblesort on NumPy arrays."""
    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 np_ary<jupyter_output><empty_output><jupyter_text>Bubble sort implemented in  parakeet Similar to Numba,  [parakeet](http://www.parakeetpython.com) is a Python compiler that optimizes the runtime of numerical computations based on the NumPy data types, such as NumPy arrays.The usage is also similar to Numba where we just have to put the `jit` decorator on top of the function we want to optimize.<jupyter_code>from parakeet import jit as para_jit
@para_jit
def parakeet_bubblesort(np_ary):
    """ The parakeet implementation of Bubblesort on NumPy arrays."""
    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 np_ary<jupyter_output><empty_output><jupyter_text>Verifying that all implementations work correctly<jupyter_code>import random
import copy
import numpy as np
random.seed(4354353)
print "my number is", random.randint(1,1000)
#l = np.asarray([random.randint(1,1000) for num in xrange(1, 1000)])
#print l
l_sorted = np.sort(l)
for f in [python_bubblesort, python_bubblesort_ary, cython_bubblesort, 
          numba_bubblesort]:
    assert(l_sorted.all() == f(copy.copy(l)).all())
print('Bubblesort works correctly')<jupyter_output>my number is 337
Bubblesort works correctly<jupyter_text>Timing<jupyter_code>import timeit
import copy
import numpy as np

funcs = ['python_bubblesort',
         'python_bubblesort_ary',
         'cython_bubblesort',
         'numba_bubblesort'
         ]

orders_n = [10**n for n in range(1, 6)]
timings = {f:[] for f in funcs}

for n in orders_n:
    l = [np.random.randint(n) for num in range(n)]
    for f in funcs:
        l_copy = copy.deepcopy(l)
        if f != 'python_bubblesort':
            l_copy = np.asarray(l_copy)
        timings[f].append(min(timeit.Timer('%s(l_copy)' %f, 
                      'from __main__ import %s, l_copy' %f)
                              .repeat(repeat=3, number=10)))<jupyter_output><empty_output><jupyter_text>Setting up the plots<jupyter_code>import platform
import multiprocessing
from cython import __version__ as cython__version__
from llvm import __version__ as llvm__version__
from numba import __version__ as numba__version__
from parakeet import __version__ as parakeet__version__

def print_sysinfo():
    
    print '\nPython version  :', platform.python_version()
    print 'compiler        :', platform.python_compiler()
    print 'Cython version  :', cython__version__
    print 'NumPy version   :', np.__version__
    print 'Numba version   :', numba__version__
    print 'llvm version    :', llvm__version__
    print 'parakeet version:', parakeet__version__
    
    print '\nsystem     :', platform.system()
    print 'release    :', platform.release()
    print 'machine    :', platform.machine()
    print 'processor  :', platform.processor()
    print 'CPU count  :', multiprocessing.cpu_count()
    print 'interpreter:', platform.architecture()[0]
    print '\n\n'
%matplotlib inline
import matplotlib.pyplot as plt

def plot(timings, title, ranked_labels, labels, orders_n):
    plt.rcParams.update({'font.size': 12})

    fig = plt.figure(figsize=(11,10))
    for lb in ranked_labels:
        plt.plot(orders_n, timings[lb], alpha=0.5, label=labels[lb], 
                 marker='o', lw=3)
    plt.xlabel('sample size n (items in the list)')
    plt.ylabel('time per computation in milliseconds')
    plt.xlim([min(orders_n) / 10, max(orders_n)* 10])
    plt.legend(loc=2)
    plt.grid()
    plt.xscale('log')
    plt.yscale('log')
    plt.title(title)
    plt.show()
import prettytable

def summary_table(ranked_labels):
    fit_table = prettytable.PrettyTable(['n=%s' %orders_n[-1], 
                                         'bubblesort function' ,
                                         'time in millisec.',
                                         'rel. performance gain'])
    fit_table.align['bubblesort function'] = 'l'
    for entry in ranked_labels:
        fit_table.add_row(['', labels[entry[1]], round(entry[0]*100, 3), 
                           round(ranked_labels[0][0]/entry[0], 2)])
        # times 100 for converting from seconds to milliseconds: (time*1000 / 10-loops)
    print(fit_table)<jupyter_output><empty_output><jupyter_text>Results<jupyter_code>title = 'Performance of Bubblesort in Python, Cython, parakeet, and Numba'

labels = {'python_bubblesort':'(C)Python Bubblesort - Python lists', 
          'python_bubblesort_ary':'(C)Python Bubblesort - NumPy arrays',  
          'cython_bubblesort': 'Cython Bubblesort - NumPy arrays',
          'numba_bubblesort': 'Numba Bubblesort - NumPy arrays',
          'parakeet_bubblesort': 'parakeet Bubblesort - NumPy arrays'
          }

ranked_by_time = sorted([(time[1][-1],time[0]) for time in timings.items()], reverse=True)

print_sysinfo()
plot(timings, title, [l for t,l in ranked_by_time], labels, orders_n)
summary_table(ranked_by_time)<jupyter_output>Python version  : 2.7.6
compiler        : GCC 4.0.1 (Apple Inc. build 5493)
Cython version  : 0.20.1
NumPy version   : 1.8.0
Numba version   : 0.12.1
llvm version    : 0.12.3
parakeet version: 0.23.2

system     : Darwin
release    : 13.2.0
machine    : x86_64
processor  : i386
CPU count  : 4
interpreter: 64bit
{'fraction_non_alphanumeric': 0.10234278668310727, 'fraction_numerical': 0.02025717808701779, 'mean_word_length': 3.0208923512747874, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 41, 'https://': 5, 'lorem ipsum': 0, 'www.': 4, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '579450', 'license': 'CC0-1.0', 'n_tokens_mistral': 3859, 'n_tokens_neox': 3656, 'n_words': 1053, 'path': 'Day02_EverythingData/notebooks/05 - Theory and Practice.ipynb', 'repo_name': 'LucaFoschini/UCSBDataScienceBootcamp2015', 'size': '11390'}