Скорость работы алгоритмов / Нахождение простых чисел (C++)

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

Технические подробности проведения тестов
Код программы-оболочки, замеряющей скорость алгоритмов (язык C++)

 

Важные замечания.

Первое.
Если создавать массив постредством простого объявления int ar[SIZE] , то его размер будет ограничен 250 000 ячеек (для int). Если используем более сложный путь
int *ar = new int[SIZE];
...
delete[] ar;
   //не забываем удалять
то тогда смотрим, какая у нас разрядность системы. Для 32-битной системы размер массива ограничен величиной адрессного пространства и теоретически составляет 2Гб (иначе выскочит ошибка C2148). На практике ещё меньше. В случае 64-битных систем мы в размере массива де-факто не ограничены. В экспериментальных целях был создан и безо всяких проблем начал обрабатываться массив из 5 миллиардов ячеек типа int при том, что на компьютере было всего 16 Гб оперативной памяти (система использовала файл кодкачки).

Второе.
При тестировании алгоритмов важно, чтобы в их процессе промежуточная информация не выводилась на экран или в другое место. Вывод информации является времязатратным процессом, имеющим свои особенности и подверженным сильному влиянию помех. Данный факт нам стал понятен не сразу. При первой версии исследования алгоритмы выводили найденные числа в консоль. В результате полученные замеры времени имели большой разброс и был сделан ряд выводов, которые, как потом выяснилось, оказались неточными. См. предыдущую версию статьи. Если вывод в консоль убрать, то замеры возвращают стабильные цифры. Можете пронаблюдать это ниже.

Третье. (P.S.)
Функции push_back и resize имеют разное быстродействие для разных компиляторов. Так что результаты и выводы относятся только к тем условиям, в которых произведены измерения.

Тестируемые аглоритмы, измеренное время и сделанные вывыды:

Базовый алгоритм (для дальнейших сравнений)

    for (i = 2; i <= NL; i++) {
        for (j = 2; j <= i && i%j != 0; j++) {
        }
        if (j == i)

            primeNumbers.push_back(i);
    }

//  250 000 чисел -  5.691,  5.684 сек

//  500 000 чисел - 21.492, 21.493 сек
//1 000 000 чисел - 81.366, 81.364 сек

Операция вывода значений перенесена внутрь цикла

    for (i = 2; i <= NL; i++)
        for (j = 2; j <= i; j++)
            if (!(i%j)) {
                if (j == i)
                    primeNumbers.push_back(i);
                break;
            }

//  250 000 чисел -  5.686,  5.690 сек

//  500 000 чисел - 21.494, 21.488 сек
//1 000 000 чисел - 81.355, 81.356 сек

Базовый алгоритм с перебором до корня

    for (i = 2; i <= NL; i++) {
        for (j = 2; j*j <= i && i%j != 0; j++) {
        }
        if (j*j > i)
            primeNumbers.push_back(i);
    }

//  250 000 чисел -  0.022,  0.023 сек

//  500 000 чисел -  0.059,  0.061 сек
//1 000 000 чисел -  0.152,  0.153 сек

Перебор до корня и операция вывода перенесена внутрь цикла, использование GOTO

    for (i = 2; i <= NL; i++) {
        for (j = 2; j*j <= i; j++) {
            if (i%j == 0)
                goto CYCLE_END;
        }
        primeNumbers.push_back(i);
        CYCLE_END: ;
    }

//  250 000 чисел -  0.023,  0.023 сек

//  500 000 чисел -  0.063,  0.059 сек
//1 000 000 чисел -  0.153,  0.152 сек

1.
Во многих случаях можно уменьшить суммарное количество операций, производимых в цикле for (…;…;…), прописав внутри цикла дополнительные условия с break, continue и goto. Но как показывают измерения скорости (не только приведённые выше, но и другие), подобные усложнения в подавляющем большинстве случаев прибавки к скорости не дают. А иногда могут даже, наоборот, немного замедлить программу. Не мудрите с этими дополнительными операторами без особой надобности.

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

Проход лишь по нечётным числам во внешнем цикле

    primeNumbers.push_back(2);
    for (i = 3; i <= NL; i+=2) {
        for (j = 2; j <= i && i%j != 0; j++) {
        }
        if (j == i)
            primeNumbers.push_back(i);
    }

//  250 000 чисел -  5.685,  5.694 сек

