C++ Оптимизация этого алгоритма

Question

После просмотра некоторых видеороликов Terence Tao я хотел попробовать внедрить алгоритмы в код C++, чтобы найти все простые числа до числа n. В моей первой версии, где у меня было всего целых чисел от 2 до n, чтобы проверить, были ли они делятся на что-либо от 2 до sqrt (n), я получил программу, чтобы найти простые числа от 1 до 10 000 000 за ~ 52 секунды.

Попытка оптимизировать программу и реализовать то, что я теперь знаю, как сито Эратосфена, я предположил, что задача будет выполняться намного быстрее, чем 51 секунда, но, к сожалению, это было не так. Даже идти до 1000000. потребовалось значительное количество времени (не время это, хотя)

#include <iostream> 
#include <vector> 
using namespace std; 

void main() 
{ 
    vector<int> tosieve = {};   
    for (int i = 2; i < 1000001; i++) 
    {          
     tosieve.push_back(i);    
    }          
     for (int j = 0; j < tosieve.size(); j++) 
     { 
      for (int k = j + 1; k < tosieve.size(); k++) 
      { 
       if (tosieve[k] % tosieve[j] == 0) 
       { 
        tosieve.erase(tosieve.begin() + k); 
       } 
      } 
     } 
    //for (int f = 0; f < tosieve.size(); f++) 
    //{ 
    // cout << (tosieve[f]) << endl; 
    //} 
    cout << (tosieve.size()) << endl; 
    system("pause"); 
} 

ли повторное реферирование векторов или что-то? Почему это так медленно? Даже если я полностью упускаю из виду что-то (может быть, полный новичок в этом: я), я думаю, что поиск простых чисел от 2 до 1 000 000 с помощью этого ужасного неэффективного метода будет быстрее, чем мой первоначальный способ найти их от 2 до 10 000 000.

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

Answer 1

Основные операции vector, в том числе erase(), имеют линейную сложность времени O(n).

Поскольку у вас есть две петель размера 10^6, и vector размера 10^6, ваш алгоритм выполняет до 10^18 операций.

Кубические алгоритмы для такого большого N займут огромное количество времени.
N = 10^6 даже достаточно большой для квадратичных алгоритмов.

Пожалуйста, внимательно прочитайте о Sieve of Eratosthenes. Тот факт, что и полный поиск, и алгоритм Сита Эратосфена занял одно и то же время, означает, что вы сделали второй неправильно.

Answer 2

Проблема заключается в том, что «стирание» перемещает каждый элемент в векторе вниз на один, что означает, что это операция O (n).

Есть три альтернативных варианта:

1) Просто пометьте удаленные элементы, как 'пустой' (сделать их 0, например). Это будет означать, что будущие проходы должны пройти через эти пустые позиции, но это не так дорого.

2) Сделайте новый вектор, и push_back новых значений.

3) Использовать std :: remove_if: Это приведет к перемещению элементов вниз, но сделайте это за один проход, поэтому будет более эффективным. Если вы используете std :: remove_if, вам придется помнить, что он не изменяет размер самого вектора.

Answer 3

я вижу две performanse проблемы здесь:

Прежде всего, push_back() придется перераспределить динамический блок памяти один раз в то время. Используйте reserve():

vector<int> tosieve = {}; 
tosieve.resreve(1000001);  
for (int i = 2; i < 1000001; i++) 
{          
    tosieve.push_back(i);    
} 

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

for (auto& x : tosieve) { 
    for (auto y = tosieve.begin(); *y < x; ++y) // this check works only in 
               // the case of an ordered vector 
     if (y != 0 && x % y == 0) x = 0; 
} 
{ // this block will make sure, that sieved will be released afterwards 
    auto sieved = vector<int>{}; 
    for(auto x : tosieve) 
     sieved.push_back(x); 
    swap(tosieve, sieved); 
} // the large memory block is released now, just keep the sieved elements. 

рассмотреть возможность использования стандартных алгоритмов вместо рукописные петель. Они помогают вам заявить о своих намерениях. В этом случае я вижу std::transform() для внешнего контура сита, std::any_of() для внутренней петли, std::generate_n() для заполнения tosieve в начале и std::copy_if() для заполнения sieved (непроверенных код):

vector<int> tosieve = {}; 
tosieve.resreve(1000001); 
generate_n(back_inserter(tosieve), 1000001, []() -> int { 
    static int i = 2; return i++; 
}); 

transform(begin(tosieve), end(tosieve), begin(tosieve), [](int i) -> int { 
    return any_of(begin(tosieve), begin(tosieve) + i - 2, 
        [&i](int j) -> bool { 
         return j != 0 && i % j == 0; 
        }) ? 0 : i; 
}); 
swap(tosieve, [&tosieve]() -> vector<int> { 
    auto sieved = vector<int>{}; 
    copy_if(begin(tosieve), end(tosieve), back_inserter(sieved), 
      [](int i) -> bool { return i != 0; }); 
    return sieved; 
}); 

РЕДАКТИРОВАТЬ:

Еще один способ получить, что сделано:

vector<int> tosieve = {}; 
tosieve.resreve(1000001); 
generate_n(back_inserter(tosieve), 1000001, []() -> int { 
    static int i = 2; return i++; 
}); 
swap(tosieve, [&tosieve]() -> vector<int> { 
    auto sieved = vector<int>{}; 
    copy_if(begin(tosieve), end(tosieve), back_inserter(sieved), 
      [](int i) -> bool { 
       return !any_of(begin(tosieve), begin(tosieve) + i - 2, 
           [&i](int j) -> bool { 
            return i % j == 0; 
           }); 
      }); 
    return sieved; 
}); 

Теперь вместо маркировки элементов, ш e не хочу копировать потом, а просто копировать только те элементы, которые мы хотим скопировать. Это не только быстрее, чем приведенное выше предложение, но и лучше заявляет о намерении.