0

我被这个问题困扰了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 行代码（甚至更好）？

4

4 回答 4

8

更好的缩进会有很长的路要走。我为你修好了。此外，这似乎要求更好的变量局部性。我不清楚变量名称，但这可能是因为我不知道该算法所属的域。

通常，如果您想让复杂的代码更易于理解，请识别子算法并将它们放入自己的（内联）函数中。（将代码片段放入函数中有效地为其命名，并使变量进出代码的传递更加明显。通常，这使代码更容易消化。）
我不确定这对于这篇文章是否必要不过，代码。

然而，仅仅压缩代码不会使其更具可读性。相反，它只会使其更加浓缩。

于 2011-09-29T17:02:45.870 回答
5

不要压缩你的代码。请？请问好看吗？上面有樱桃？

除非您可以创建更好的算法，否则压缩现有代码只会使其看起来像是直接从地狱之门出来的东西。没有人能够理解它。即使在几天之后，您也无法理解它。

即使是编译器也可能会被所有分支弄糊涂，无法正确优化它。

如果您正在尝试提高性能，请考虑以下事项：

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

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

  3. 行数可能与生成的可执行代码的大小完全无关。

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

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

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

于 2011-09-29T17:21:48.940 回答
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) );
}
于 2011-09-29T19:17:57.423 回答
2
  1. 我不相信你能把它大大缩短。
  2. 如果这段代码更短，我猜它会大大降低可读性。
  3. 由于逻辑相对清晰，行数无关紧要——除非你打算在 codegolf.stackexchange.com 上使用它，这是一个你应该相信你的编译器可以帮助你的地方（因为它会）
  4. 这让我觉得过早的优化。
于 2011-09-29T17:06:11.643 回答