Эффективность алгоритма - эффективна ли частичная развертка цикла, если требуется больше сравнений?

Question

Как судить, стоит ли ставить два дополнительных задания в итерации дорого или устанавливать условие if для проверки другой вещи? здесь я уточняю. вопрос состоит в том, чтобы сгенерировать и напечатать первые n членов последовательности Фибоначчи, где n> = 1. моя машина в C была:

#include<stdio.h>
void main()
{
    int x=0,y=1,output=0,l,n;
    printf("Enter the number of terms you need of Fibonacci Sequence ? ");
    scanf("%d",&n);
    printf("\n");
    for (l=1;l<=n;l++)
    {
        output=output+x;
        x=y;
        y=output;
        printf("%d ",output);
    }
}

но автор книги «Как решить ее с помощью компьютера» говорит, что она неэффективна, поскольку она использует два дополнительных назначения для одного сгенерированного числа Фибоначчи. он предложил:

a=0
b=1
loop: 
print a,b
a=a+b
b=a+b

Я согласен, что это более эффективно, так как все время сохраняет актуальность a и b, и одно назначение генерирует одно число. НО это печатает или поставляет два числа Фибоначчи одновременно. Предположим, вопрос состоит в том, чтобы сгенерировать нечетное количество терминов, что бы мы сделали? Автор предложил поставить условие проверки, чтобы проверить, является ли n нечетным числом. разве мы не потеряем преимущества сокращения количества назначений, добавляя тест if в каждую итерацию?

Answer 1

Я считаю очень плохим совет автора даже упоминать об этом в книге, предназначенной для начинающих программистов.( Редактировать : по правде говоря, книга была первоначально опубликована в 1982 году, когда программирование, как правило, было гораздо более низкого уровня, чем сейчас.)

99,9% кода ненужно оптимизировать.Особенно в коде, подобном этому, который смешивает чрезвычайно дешевые операции (арифметика с целыми числами) с очень дорогими операциями (ввод-вывод), оптимизация дешевой части - пустая трата времени.

Подобные микрооптимизации должны толькоучитывайте критический по времени код, когда необходимо выжать из своего оборудования каждый бит производительности.

Когда вам это нужно, единственный способ узнать, какой из нескольких вариантов работает лучше всего, - это измерение .Даже в этом случае результаты могут изменяться с различными процессорами, платформами, конфигурациями памяти ...

Answer 2

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

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

Answer 3

Мой первый совет перекликается с остальными: стремитесь сначала к чистому и понятному коду, а затем оптимизируйте, где вы знаете, что есть проблемы с производительностью. (Трудно представить критический по времени секвенсор Фибоначчи ...)

Тем не менее, выступая в роли человека, который работает в системах, где важны микросекунды, есть простой ответ на вопрос, который вы задаете: выполните тест «если нечетно» только один раз, а не внутри цикла.

Общая схема развертывания петли:

  create X repetitions of the loop logic.
  divide N by X.
  execute the loop N/X times.
  handle the N%X remaining items. 

Для вашего конкретного случая:

a=0;
b=1;
nLoops = n/2;
while (nloops-- > 0) {
  print a,b;
  a=a+b;
  b=a+b;
}
if (isOdd(n)) {
  print a; 
}

(Обратите также внимание, что N / 2 и isOdd тривиально реализованы и чрезвычайно быстры на двоичном компьютере.)