Может кто-нибудь написать этот код с лучшей логикой?

Question

Я застрял с этой проблемой на 2 дня. Может ли кто-нибудь помочь мне с логикой?

Я работаю над программами на C ++ для хороших алгоритмов. Сейчас я работаю над алгоритмом Даниелсона-Ланцоша для вычисления БПФ последовательности.

Глядя на

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

Do not сжимает ваш код. Пожалуйста? Довольно пожалуйста? С вишней сверху?

Если вы не можете создать лучший алгоритм , сжатие существующего фрагмента кода только сделает его похожим на нечто прямо из ворот самого Ада. Никто не сможет этого понять. Вы не сможете этого понять, даже через несколько дней.

Даже компилятор может быть слишком запутан всеми ветками, чтобы правильно его оптимизировать.

Если вы пытаетесь улучшить производительность, учтите следующее:

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. Это кажется мне преждевременной оптимизацией.