Расширение сита эратосфенов за миллиард

Для MAX значения 1000000000 (\ $ 10 ^ 9 \ $) требуется около 45 секунд, чтобы добраться до строки, где он печатает «сделано». Как я могу ускорить это?

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

При увеличении размера MAX за пределами \ $ 10 ^ 9 \ $ дает мне исключение в строке memset(a, true, MAX);. Есть ли какой-либо предел для этой функции? Я должен использовать всю ОЗУ. Запуск этой программы занимает около 954 МБ памяти.

void sieve_of_eratosthenes(){
    bool* a;
    a = (bool*)malloc(MAX * sizeof(bool));
    memset(a, true, MAX);
    unsigned long int i = 1;
    while (i < MAX){

        while (((++i)<MAX)&&(!a[i]));

        if (2 * i >= MAX)
            break;

        for (unsigned long int k = 2 * i; k < MAX; k += i)
            if (a[k])
                a[k] = false;
    }
    std::cout << "done\n";
    for (unsigned long int i = 2; i < MAX; i++)
        if (a[i])
            std::cout << i << "\n";
    getchar(); getchar();
}
28 голосов | спросил piepi 19 SatEurope/Moscow2015-12-19T22:19:50+03:00Europe/Moscow12bEurope/MoscowSat, 19 Dec 2015 22:19:50 +0300 2015, 22:19:50

4 ответа


16

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

Сначала вы сохраняете очень много места, сохраняя только нечетные числа в сите. Единственное четное число - это номер 2. Обратите внимание, что на современном компьютере время, затрачиваемое вашим алгоритмом, примерно эквивалентно количеству данных, которые он читает и пишет, поэтому вдвое меньше необходимого времени займет половина времени. Таким образом, bool в index \ $ i \ $ представляет число \ $ 2_i + 1 \ $.

Теперь вам нужно только удалить нечетные числа. Когда вы сначала установите значение true, установите array[0] в false, так как 1 не является простым. Теперь, когда вы удаляете кратность простого p, вы знаете, что все кратные меньше \ $ p ^ 2 \ $ уже удалены, поэтому вы начинаете цикл для удаления простых чисел в \ $ p ^ 2 \ $. И вы увеличиваете на 2p за раз, потому что p*p, (p+2)*p, (p+4)*p и т. д. - нечетные кратные p. А так как первое число, которое вы удаляете, это \ $ p ^ 2 \ $, вы можете остановить цикл, ищущий простые числа, когда \ $ p ^ 2 \ $ <= MAX.

Теперь все немного сложно: вы ищете следующий простой p. Для этого вы проверяете [i], пока не найдете значение true. Индекс i сопоставляется с простым p = 2i + 1. \ $ p ^ 2 \ $ - нечетное число, а число \ $ p ^ 2 \ $ хранится в индексе j = (p^2 - 1) / 2. Таким образом, вы очищаете числа a [j], [j + p] и т. Д.

Пока это просто, теперь мы немного умнее. Ваш MAX большой, скажем \ $ 10 ^ 9 \ $. Когда вы удаляете кратные 3, вы получаете повторяющийся шаблон. Для чисел p = 1, 3, 5, 7, 9, 11, 13, 15, 17 вы получаете шаблон (true, false, true), (true, false, true), (true, false, true) и так далее. Три значения повторяются вечно. Заполните первые 15 чисел этим шаблоном, затем удалите кратные пять: From (T, F, T, T, F, T, T, F, T, T, F, T, T, F, T) после удаления кратные пять вы сохраняете (T, F, F, T, F, T, T, F, T, T, F, T, F, F, T). Этот образец пятнадцати болтов повторится навсегда. Вы делаете 7 копий, давая 105 номеров и удаляя кратные 7. Вы делаете 11 копий, давая 1155 номеров и удаляете кратность 11. Вы делаете 13 копий, давая 15 015 номеров и удаляете кратные 13. Вы можете сделать 17 копий, давая 255 255 номеров и убрать множители 17. Это очень быстро, потому что у вас не было миллиарда чисел, всего несколько сотен тысяч. Когда вы закончите, вы дублируете данные во весь массив с помощью memcpy. Для последней части вам нужно следить за тем, чтобы не перезаписывать конец массива. Это было всего шесть номеров, но эти 6 номеров составляют очень важную часть работы!

