простое число менее 2 миллиардов - использование std :: list снижает производительность

Question

Задача состоит в том, чтобы найти простое число менее 2 миллиардов на таймфрейме <20 секунд. Я следовал ниже подходов. </p>

1. Разделите число n на список чисел k (k - заняло 20 секунд

2. Разделите число n на список простых чисел ниже sqrt (n) . В этом сценарии я сохранил простые числа в std :: list - заняло более 180 секунд

Может ли кто-нибудь помочь мне понять, почему 2-й подход занял много времени, хотя мы не сократили число делений на 50% (приблизительно)? или я выбрал неправильную структуру данных?

Подход 1:

#include <iostream>
#include<list>
#include <ctime>
using namespace std;

list<long long> primeno;
void ListPrimeNumber();

int main()
{
    clock_t time_req = clock();
    ListPrimeNumber();
    time_req = clock() - time_req;
    cout << "time taken " << static_cast<float>(time_req) / CLOCKS_PER_SEC << " seconds" << endl;
    return 0;
}

void check_prime(int i);

void ListPrimeNumber()
{
    primeno.push_back(2);
    primeno.push_back(3);
    primeno.push_back(5);
    for (long long i = 6; i <= 20000000; i++)
    {
        check_prime(i);
    }

}

void check_prime(int i)
{
    try
    {
        int j = 0;
        int limit = sqrt(i);
        for (j = 2 ; j <= limit;j++)
        {
            if(i % j == 0)
            {
                break;
            }
        }
        if( j > limit)
        {
            primeno.push_back(i);
        }
    }

    catch (exception ex)
    {
        std::cout << "Message";
    }
}

Подход 2:

#include <iostream>
#include<list>
#include <ctime>
using namespace std;

list<long long> primeno;
int noofdiv = 0;
void ListPrimeNumber();

int main()
{
    clock_t time_req = clock();
    ListPrimeNumber();
    time_req = clock() - time_req;
    cout << "time taken " << static_cast<float>(time_req) / CLOCKS_PER_SEC << " seconds" << endl;
    cout << "No of divisions : " << noofdiv;
    return 0;
}

void check_prime(int i);

void ListPrimeNumber()
{
    primeno.push_back(2);
    primeno.push_back(3);
    primeno.push_back(5);
    for (long long i = 6; i <= 10000; i++)
    {
        check_prime(i);
    }

}

void check_prime(int i)
{
    try
    {
        int limit = sqrt(i);
        for (int iter : primeno)
        {
            noofdiv++;
            if (iter <= limit && (i%iter) == 0)
            {
                break;
            }
            else if (iter > limit)
            {
                primeno.push_back(i);
                break;
            }
        }
    }

    catch (exception ex)
    {
        std::cout << "Message";
    }
}

Answer 1

Причина, по которой ваш второй пример занимает больше времени, заключается в том, что вы итерируете std::list.

A std::list в C ++ - это связанный список, что означает, что он не использует непрерывную память.Это плохо, потому что для итерации списка вы должны переходить от узла к узлу непредсказуемым образом (к процессору / сборщику).Кроме того, вы, скорее всего, «используете» только несколько байтов каждой кеш-линии.Оперативная память медленная.Извлечение байта из ОЗУ занимает лот дольше, чем извлечение его из L1.В наши дни процессоры работают быстро, поэтому ваша программа большую часть времени ничего не делает и ожидает поступления памяти.

Вместо этого используйте std::vector.Он хранит все значения один за другим, и итерация очень дешевая.Поскольку вы выполняете итерацию вперед в памяти без скачков, вы используете full кешлайн, и ваш модуль предварительной выборки сможет извлекать дополнительные страницы, прежде чем они понадобятся, потому что ваш доступ к памяти предсказуем.

Многие люди, в том числе Бьярно Страуструп, доказали, что std::vector во многих случаях быстрее, чем std::list, даже в тех случаях, когда std::list имеет "теоретически" лучшую сложность (случайная вставка, удаление,...) только потому, что кэширование очень помогает.Поэтому всегда используйте std::vector по умолчанию.И если вы думаете , связанный список будет быстрее в вашем случае, измерьте , и вы будете удивлены, что - большую часть времени - std::vector доминирует.

Редактировать: как уже отмечали другие, ваш метод поиска простых чисел не очень эффективен.Я просто немного поиграл и применил Сито Эратосфена с использованием набора битов.

constexpr int max_prime = 1000000000;
std::bitset<max_prime> *bitset = new std::bitset<max_prime>{};
// Note: Bit SET means NO prime
bitset->set(0);
bitset->set(1);

for(int i = 4; i < max_prime ; i += 2)
    bitset->set(i); // set all even numbers
int max = sqrt(max_prime);
for(int i = 3; i < max; i += 2) { // No point testing even numbers as they can't be prime
    if(!bitset->test(i)) { // If i is prime
        for(int j = i * 2; j < no_primes; j += i)
            bitset->set(j); // set all multiples of i to non-prime
    }
}

Это занимает от 4,2 до 4,5 секунд 30 секунд (не знаю почемупосле небольших модификаций он сильно изменился ... должно быть, это оптимизация, которой я больше не занимаюсь), чтобы найти все простые числа менее одного миллиарда (1 000 000 000) на моей машине.Ваш подход занял слишком много времени даже для 100 миллионов.Примерно через две минуты я отменил поиск в 1 миллиард.

Сравнение для 100 миллионов:

time taken:                63.515 seconds
time taken bitset:         1.874 seconds
No of divisions :          1975961174
No of primes found:        5761455
No of primes found bitset: 5761455

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

Answer 2

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

std::list - это связанный список. Это в основном полезно, когда вы хотите вставить или удалить элементы случайным образом (т.е. не с конца).

Для случая, когда вы добавляете только в конец списка std::list, возникают следующие проблемы:

• Итерация по списку является относительно дорогой, так как код должен следовать указателям на узлы, а затем извлекать данные
• Список использует гораздо больше памяти, каждому элементу требуется указатель на предыдущий и следующий узлы в дополнение к фактическим данным. В 64-битной системе это равно 20 байтов на элемент, а не 4 для списка int
• Поскольку элементы в списке не являются смежными в памяти, компилятор не может выполнить столько SIMD-оптимизаций, и вы будете больше страдать от промахов кэша ЦП

A std::vector решит все вышеперечисленное, так как его память является смежной, и итерация по ней - это просто случай увеличения индекса массива. Вам необходимо убедиться, что вы вызываете reserve для вашего вектора в начале с достаточно большим значением, чтобы при добавлении к вектору весь массив не копировался в новый больший массив.

Лучшая оптимизация, чем указанная выше, заключается в использовании Сита Эратосфена для вычисления ваших простых чисел. Поскольку генерация этого света требует случайного удаления (в зависимости от вашей конкретной реализации), std::list может работать лучше, чем std::vector, хотя даже в этом случае накладные расходы std::list могут не перевесить его стоимость.

Answer 3

Тест в Ideone (код OP с небольшим количеством поверхностных изменений) полностью противоречит утверждениям, сделанным в этом вопросе:

/* check_prime__list:

              time taken       No of divisions         No of primes
    10M:    0.873 seconds        286144936                664579
    20M:    2.169 seconds        721544444               1270607   */

    <b>2B:       projected time: at least 16 minutes but likely much more</b>   (*)

/* check_prime__nums:

              time taken       No of divisions         No of primes
    10M:    4.650 seconds       1746210131                664579
    20M:   12.585 seconds       4677014576               1270607   */

    <b>2B:       projected time: at least 3 hours but likely much more</b>      (*)

Я также изменил тип счетчика количества делений на long int, так как он был ограничен пределом типа данных.Таким образом, они могли неправильно истолковать , что .

Но время выполнения не было затронуто этим.Настенные часы - это настенные часы.

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

---

(*) Прогноз времени был сделан с помощью эмпирических порядков роста анализа:

100**1.32 * 2.169 / 60 = 15.8

100**1.45 * 12.585 / 3600 = 2.8

Эмпирических порядков роста, измеренных по даннымдиапазон размеров был заметно лучше для алгоритма списка, n ^1,32 против n ^1,45 для тестирования по всем числам.Это вполне ожидаемо из-за теоретической сложности, поскольку простых чисел меньше, чем все числа до n , с коэффициентом log n , для общей сложности O (n ^1,5 / log n) против O (n ^1,5 ) .Кроме того, маловероятно, что любое несоответствие реализации превзойдет фактическое алгоритмическое преимущество.