next_opt vs fft.py

from __future__ import print_function
import numpy as np
from timeit_utils import timeit_fast
from numpy.random import rand
import matplotlib.pyplot as plt
import datetime
import socket
import sys

N_max = 100000
num = 1000
# Random numbers between 1 and N_max, uniformly distributed on a log scale
lens = [int(np.ceil(N_max**x)) for x in rand(num)]
lens = np.union1d(lens, lens)  # Remove duplicates
print(len(lens), 'tests')

times = []
for n in lens:

    print(n, end=' ')

    setup = """
from numpy.random import randn
a = randn({n})
n = {n}
from scipy.fftpack import fft
from helper import next_fast_len
""".format(**locals())
    c1 = 'next_fast_len(n)'
    c2 = 'fft(a)'
    c1time = timeit_fast(c1, setup)[1]
    c2time = timeit_fast(c2, setup)[1]

    times.append((n, c1time, c2time, c1time / c2time))

times = np.asarray(times)

plt.figure()
plt.loglog(times[:, 0], times[:, 1], 'b.', label=c1)
plt.loglog(times[:, 0], times[:, 2], 'r.', label=c2)
plt.legend(loc='best')
plt.grid(True, color = '0.7', linestyle='-', which='major')
plt.grid(True, color = '0.9', linestyle='-', which='minor')

hostname = socket.gethostname()
version = sys.version[:5]
datestamp = datetime.datetime.now().strftime("%Y-%m-%d %H-%M-%S")

plt.savefig(' '.join((hostname, version, datestamp)) + '.png')
plt.show()

timeit_utils.py

"""
Created on Thu Oct 03 20:11:05 2013
"""

from timeit import Timer # Don't mess with IPython's timeit magic word

def timeit_auto(stmt="pass", setup="pass", repeat=3):
    """
    http://stackoverflow.com/q/19062202/190597
    Imitate default behavior when timeit is run as a script.

    Runs enough loops (>=10) so that total execution time is greater 
    than 0.2 sec, and then repeats that 3 times and keeps the lowest value.

    Returns the number of loops and the time for each loop in microseconds
    """
    t = Timer(stmt, setup)

    # determine number so that 0.2 <= total time < 2.0
    for i in range(1, 10):
        number = 10**i
        x = t.timeit(number) # seconds
        if x >= 0.2:
            break
    r = t.repeat(repeat, number)
    best = min(r)
    usec = best * 1e6 / number
    return number, usec


def timeit_fast(stmt="pass", setup="pass", repeat=3):
    """
    Faster, less painstaking version of timeit_auto for automated 
    testing of many inputs.
    
    Will do only 1 loop (like IPython's timeit) with no repetitions 
    (unlike IPython) for very slow functions.  Only does enough loops 
    to take 5 ms, which seems to produce similar results on Windows at 
    least, and avoids doing an extraneous cycle that isn't measured.
    """
    t = Timer(stmt, setup)

    # determine number so that 5 ms <= total time
    x = 0
    for i in range(0, 10):
        number = 10**i
        x = t.timeit(number) # seconds
        if x >= 5e-3 / 10: # 5 ms for final test, 1/10th that for this one
            break
    if x > 1: # second
        # If it's macroscopic, don't bother with repetitions
        best = x
    else:
        number *= 10
        r = t.repeat(repeat, number)
        best = min(r)
        
    usec = best * 1e6 / number
    return number, usec