0

私はこの問題で2日間立ち往生しています。誰かがロジックを手伝ってくれますか?

優れたアルゴリズムの C++ プログラムに取り組んでいます。私は現在、シーケンスの FFT を計算するための Danielson-Lanczos アルゴリズムに取り組んでいます。

見つめている

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

関連する数学を反映するために、複素数クラスを使用できます。

コードの大部分は、2 つの複雑な乗算で構成されています。

コードを次のように書き換えることができます。

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 に答える