Как оптимизировать эти циклы C?

Question

Я решил сделать эти Project Euler проблемы в C, потому что у меня создалось впечатление, что C работает быстро, но это, похоже, не так. Оба следующих петель являются чрезвычайно медленно:

int problem_7() { 
    int n = 0; 
    for (int i = 1; i <= 10001; i++) { 
     for (int j = (i==1)?1:n+1; j > 0; j++) { 
      int factorCounter = 0; 
      for (int k = 1; k <= j/2; k++) 
       factorCounter += (j % k == 0); 
      if (factorCounter == 1) { 
       n = j; 
       break; 
      } 
     } 
    } 
    return n; 
} 


long long int problem_10() { 
    long long int sum = 0; 
    for (int i = 2; i < 2000000; i++) { 
     int factorCount = 0; 
     for (int j = 1; j <= i/2; j++) { 
      factorCount += (i % j == 0); 
      sum += i*(j == i/2 && factorCount == 1); 
     } 
    } 

    return sum; 
} 

Есть ли способ, что я могу сделать эти петли работать быстрее? Они делают то, что они должны делать, но каждый из них занимает 5 минут, чтобы выполнить.

Answer 1

С предсказания ветвлений, используя булевы числовые значения не по необходимости:

Глядя на problem7, например, это может быть ускорено с помощью если заявления:

int n = 0; 
    for (int i = 1; i <= 10001; i++) { 
     for (int j = (i==1)?1:n+1; j > 0; j++) { 
      int factorCounter = 0; 
      for (int k = 1; k <= j/2; k++) 
      { 
       if (j%k==0)     // code is changed HERE 
       { 
       factorCounter ++; 
       if (factorCounter > 1) 
       { 
         break; 
       } 
       }       // code change ends here 
      } 
      if (factorCounter == 1) { 
       n = j; 
       break; 
      } 
     } 

Это завершает в 0.88secs в отличие от оригинала 9.5secs - более чем в 10 раз быстрее, чем одно изменение

Объяснение оптимизации и рациональной эквивалентности:

Изменение сделано было из исходной строки:

factorCounter += (j % k == 0); 

Первое изменение, которое его эквивалент:

if (j%k==0) 
{ 
    factorCounter ++; 
} 

Обратите внимание, как factorCounter может увеличиваться только, а после цикла любое значение свыше 1 отбрасывается, поскольку (factorCounter == 1) будет ложным, поэтому, если оно больше 1, нет причин продолжать цикл. Также обратите внимание, что значение factorCounter может быть изменен только при (j%k==0) поэтому тест на factorCounter > 1 должно происходить внутри, если проверки, код теперь:

if (j%k==0) 
{ 
     factorCounter ++; 
     if (factorCounter > 1) 
     { 
     break; // We stop the loop much earlier HERE 
     } 
} 

И выход из цикла раньше, что дает прирост производительности

Answer 2

Думаю, я отвечу на этот вопрос. Ваша программа медленная, потому что ваши петли плохо разработаны и плохо вложены. Я не собираюсь проводить анализ сложности, но вы находитесь где-то в диапазоне O (N^x), где x> 4 (из того, что я могу сказать).

Это просто плохое программирование, и оно мало связано с оптимизацией цикла. Вам нужно использовать что-то вроде Sieve of Eratosthenes для решения Euler 7. Я не дам вам решение здесь, как и в статье Wiki, это довольно тривиально.

Answer 3

C быстро. Языки более высокого уровня также могут быть быстрыми. Но даже лучший компилятор не может оптимизировать дополнительные операции, которые у вас есть! Простым способом сокращения числа операций в вашем алгоритме проблемы 7 было бы разбить самый глубокий цикл, если factorCounter становится больше 1. Извините, что сломал его вам, но: он не является компилятором, это алгоритм!

Answer 4

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

#include <iostream> 
#include <cmath> 

using namespace std; 

bool isPrime(int j) 
{ 
    for(int fac = 2; fac < sqrt(j)+0.5; ++fac) 
     if(j%fac == 0) 
      return false; 

    return true; 
} 

int main() 
{ 
    int primesFound = 1; // 2 is prime 
    int possiblePrime = 1; 

    while(primesFound != 10001) 
    { 
     possiblePrime += 2; 
     if(isPrime(possiblePrime)) 
      ++primesFound; 
    } 

    cout << possiblePrime << endl; 
}