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

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. 行数可能与生成的可执行代码的大小完全没有关系。

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

5. 除非代码真的对性能至关重要，否则可读性胜过一切。

6. 如果它对性能至关重要，则首先进行分析，然后开始优化。

Answer 3

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

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

您可以将代码重写为：

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) );
}

Answer 4

1. 我不相信你能够让它变得更短。
2. 如果这段代码变得更短，我猜它会显着降低可读性。
3. 由于逻辑相对清晰，行数并不重要 - 除非您计划在 codegolf.stackexchange.com 上使用它，否则您应该相信您的编译器会帮助您（因为它会）
4. 这让我印象深刻作为过早的优化。