//  500 000 чисел - 21.490, 21.490 сек
//1 000 000 чисел - 81.365, 81.374 сек

Проход лишь по нечётным числам в обоих циклах

    primeNumbers.push_back(2);
    for (i = 3; i <= NL; i+=2) {
        for (j = 3; j <= i && i%j != 0; j+=2) {
        }
        if (j == i)
            primeNumbers.push_back(i);
    }

//  250 000 чисел -  2.845,  2.846 сек

//  500 000 чисел - 10.742, 10.749 сек
//1 000 000 чисел - 40.698, 40.688 сек

Проход лишь по нечётным числам во внешнем цикле с перебором до корня

    primeNumbers.push_back(2);
    for (i = 3; i <= NL; i += 2) {
        for (j = 2; j*j <= i && i%j != 0; j++) {
        }
        if (j*j > i)
            primeNumbers.push_back(i);
    }

//  250 000 чисел -  0.023,  0.022 сек

//  500 000 чисел -  0.060,  0.059 сек
//1 000 000 чисел -  0.152,  0.152 сек

Проход лишь по нечётным числам в обоих циклах с перебором до корня

    primeNumbers.push_back(2);
    for (i = 3; i <= NL; i += 2) {
        for (j = 3; j*j <= i && i%j != 0; j+=2) {
        }
        if (j*j > i)
            primeNumbers.push_back(i);
    }

//  250 000 чисел -  0.013,  0.013 сек

//  500 000 чисел -  0.032,  0.032 сек
//1 000 000 чисел -  0.080,  0.080 сек

2.
Операция i++ (инкремент) выполняется быстрее, чем i+=2. Замена цикла for (…;…;i++), где каждый второй цикл с ходу пропускается после проверки некоторого простого условия, на более сложный for (…;…;i+=2) во многих случаях вам никакой выгоды не даст.

Какие-то особенности обработки операции внутри процессора.
(См. также нижеприведённые тесты с разновидностями решета Эратосфена.)

С использованием ранее найденных простых чисел
(динамического массив, увеличивающийся посредством .push_back(n) )

    int t_lng = 0;

    for (i = 2; i <= NL; i++) {
        for (j = 0; j < t_lng && i%primeNumbers[j] != 0; j++) {
        }
        if (j >= t_lng) {
            primeNumbers.push_back(i);
            t_lng++;

        }
    }

//  250 000 чисел -  0.532,  0.531 сек

//  500 000 чисел -  1.878,  1.880 сек
//1 000 000 чисел -  6.699,  6.691 сек

С использованием ранее найденных простых чисел
(динамический массив, увеличивающегося скачкообразно, с шагом 100)

    primeNumbers.resize(100);
    primeNumbers[0] = 2;
    int t_max = 100;
    int t_lng = 1;

    for (i = 3; i <= NL; i++) {
        for (j = 0; j < t_lng && i%primeNumbers[j] != 0; j++) {
        }
        if (j >= t_lng) {
            if (t_lng >= t_max) {
                t_max += 100;
                primeNumbers.resize(t_max);
            }
            primeNumbers[t_lng] = i;
            t_lng++;
        }
    }


    primeNumbers.resize(t_lng);
//  250 000 чисел -  0.531,  0.531 сек

//  500 000 чисел -  1.883,  1.877 сек
//1 000 000 чисел -  6.693,  6.688 сек

С использованием ранее найденных простых чисел
(динамический массив, увеличивающегося скачкообразно, с шагом 1000)

    primeNumbers.resize(1000);
    primeNumbers[0] = 2;
    int t_max = 1000;
    int t_lng = 1;

    for (i = 3; i <= NL; i++) {
        for (j = 0; j < t_lng && i%primeNumbers[j] != 0; j++) {
        }
        if (j >= t_lng) {
            if (t_lng >= t_max) {
                t_max += 1000;
                primeNumbers.resize(t_max);
            }
            primeNumbers[t_lng] = i;
            t_lng++;
        }
    }


    primeNumbers.resize(t_lng);
//  250 000 чисел -  0.530,  0.531 сек

//  500 000 чисел -  1.881,  1.882 сек
//1 000 000 чисел -  6.694,  6.690 сек

3.
(Выводы сделаны не только на основе вышеприведённых измерениях, но и на других наблюдениях.)
Динамические массивы являются относительно медленными конструкциями языка. Это неповоротливые монстры, которые следует использовать только там, где они действительно нужны. Порой они могут заметно ускорить алгоритм в целом, но при этом иногда несколько простых циклов выполнятся быстрее, чем один, связанный с изменением размера динамического массива.

