[Numpy-discussion] Correlation function about a factor of 100 slower than matlab/mathcad ... but with fft even worse ?

[qubax at gmx.at]

My own solution (i just heard that a very similar fix is (about to
be) included in the new svn version) - for those who need a quickfix:

*) This quick and dirty solution is about a factor of 300 faster
for an input of 10^5 random numbers. Probably alot more for larger
vectors.

*) The deviation from correlate(v,v,mode='full') is max. about 10^-10 and
similar to the difference between conv() and xcorr() in matlab.


The trick: please notice the fft(x,2**_nextPow2()) part.


------------------------------------------

def myXcorrfun(x):
  len_x=len(a)
  maxlag = len_x - 1
  c = ifft(abs(fft(x,2**__nextPowOf2(2*len_x-1)))**2)
  # force it to be real
  c = real(c)
  c_final = append(c[-maxlag:],c[0:maxlag+1])
  return c_final

def __nextPowOf2(x):
  # round up what remains after log2 ... that should be
  # the next highest power of 2 for the given number
  return ceil(log2(x))

----------------------------------------

you can give it a quick try via:


expon = range(5)

for k in expon:
  a = random.rand(10**k)
  print 'testing with 10^',k,' random numbers'

  tic=time.time()
  myc = myXcorrfun(a)
  mytime = time.time()-tic
  print mytime,'seconds for myXcorr'

  tic=time.time()
  pyc = correlate(a,a,mode='full')
  pytime = time.time()-tic
  print pytime,'seconds for scipy correlate'
  print
  print 'estimated speedup:', int(pytime/mytime)
  print max(myc-pyc),' max deviation between the two'
  print

I hope it helps one or the other out there.

With best regards,
q

On Wed, Nov 25, 2009 at 09:09:50PM +0200, Pauli Virtanen wrote:
> ke, 2009-11-25 kello 19:23 +0100, qubax at gmx.at kirjoitti:
> [clip]
> > Could someone please investigate why correlate and especially
> > fftconvolve are orders of magnitude slower?
> 
> Read http://projects.scipy.org/numpy/ticket/1260
> 
> _______________________________________________
> NumPy-Discussion mailing list
> NumPy-Discussion at scipy.org
> http://mail.scipy.org/mailman/listinfo/numpy-discussion

-- 
The king who needs to remind his people of his rank, is no king.

A beggar's mistake harms no one but the beggar. A king's mistake,
however, harms everyone but the king. Too often, the measure of
power lies not in the number who obey your will, but in the number
who suffer your stupidity.