Для других простых чисел вы удалите все их нечетные кратные. Мы можем сделать это быстрее. Возьмите p = 101. Вы удалите 101p, 103p, 105p, 107p и так далее. Но 105p делится на 3, поэтому он уже удален. То же самое для 111p и так далее. Итак, вот что вы делаете: вы удаляете \ $ p ^ 2 \ $. Если p+2 не делится на 3, вы также удаляете (p+2)*p. Следующий номер, который вы попытаетесь удалить, будет кратным 3. Поэтому вместо увеличения числа, которое вы удаляете на 2p каждый раз, вы увеличиваете на 4p (избегая кратного 3), затем на 2p, затем снова на 4p, 2p , 4p, 2p и так далее. Это экономит одну треть работы.

Еще одно улучшение: вместо того, чтобы использовать один байт для хранения каждого номера, вы используете только один бит. Это означает, что вам нужно выполнить операции переключения для доступа к каждому биту, но объем используемой памяти сокращается в 1 раз. Это позволяет обрабатывать гораздо большие числа, и меньше памяти будет работать быстрее.

И последний, большой: оптимизируйте доступ к памяти. Допустим, у вас MAX = 1 миллиард, и используйте один бит на нечетное число = 62,5 мегабайта. Это больше, чем вписывается в кеш процессора. Допустим, у вас есть 2MB L3 cache = 32 миллиона номеров. В этом случае вы полностью выполняете операцию сита для первых 32 миллионов номеров. Это будет работать намного быстрее, потому что ваши данные находятся в кеше L3. Допустим, у вас есть кеш L2 256 КБ = 4 миллионаномера. В этом случае вы полностью выполняете операцию решета для первых 4 миллионов номеров, затем следующие четыре миллиона и так далее. Это еще быстрее, потому что теперь все данные, которые вы используете, находятся в кэше L2 и могут быть быстро прочитаны /записаны.

ответил gnasher729 20 SunEurope/Moscow2015-12-20T02:35:41+03:00Europe/Moscow12bEurope/MoscowSun, 20 Dec 2015 02:35:41 +0300 2015, 02:35:41
27

Несколько вещей, которые вы можете сделать:

  • Используйте бит-бит (с манипуляцией бит) вместо массива bool. Это дает вам в 8 раз больше памяти. Если вы используете C ++ vector< bool>, вы получаете эту оптимизацию бесплатно.

  • Сохранять только нечетные числа в массиве. Это позволит сэкономить дополнительный коэффициент 2 в памяти. Вам нужно немного адаптировать логику программы, но это не очень сложно. Это экономит также некоторое время, потому что на первой итерации алгоритмы просто отмечают половину чисел.

  • Внешний цикл (while (i < MAX)) должен выполняться только от 0 до ceil(sqrt(MAX)).

  • Внутренний цикл может начинаться с i*i не только 2*i.

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

Segfault, скорее всего, связано с тем, что a == NULL, то есть подпрограмма malloc не может выделить память. Вам нужно проверить NULL после вызова malloc и до memset.

ответил Andreas H. 19 SatEurope/Moscow2015-12-19T22:52:03+03:00Europe/Moscow12bEurope/MoscowSat, 19 Dec 2015 22:52:03 +0300 2015, 22:52:03
8

Хотя лучше использовать классы контейнеров в C ++ вместо выделения памяти вручную, я все же укажу на это, так как все равно нужно сказать:

a = (bool*)malloc(MAX * sizeof(bool));

В C ++ лучше использовать new вместо malloc(). Это также позволит избежать необходимости в таком акте, который требуется на C ++ не в C.

Вы также можете инициализировать a вместо того, чтобы сначала объявить его, а затем назначить ему.

bool* a = new bool[MAX];

Но вы все равно должны использовать класс контейнера, как упоминалось в @Andreas H. Plus, вы никогда не использовали free() здесь, поэтому эта функция вызовет утечку памяти.

ответил Jamal 20 SunEurope/Moscow2015-12-20T01:00:46+03:00Europe/Moscow12bEurope/MoscowSun, 20 Dec 2015 01:00:46 +0300 2015, 01:00:46
0

Есть ли причина, по которой вам нужно использовать сито? Я не пробовал это с подходами к упаковке, предлагаемыми для сокращения использования памяти, но простой тест на все до квадратного корневого маршрута сдувает реализацию сита, который вы используете. Как только вы начнете вызывать кеш-пропуски производительности Sieve nosedives и даже с бит-упаковкой, вы не сможете сохранить его в кэше L1.

ответил Loren Pechtel 20 SunEurope/Moscow2015-12-20T07:18:12+03:00Europe/Moscow12bEurope/MoscowSun, 20 Dec 2015 07:18:12 +0300 2015, 07:18:12

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132