Увеличение длины операцией .push_back(n) происходит многократно быстрее, чем через операцию .resize(новая_длина). Однако в некоторых случаях замена большого количества push_back на один resize может быть оправдана.

Если всё же используете resize, то увеличение шага его приращения (к примеру, со 100 до 1000, как в нашем примере) совсем не обязательно приводит к ускорению работы алгоритма.

 

Решето Эратосфена

    int *ar = new int[NL+1]{};
    for (i = 2; i*i <= NL; i++)
        if (ar[i] == 0)
            for (j = i*i; j <= NL; j += i)
                ar[j] = 1;

    for (i=2; i<=NL; i++)
        if(ar[i]==0)
            primeNumbers.push_back(i);

    delete[] ar;

//      250 000 чисел -  0.001,  0.001 сек

//      500 000 чисел -  0.002,  0.003 сек
//    1 000 000 чисел -  0.006,  0.007 сек
//   10 000 000 чисел -  0.108,  0.108 сек
//  100 000 000 чисел -  1.202,  1.215 сек
//1 000 000 000 чисел - 13.933, 13.958 сек

Решето Эратосфена с проходом только по нечётным числам

    int *ar = new int[NL+1]{};
    ar[2] = 1;
    for (i=3; i*i<=NL; i+=2)
        if (ar[i] == 0)
            for (j = i*i; j <= NL; j += i)
                ar[j] = 1;

    primeNumbers.push_back(2);
    for (i=3; i<=NL; i+=2)
        if(ar[i]==0)
            
primeNumbers.push_back(i);

    delete[] ar;
//    1 000 000 чисел -  0.007,  0.007 сек
//   10 000 000 чисел -  0.103,  0.102 сек
//  100 000 000 чисел -  1.146,  1.153 сек
//1 000 000 000 чисел - 13.315, 13.344 сек

Решето Эратосфена с заменой int на int unsigned

    int unsigned *ar = new int unsigned[NL+1]{};
    for (i = 2; i*i <= NL; i++)
        if (ar[i] == 0)
            for (j = i*i; j <= NL; j += i)
                ar[j] = 1;

    for (i = 2; i <= NL; i++)
        if (ar[i] == 0)
            primeNumbers.push_back(i);


    delete[] ar;
//    1 000 000 чисел -  0.006,  0.007 сек
//   10 000 000 чисел -  0.108,  0.107 сек
//  100 000 000 чисел -  1.206,  1.214 сек
//1 000 000 000 чисел - 13.959, 13.981 сек

Решето Эратосфена с заменой int на short

    short *ar = new short[NL+1]{};
    for (i = 2; i*i <= NL; i++)
        if (ar[i] == 0)
            for (j = i*i; j <= NL; j += i)
                ar[j] = 1;

    for (i = 2; i <= NL; i++)
        if (ar[i] == 0)
            primeNumbers.push_back(i);


    delete[] ar;
//    1 000 000 чисел -  0.004,  0.004 сек
//   10 000 000 чисел -  0.084,  0.084 сек
//  100 000 000 чисел -  0.986,  0.991 сек
//1 000 000 000 чисел - 11.100, 11.134 сек

Решето Эратосфена с заменой int на short unsigned

    short unsigned *ar = new short unsigned[NL+1]{};
    for (i = 2; i*i <= NL; i++)
        if (ar[i] == 0)
            for (j = i*i; j <= NL; j += i)
                ar[j] = 1;

    for (i = 2; i <= NL; i++)
        if (ar[i] == 0)
            primeNumbers.push_back(i);


    delete[] ar;
//    1 000 000 чисел -  0.004,  0.005 сек
//   10 000 000 чисел -  0.085,  0.089 сек
//  100 000 000 чисел -  0.989,  0.986 сек
//1 000 000 000 чисел - 11.090, 11.147 сек

Решето Эратосфена с заменой int на char

    char *ar = new char[NL+1]{};
    for (i = 2; i*i <= NL; i++)
        if (ar[i] == 0)
            for (j = i*i; j <= NL; j += i)
                ar[j] = 1;

    for (i = 2; i <= NL; i++)
        if (ar[i] == 0)
            primeNumbers.push_back(i);


    delete[] ar;
