Timing different Implementations of palindrome functions

In [1]:
import re
import timeit
import string

# All functions return True if an input string is a palindrome. Else returns False.

#############################################################
#### case-insensitive ignoring punctuation characters
############################################################

def palindrome_short(my_str):
    stripped_str = "".join(l.lower() for l in my_str if l.isalpha())
    return stripped_str == stripped_str[::-1]

def palindrome_regex(my_str):
    return re.sub('\W', '', my_str.lower()) == re.sub('\W', '', my_str[::-1].lower())

def palindrome_stringlib(my_str):
    LOWERS = set(string.ascii_lowercase)
    letters = [c for c in my_str.lower() if c in LOWERS]
    return letters == letters[::-1]

LOWERS = set(string.ascii_lowercase)
def palindrome_stringlib2(my_str):
    letters = [c for c in my_str.lower() if c in LOWERS]
    return letters == letters[::-1]

def palindrome_isalpha(my_str):
    stripped_str = [l for l in my_str.lower() if l.isalpha()]
    return stripped_str == stripped_str[::-1]



############################################################
#### functions considering all characters (case-sensitive)
############################################################

def palindrome_reverse1(my_str):
    return my_str == my_str[::-1]

def palindrome_reverse2(my_str):
    return my_str == ''.join(reversed(my_str))

def palindrome_recurs(my_str):
    if len(my_str) < 2:
        return True
    if my_str[0] != my_str[-1]:
        return False
    return palindrome(my_str[1:-1])
In [2]:
test_str = "Go hang a salami. I'm a lasagna hog."

print('case-insensitive functions ignoring punctuation characters')
%timeit palindrome_short(test_str)
%timeit palindrome_regex(test_str)
%timeit palindrome_stringlib(test_str)
%timeit palindrome_stringlib2(test_str)
%timeit palindrome_isalpha(test_str)

print('\n\nfunctions considering all characters (case-sensitive)')
%timeit palindrome_reverse1(test_str)
%timeit palindrome_reverse2(test_str)
%timeit palindrome_recurs(test_str)
case-insensitive functions ignoring punctuation characters
10000 loops, best of 3: 15.5 µs per loop
10000 loops, best of 3: 19.5 µs per loop
100000 loops, best of 3: 11.7 µs per loop
100000 loops, best of 3: 8.24 µs per loop
100000 loops, best of 3: 9.38 µs per loop


functions considering all characters (case-sensitive)
1000000 loops, best of 3: 507 ns per loop
100000 loops, best of 3: 3.08 µs per loop
1000000 loops, best of 3: 581 ns per loop
In [13]:
import timeit

funcs_s = ['palindrome_short', 'palindrome_regex', 'palindrome_stringlib', 
         'palindrome_stringlib2', 'palindrome_isalpha'] 

funcs_ins = ['palindrome_reverse1', 'palindrome_reverse2', 'palindrome_recurs']

times_s, times_ins = [], []

for f in funcs_s:
    times_s.append(min(timeit.Timer('%s(test_str)' %f, 
                      'from __main__ import %s, test_str' %f)
                              .repeat(repeat=3, number=1000)))
    
for f in funcs_ins:
    times_ins.append(min(timeit.Timer('%s(test_str)' %f, 
                      'from __main__ import %s, test_str' %f)
                              .repeat(repeat=3, number=1000)))
In [8]:
%pylab inline
In [ ]:
import matplotlib.pyplot as plt

labels = [('cy_lstsqr', 'Cython implementation'), 
          ('lin_lstsqr_mat', 'numpy matrix equation'),
          ('numpy_lstsqr', 'numpy.linalg.lstsq()'), 
          ('scipy_lstsqr', 'scipy.stats.linregress()')] 

matplotlib.rcParams.update({'font.size': 12})

fig = plt.figure(figsize=(10,8))
for f in funcs_s:
    plt.plot(orders_n, times_n[lb[0]], alpha=0.5, label=lb[1], marker='o', lw=3)
plt.xlabel('sample size n')
plt.ylabel('time per computation in milliseconds [ms]')
plt.xlim([1,max(orders_n) + max(orders_n) * 10])
plt.legend(loc=2)
plt.grid()
plt.xscale('log')
plt.yscale('log')
plt.title('Performance of least square fit implementations for different sample sizes')
plt.show()
In [29]:
import matplotlib.pyplot as plt

x_pos = np.arange(len(times_s))
plt.bar(x_pos, times_s, align='center', alpha=0.5, color="green")
plt.xticks(x_pos, funcs_s, rotation=90)
plt.ylabel('time per computation in ms')
plt.title('Performance of different case-sensitive palindrome functions')
plt.grid()
plt.show()

x_pos = np.arange(len(times_ins))
plt.bar(x_pos, times_ins, align='center', alpha=0.5, color="blue")
plt.xticks(x_pos, funcs_ins, rotation=90)
plt.ylabel('time per computation in ms')
plt.title('Performance of different case-insensitive palindrome functions')
plt.grid()
plt.show()