Исследование скорости работы алгоритмов (C++) (архив)

Это старая версия статьи. Новую смотрите здесь.

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

======
Это не полноценная исследовательская статья, а удовлетворение личного любопытства. Целью было взять различные алгоритмы по нахождению простых чисел в заданном диапазоне, поиграть с ними и посмотреть, насколько ожидания совпадают с практикой. И как показали наблюдение, не всегда уменьшение количества операций приводит к ускорению работы программы. Также стали понятны некоторые смежные моменты.

Скорость работы алгоритма невозможно измерить на практике абсолютно точно. На неё влияет тип и версия компилятора, компьютерное железо, соседствующее программное обеспечение и периодически происходящие внутри системы процессы, над которыми пользователь не имеет контроля. Один и тот же тест, дважды запущенный на одном и том же компьютере с разницей несколько секунд при никак не изменившемся внешнем окружении, иногда удивляет разницей в скорости более чем в два раза. (P.S. Не совсем так. Большой разброс в полученных значениях был связан с тем, что промежуточная информация выводилась наружу.) Чтобы как-то усреднить цифры, была написана программа-оболочка, запускающая тест несколько раз и подсчитывающая средний результат.

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

 

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

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

    for (i = 2; i <= NL; i++) {
        for (j = 2; j <= i && i%j != 0; j++) {
        }
        if (j == i)
            cout << ++count << ":\t" << i << "\n";
    }

//150 000 чисел - 4.642, 5.121 сек
//250 000 чисел - 12.430, 10.162 сек

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

    for (i = 2; i <= NL; i++)
        for (j = 2; j <= i; j++)
            if (!(i%j)) {
                if (j == i)
                    cout << ++count << ":\t" << i << "\n";
                break;
            }

//150 000 чисел - 6.267, 5.238 сек
//250 000 чисел - 12.808, 10.137 сек

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

    for (i = 2; i <= NL; i++) {
        for (j = 2; j*j <= i && i%j != 0; j++) {
        }
        if (j*j > i)
            cout << ++count << ":\t" << i << "\n";
    }

//150 000 чисел - 3.555, 3.857 сек
//250 000 чисел - 7.189, 6.727 сек

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

    for (i = 2; i <= NL; i++) {
        for (j = 2; j*j <= i; j++) {
            if (i%j == 0)
                goto CYCLE_END;
        }
        cout << ++count << ":\t" << i << "\n";
        CYCLE_END: ;
    }

//150 000 чисел - 4.323, 4.013 сек
//250 000 чисел - 7.244, 5.654 сек

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

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

    cout << ++count << ":\t" << 2 << "\n";
    for (i = 3; i <= NL; i+=2) {
        for (j = 2; j <= i && i%j != 0; j++) {
        }
        if (j == i)
            cout << ++count << ":\t" << i << "\n";
    }

//150 000 чисел - 5.151, 6.305 сек
//250 000 чисел - 12.802, 12.298 сек

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

    cout << ++count << ":\t" << 2 << "\n";
    for (i = 3; i <= NL; i+=2) {
        for (j = 3; j <= i && i%j != 0; j+=2) {
        }
        if (j == i)
            cout << ++count << ":\t" << i << "\n";
    }

//150 000 чисел - 5.391, 3.751 сек
//250 000 чисел - 10.003, 7.223 сек

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

    cout << ++count << ":\t" << 2 << "\n";
    for (i = 3; i <= NL; i += 2) {
        for (j = 2; j*j <= i && i%j != 0; j++) {
        }
        if (j*j > i)
            cout << ++count << ":\t" << i << "\n";
    }

//150 000 чисел - 4.376, 3.016 сек
//250 000 чисел - 7.151, 6.827 сек

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

    cout << ++count << ":\t" << 2 << "\n";
    for (i = 3; i <= NL; i += 2) {
        for (j = 3; j*j <= i && i%j != 0; j+=2) {
        }
        if (j*j > i)
            cout << ++count << ":\t" << i << "\n";
    }

//150 000 чисел - 4.160, 2.979 сек
//250 000 чисел - 6.055, 6.754 сек

2.
Операция i++ выполняется быстрее, чем i+=2. Какие-то особенности работы регистров процессора. Замена цикла for (…;…;i++), где каждый второй цикл с ходу пропускается после проверки некоторого простого условия, на for (…;…;i+=2) в некоторых случаях, вопреки ожиданиям, может не ускорить работу программы, а наоборот, замедлить её. (P.S. Стоит думать, что небольшое замедление работы некоторых алгоритмов при использовании i+=2 заместо i++ было связано с особенностями вывода информации в консоль. В общем случае циклы с i+=2 просто "не быстрее". Но это лишь небольшое уточнение, а в целом вывод верный.)
(См. также нижеприведённые тесты с разновидностями решета Эратосфена. Кроме этих замеров были проведены ещё пара других подобных, также подтверждающих закономерность.)

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

    vector<int> primeNumbers = { 2 };  //#include <vector>
    int t_lng = primeNumbers.size();

    cout << ++count << ":\t" << 2 << "\n";
    for (i = 3; i <= NL; i++) {
        for (j = 0; j < t_lng && i%primeNumbers[j] != 0; j++) {
        }
        if (j >= t_lng) {
            primeNumbers.push_back(i);
            t_lng++;
            cout << ++count << ":\t" << i << "\n";
        }
    }