//    1 000 000 чисел -  0.004,  0.004 сек
//   10 000 000 чисел -  0.067,  0.066 сек
//  100 000 000 чисел -  0.844,  0.849 сек
//1 000 000 000 чисел -  9.408,  9.427 сек

Решето Эратосфена с заменой int на char unsigned

    char unsigned *ar = new char unsigned[NL+1]{};
    for (i = 2; i*i <= NL; i++)
        if (ar[i] == 0)
            for (j = i*i; j <= NL; j += i)
                ar[j] = 1;

    for (i = 2; i <= NL; i++)
        if (ar[i] == 0)
            primeNumbers.push_back(i);


    delete[] ar;
//    1 000 000 чисел -  0.005,  0.004 сек
//   10 000 000 чисел -  0.067,  0.066 сек
//  100 000 000 чисел -  0.843,  0.845 сек
//1 000 000 000 чисел -  9.425,  9.434 сек

Решето Эратосфена с заменой int на bool

    bool *ar = new bool[NL+1]{};
    for (i = 2; i*i <= NL; i++)
        if (!ar[i])
            for (j = i*i; j <= NL; j += i)
                ar[j] = true;

    for (i = 2; i <= NL; i++)
        if (!ar[i])
            primeNumbers.push_back(i);


    delete[] ar;
//    1 000 000 чисел -  0.004,  0.003 сек
//   10 000 000 чисел -  0.066,  0.066 сек
//  100 000 000 чисел -  0.850,  0.850 сек
//1 000 000 000 чисел -  9.441,  9.449 сек

//Вследствие обнаруженного в исходном коде недочёта тест был проведён позднее. Хотя условия тестирования были идентичными, к данным результатам следует относиться осторожно.

Решето Эратосфена с заменой int на bool и с проходом только по нечётным числам

    bool *ar = new bool[NL+1]{};
    ar[2] = true;
    for (i=3; i*i<=NL; i+=2)
        if (!ar[i])
            for (j = i*i; j <= NL; j += i)
                ar[j] = true;

    primeNumbers.push_back(2);
    for (i=3; i<=NL; i+=2)
        if(!ar[i])
            primeNumbers.push_back(i);


    delete[] ar;
//    1 000 000 чисел -  0.003,  0.003 сек
//   10 000 000 чисел -  0.060,  0.060 сек
//  100 000 000 чисел -  0.789,  0.788 сек
//1 000 000 000 чисел -  8.809,  8.815 сек

4.
Если сравнивать int, short, char с парными им unsigned, то никаких существенных разниц в скорости на этапе их массовой обработки не обнаружено. Однако как показывают ранее проведённые тесты (см. предыдущую версию статьи), в случае unsigned наблюдается небольшое замедление, если требуется массовый вывод значений на экран. Можно сделать предположение, что это связано с тем, что компьютеру приходится выполнять дополнительные преобразования типов, когда имеет место взаимодействие unsigned и signed.

Так что несмотря на то, что на  unsigned сами по себе настолько же быстры, как signed, не стоит использовать их там, где в них нет необходимости.

5.
Если сравнивать скорости обработки int, short, char и bool, то на этапе самой обработки всё почти как ожидаемо. Чем меньше байт занимает переменная, тем быстрее она обрабатывается. В приведённых тестех самую медленную скорость показал 4-битный int, самую быструю - однобитные char и bool. Скорости char и bool практически одинаковы.

Однако есть и обратная сторона. Как показывают ранее проведённые тесты (см. предыдущую версию статьи), в случае необходимости массового вывода на экран картина меняется: short и char ведут себя медленнее, чем int. И bool тоже притормаживает. По всей видимости это связано с необходимостью дополнительного преобразования типов.

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

 

Так какой же алгоритм нахождения простых чисел самый эффективный

 

 

Выше перечисленные выводы являются техническими. На их основе можно сделать несколько общих философских заключений:
 • Уменьшение количества операций не всегда ускоряет алгоритм.
 • Чем более "крутые" конструкции языка вы применяете, тем медленнее они работают.
 • Знание принципов работы компьютерного железа может ускорить ваши алгоритмы, даже если используете языки высокого уровня.

 


P.S.
Другие рекомендации по написанию эффективного кода на С++ можно найти в нашей следующей статье "
Сортировка больших массивов случайных чисел"
 

Add new comment

Plain text

  • No HTML tags allowed.
  • Lines and paragraphs break automatically.
  • Web page addresses and email addresses turn into links automatically.