Какие операции занимают много времени и как их избежать?

Question

Я довольно новичок в C++, и я хочу узнать, как оптимизировать скорость моих программ. В настоящее время я работаю над программой, которая вычисляет идеальные числа от 1 до 1.000.000. Идеальное число - это то, где сумма его собственных делителей равна самому числу. Например. 28 - идеальное число, потому что 1 + 2 + 4 + 7 + 14 = 28. Ниже приведен мой код

#include <iostream> 
using namespace std; 

int main() { 

int a = 1000000; 

for(int i = 1; i <= a; ++i) 
{ 
    int sum = 0; 
    int q; 

    // The biggest proper divisor is half the number itself 
    if(i % 2 == 0) q = i/2; 
    else q = (i+1)/2; 


    for(int j = 1; j <= q; ++j) 
    { 
     if(i % j == 0) sum += j; 
    } 

    //Condition for perfect number 
    if(sum == i) cout << i << " is a perfect number!" << endl; 
} 

system("pause"); 

return 0; 
} 

Какие операции в этом коде требуется много времени? Как я могу улучшить скорость программы? В общем, как узнать, какие операции занимают много времени и как их избежать?

Answer 1

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

Чтобы ответить на ваш вопрос, а именно: самое время в этой программе будет потрачено на этой линии:

system("pause"); 

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

Answer 2

Мои Эмпирические правила:

• условных переходов (т.е. сравнения) являются дорогостоящими
• подразделения являются дорогостоящими (а также по модулю%)
• предпочитают целочисленные операции над плавающей точкой

Как их избежать?

Ну, нет простого ответа. Во многих случаях вы просто не можете.

Вы избегаете условных ветвей с помощью ветвящихся выражений или улучшаете логику программы.

Вы избегаете делений с помощью сдвигов или поисковых таблиц или переписывающих выражений (когда это возможно).

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

В данном примере вам необходимо сосредоточиться на теле самой внутренней петли. Это линия, которая наиболее часто выполняется (около 125000000000 раз против 1000000 для других). К сожалению, есть сравнение и разделение, которые трудно удалить.

Оптимизация других частей кода не будет иметь измеримого эффекта. В частности, не беспокойтесь о заявлении cout: он будет называться всего 4 раза.

Answer 3

Вы можете торговать из расчета по потреблению памяти со следующим:

const int max = 1000000; 
std::vector<std::size_t> a(max); 

for(std::size_t i = 1; i != a.size(); ++i) { 
    for (std::size_t j = 2 * i; j < a.size(); j += i) { 
     a[j] += i; 
    } 
} 
for (std::size_t i = 1; i != a.size(); ++i) { 
    if(a[i] == i) { 
     std::cout << i << " is a perfect number!" << std::endl; 
    } 
} 

Live example

Answer 4

Отрасль: if с, циклы, вызовы функций и goto являются дорогостоящими. Они имеют тенденцию отвлекать процессор от выполнения операций передачи данных и математических операций.

Например, вы можете устранить if заявление:

q = (i + (i % 2))/2; // This expression not simplified. 

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

Операции ввода-вывода являются дорогостоящими, особенно с использованием форматированного ввода-вывода. Попробуйте это:

if(sum == i) 
{ 
    static const char text[] = " is a perfect number!\n"; 
    cout << i; 
    cout.write(text, sizeof(text) - 1); // Output as raw data. 
} 

Division и по модулю операции являются дорогостоящими.
Если вы можете разделить на 2, вы можете преобразовать деление в сдвиг вправо.
Возможно, вы сможете избежать операций с модулем, используя двоичный код AND.