//150 000 чисел - 3.759, 3.338 сек
//250 000 чисел - 7.103, 7.273 сек

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

    vector<int> primeNumbers;  //#include <vector>
    primeNumbers.resize(100);
    primeNumbers[0] = 2;
    int t_max = 100;
    int t_lng = 1;

    cout << ++count << ":\t" << 2 << "\n";
    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++;
            cout << ++count << ":\t" << i << "\n";
        }
    }

//150 000 чисел - 4.144, 4.162 сек
//250 000 чисел - 7.169, 7.212 сек

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

    vector<int> primeNumbers;  //#include <vector>
    primeNumbers.resize(1000);
    primeNumbers[0] = 2;
    int t_max = 1000;
    int t_lng = 1;

    cout << ++count << ":\t" << 2 << "\n";
    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++;
            cout << ++count << ":\t" << i << "\n";
        }
    }

//150 000 чисел - 2.657, 3.610 сек
//250 000 чисел - 4.017, 7.164 сек

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

Использование динамических массивов (std::vector), длина которых постоянно изменяется, времязатратно по сравнению с простыми циклами. В некоторых случаях несколько простых циклов выполнятся быстрее, чем всего один, связанный с изменением длины массива.

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

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

 

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

    int ar[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)
            cout << ++count << ":\t" << i << "\n";

//150 000 чисел - 3.049, 2.761 сек
//250 000 чисел - 5.233, 4.517 сек

 

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

    int ar[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;

    cout << ++count << ":\t" << 2 << "\n";
    for (i=3; i<=NL; i+=2)
        if(ar[i]==0)
            cout << ++count << ":\t" << i <<
"\n";
//150 000 чисел - 3.392, 3.240 сек
//250 000 чисел - 5.630, 5.236 сек

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

    int unsigned ar[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)
            cout << ++count << ":\t" << i << "\n";

//150 000 чисел - 3.757, 4.673 сек
//250 000 чисел - 6.618, 7.135 сек

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

    short ar[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)
            cout << ++count << ":\t" << i << "\n";

//150 000 чисел - 3.998, 4.735 сек
//250 000 чисел - 4.261, 7.859 сек

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

    short unsigned ar[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)
            cout << ++count << ":\t" << i << "\n";

//150 000 чисел - 4.632, 4.358 сек
//250 000 чисел - 8.340, 6.124 сек

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

    char ar[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)
            cout << ++count << ":\t" << i << "\n";

//150 000 чисел - 2.717, 4.279 сек
//250 000 чисел - 6.697, 7.087 сек

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

    char unsigned ar[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)
            cout << ++count << ":\t" << i << "\n";

//150 000 чисел - 5.010, 4.465 сек
//250 000 чисел - 7.845, 5.195 сек

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

    bool ar[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])
            cout << ++count << ":\t" << i << "\n";

//150 000 чисел - 3.774, 2.685 сек
//250 000 чисел - 6.340, 6.273 сек

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

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

    bool ar[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;

    cout << ++count << ":\t" << 2 << "\n";
    for (i=3; i<=NL; i+=2)
        if(!ar[i])
            cout << ++count << ":\t" << i << "\n";

//150 000 чисел - 4.379, 2.959 сек
//250 000 чисел - 5.898, 6.919 сек

4.
При замене типов int, short и char на смежные с ними unsigned в большинстве случаев было замечено небольшое замедление быстродействия. Хотя результаты некоторых одиночных тестов показывают противоположный результат.

Замена типа int на short, char позволяет сэкономить память. Но вот в плане скорости при этом, вопреки ожиданиям многих, наблюдается некоторое замедление. По всей видимости процессоры или ОС оптимизированы для работы с int. Именно с int, а не с int unsigned.

И быстрее всего этот вывод можно расширить даже на bool. Для более чёткого утверждения данных не достаточно, но как мимимум, выгоды в в быстродействии при замене int на bool в данном контексте нет.

(P.S. Как стало понятно в ходе дальнейших разбирательств, эти выводы была ошибочными. Причиной тому было то, что промежуточные результаты выводились в консоль, в связи с чем происходило дополнительное преобразование типов и на этом терялась скорость. См. более новую версию статьи.)

 

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

 

 

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

 

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

Чтобы в момент объявления массива сразу проинициализировать его нулями, используйте {}, иначе там будут случайные числа.

 

В связи с накопившимся опытом тестирование стоит переделать.

Add new comment

Plain text

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