有人可以用更好的逻辑写这段代码吗？

Question

我被这个问题困住了2天。有人能帮我理解逻辑吗？

我正在研究C++程序以获得更好的算法。我现在正在研究Danielson-Lanczos算法来计算序列的FFT。

看着

mmax=2; 
while (n>mmax) { 
    istep = mmax<<1; 
    theta = -(2*M_PI/mmax); 
    wtemp = sin(0.5*theta); 
    wpr = -2.0*wtemp*wtemp; 
    wpi = sin(theta); 
    wr = 1.0; 
    wi = 0.0; 

    for (m=1; m < mmax; m += 2) { 
     for (i=m; i <= n; i += istep) { 
      j=i+mmax; 
      tempr = wr*data[j-1] - wi*data[j]; 
      tempi = wr * data[j] + wi*data[j-1]; 

      data[j-1] = data[i-1] - tempr; 
      data[j] = data[i] - tempi; 
      data[i-1] += tempr; 
      data[i] += tempi; 
     } 
     wtemp=wr; 
     wr += wr*wpr - wi*wpi; 
     wi += wi*wpr + wtemp*wpi; 
    } 
    mmax=istep; 
} 

来源：http://www.eetimes.com/design/signal-processing-dsp/4017495/A-Simple-and-Efficient-FFT-Implementation-in-C--Part-I

有什么办法来逻辑地写代码，使得整个for-loop部分被减少到只有4行代码（或更好）？

Answer 1

更好的缩进会有很长的路要走。我为你解决了这个问题。此外，这似乎要求更好的变量位置。变量名称对我来说不清楚，但这可能是因为我不知道这个算法属于哪个域。

通常，如果您想使复杂的代码更容易理解，请确定子算法并将它们放入自己的（内联）函数中。 （将代码片段放到一个函数中有效地赋予它一个名称，并使得变量进出代码更加明显。通常，这会使代码更易于消化。）
我不确定这是必需的这段代码，但。

只是浓缩但是，代码不会使其更具可读性。相反，它会让它变得更加浓缩。

Answer 2

1. 我不相信你能够使它大大缩短。
2. 如果此代码缩短了很多，我猜测它会显着降低可读性。
3. 由于逻辑相对清晰，行数并不重要—除非你打算在codegolf.stackexchange.com上使用它，这是一个你应该相信你的编译器来帮助你的地方（因为它会）
4. 这让我觉得不成熟的优化。

Answer 3

做不是压缩你的代码。请？请好吗？顶部有樱桃？

除非你可以创建一个更好的算法，否则压缩现有的一段代码只会使它看起来像是直接离开Hell本身的门。没有人能够理解它。 即使在几天后，您也无法理解。

即使编译器可能会被所有分支弄糊涂以正确优化它。

如果你想提高性能，考虑以下因素：

1. 过早的优化是万恶之源。

2. 先处理算法，然后处理代码。

3. 行计数可能与生成的可执行代码的大小完全没有关系。

4. 编译器不喜欢纠缠的代码路径和复杂的表达式。真的...

5. 除非代码是真的性能的关键，可读性胜过一切其他。

6. 如果它是性能至关重要，首先配置文件，然后开始优化。

Answer 4

您可以使用复数类来反映所涉及的数学。

代码的很大一部分是由两个复数乘法组成的。

您可以重写代码为：

unsigned long mmax=2; 
while (n>mmax) 
{ 
    unsigned long istep = mmax<<1; 
    const complex wp = coef(mmax); 
    complex w(1. , 0.); 
    for (unsigned long m=1; m < mmax; m += 2) 
    { 
     for (unsigned long i=m; i <= n; i += istep) 
     { 
      j=i+mmax; 
      complex temp = w * complex(data[j-1] , data[j]); 
      complexref(data[j-1] , data[j]) = complex(data[i-1] , data[i]) - temp ; 
      complexref(data[i-1] , data[i]) += temp ; 
     } 
     w += w * wp ; 
    } 
    mmax=istep; 
} 

有了：

struct complex 
{ 
    double r , i ; 
    complex(double r , double i) : r(r) , i(i) {} 

    inline complex & operator+=(complex const& ref) 
    { 
     r += ref.r ; 
     i += ref.i ; 
     return *this ; 
    } 
}; 

struct complexref 
{ 
    double & r , & i ; 
    complexref(double & r , double & i) : r(r) , i(i) {} 

    inline complexref & operator=(complex const& ref) 
    { 
     r = ref.r ; 
     i = ref.i ; 
     return *this ; 
    } 

    inline complexref & operator+=(complex const& ref) 
    { 
     r += ref.r ; 
     i += ref.i ; 
     return *this ; 
    } 
} ; 

inline complex operator*(complex const& w , complex const& b) 
{ 
    return complex(
     w.r * b.r - w.i * b.i , 
     w.r * b.i + w.i * b.r 
    ); 
} 

inline complex operator-(complex const& w , complex const& b) 
{ 
    return complex(w.r - b.r , w.i - b.i); 
} 
inline complex coef(unsigned long mmax) 
{ 
    double theta = -(2*M_PI/mmax); 
    double wtemp = sin(0.5*theta); 
    return complex(-2.0*wtemp*wtemp , sin(theta)); 
}