You can check everything in the notebook, it will generate all the data.
I checked the runtime for sizes in logspace(2, 7, 25). I know that the
fft will work faster for array sizes that are a power of 2 but
differences on 3 orders of magnitude is huge. I also attached a script
generated from the notebook that you can run as well
best Max
On Thu, 2013-11-14 at 10:45 -0600, Charles Waldman wrote:
> Can you post the raw data? It seems like there are just a couple of "bad"
> sizes, I'd like to know more precisely what these are.
>
> It's typical for FFT to perform better at a sample size that is a power of
> 2, and algorithms like FFTW take advantage of factoring the size, and
> "sizes that are products of small factors are transformed most efficiently."
>
> - Charles
>
> On Thu, Nov 14, 2013 at 10:18 AM, Max Linke <max_li...@gmx.de> wrote:
>
> > Hi
> >
> > I noticed some strange scaling behavior of the fft runtime. For most
> > array-sizes the fft will be calculated in a couple of seconds, even for
> > very large ones. But there are some array sizes in between where it will
> > take about ~20 min (e.g. 400000). This is really odd for me because an
> > array with 10 million entries is transformed in ~2s. Is this typical for
> > numpy?
> >
> > I attached a plot and an ipynb to reproduce and illustrate it.
> >
> > best Max
> >
> > _______________________________________________
> > NumPy-Discussion mailing list
> > NumPy-Discussion@scipy.org
> > http://mail.scipy.org/mailman/listinfo/numpy-discussion
> >
> >
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion@scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion
import numpy as np
import matplotlib.pyplot as plt
import timeit
x_length = np.logspace(2, 7, 25)
times = np.empty((25,2))
for i, length in enumerate(x_length):
setup = 'import numpy as np\ntrj=np.random.uniform(low=-1,high=1,size=%i)' % (length)
times[i] = timeit.repeat(stmt='fft=np.fft.fft(trj)', setup=setup,
repeat=2, number=2)
plt.plot(x_length, times[:, 0], marker='o');
plt.plot(x_length, times[:, 1], marker='o');
#plt.yscale('log');
plt.xscale('log');
plt.xlabel('elements in array');
plt.ylabel('execution time in seconds');
plt.show()
## Check if fft produces correct results
trj = np.sin(np.arange(x_length[-1]))
fft = np.fft.fft(trj)
plt.plot(np.abs(fft) ** 2)
plt.title('fourier spectra of sin(x)');
plt.show()
acf = np.fft.ifft(np.abs(fft) **2) / x_length[-1]
acf = np.real(acf[:acf.size / 2] / acf[0])
plt.plot(acf, marker='o');
plt.xlim(0, 10)
plt.title('acf of sin(x)');
plt.show()
trj = np.random.uniform(low=-1, high=1, size=x_length[-1])
fft = np.fft.fft(trj)
plt.plot(np.abs(fft) ** 2)
plt.title('fourier spectra of noise');
plt.show()
acf = np.fft.ifft(np.abs(fft) ** 2) / x_length[-1]
acf = np.real(acf[:acf.size / 2] / acf[0])
plt.plot(acf, marker='o');
plt.xlim(0, 10);
plt.title('acf of noise');
plt.show()
_______________________________________________
NumPy-Discussion mailing list
NumPy-Discussion@scipy.org
http://mail.scipy.org/mailman/listinfo/numpy-discussion
