Skip to main content
 首页 » 编程设计

python之python中最快的递归FFT

2024年12月31日8qq号

<分区>

我正在为精准农业应用程序处理根据无人机照片创建的 map ,该应用程序使用 Rhino 6 中的 IronPython 2.7 脚本分析拥有 10,000 棵树的 Orchard 。我使用 FFT 来确定 Y&X 中树木的间距或间距方向。对于 FFT,我从 2015 年 5 月 25 日 StackOverflow 的一篇递归 FFT 帖子开始,该帖子将由 Mike Muller 在 Python 2.7 中运行,

def fft(x): 
    N = len(x) 
    T = exp(-2*pi*1j/N) 
    if N > 1: 
        x = fft(x[::2]) + fft(x[1::2]) 
        for k in xrange(N/2): 
            xk = x[k] 
            x[k] = xk + T**k*x[k+N/2] 
            x[k+N/2] = xk - T**k*x[k+N/2] 
    return x 

效果很好。玩代码一段时间后,我使用这段代码获得了超过 2 倍的加速:

from cmath import exp, pi 
 
# Create dictionary for lookup of exp term. 
def make_wm(N): 
    global Xwm 
    Xwm = {} 
    for i in range(N.bit_length()-1,0,-1): Xwm[N] = exp(-2j*pi/N); N //= 2 
 
# FFT 
def fft(x,N): 
    N2 = N // 2 
    if N > 2: x = fft(x[::2],N2) + fft(x[1::2],N2) # When N == 2, x = [x[0],x[1]] is processed below. Thus fft is never called with N = 1. 
    wm = Xwm[N]; w = 1 # Get initial exp value from dictionary lookup. 
    for k in xrange(N2): # This loop is executed a total of 0.5*N*log2(N) times. 
        kn = k + N2 
        xk = x[k] 
        t = w*x[kn] 
        x[k] = xk + t 
        x[kn] = xk - t 
        w *= wm # Use multiply to generate subsequent exp terms. 
    return x 
 
# From the main code, fft is called with: 
    N = len(X) 
    make_wm(N) 
    F = fft(X,N) 
 
# Note: 1 FFT can transform 2 real-data inputs by interleaving the inputs and separating the output: 
    X = map(complex,yi,xi) 
    N = len(X) 
    make_wm(N) 
    F = fft(X,N) 
    # Separate two complex outputs of length N/2 from the N-terms in the FFT result. 
    yfft,xfft = separate_output(F) 

此版本消除了一半的递归调用,并从 fft 代码中删除了缓慢的 exp 和 power (T**k) 计算。由于 Y&X 方向的间距都需要,并且用于此计算的 FFT 输入数据是实数值,我通过使用一个 FFT 通过交错 Y&X 数据同时转换两个 Y&X 数据集,获得了另外 2 倍的加速设置使用:

# Interleave two real-data inputs. 
X = map(complex,yi,xi) 

然后使用以下方法将 FFT 结果分离为 Y&X 分量:

# Separate two N/2-point ffts from one N-point fft. 
def separate_output(X): 
    N = len(X) 
    N2 = N // 2 
    # Extend X by copying 0th term to Nth entry so that extracting DC term (k=0) does not cause overflow. 
    X.append(X[0]) 
    # Separate 2 ffts. 
    G = [(X[k].real + X[N-k].real + 1j*(X[k].imag - X[N-k].imag))/(2.*N) for k in xrange(N2)] 
    H = [(X[k].imag + X[N-k].imag - 1j*(X[k].real - X[N-k].real))/(2.*N) for k in xrange(N2)] 
    return G,H 

我无法在 Rhino 6 的 IronPython 中访问 numpy 的 FFT,后者会快得多。

我的问题:

  • 有没有办法进一步加速 Python 2.7 中的 fft?
  • 非递归版本会更快吗?
  • 是否有人拥有 split 基数 FFT 的代码,它的运算次数可以减少大约 2/3?