Блог

У меня есть фрагмент C ниже, который повторяет 1-50 и выводит оператор вместо числа, если элемент делится на 2 или 3. Текущее время выполнения составляет ~ 1,47 секунды. Как я могу оптимизировать эту проблему для более быстрого запуска?

 #include <iostream>

int main() {
    for (int j = 1; j <= 50; j  )
    {
        if (j % 2 == 0 amp;amp; j % 3 == 0)
        {
            std::cout << "Both" << std::endl;
        }

        else if (j % 2 == 0)
        {
            std::cout << "Two" << std::endl;
        }

        else if (j % 3 == 0)
        {
            std::cout << "Three" << std::endl;
        }

        else
        {
            std::cout << j << std::endl;
        }
    }
}
  

Вы можете изменить endl внутри цикла на "n" , а затем std::cout << std::flush; после завершения цикла. Это уменьшит количество сбросов в 50 раз.

Поскольку очистка вывода — единственная нетривиальная работа, выполняемая здесь, я ожидаю, что это сократит время выполнения на 98%. Однако я бы ожидал, что даже при 50 сбросах все равно должно быть значительно меньше секунды.

Прежде всего, не пытайтесь оптимизировать struff до того, как вам это действительно понадобится (имейте это в виду). Я действительно не верю, что выполнение этого кода занимает 1,4 секунды. Но хорошо.

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

Итак, что я сделал, так это создал функцию, оцениваемую во время компиляции, которая возвращает a const char* с текстом, если это необходимо, или с nullprt, если это не так:

 constexpr const char *type(int n) {
    if (n % 2 == 0 amp;amp; n % 3 == 0) {
        return "Both";
    }

    if (n % 2 == 0) {
        return "Two";
    }

    if (n % 3 == 0) {
        return "Three";
    }

    return nullptr;
}
  

Далее у меня есть массив со всеми необходимыми результатами:

 const int max_number = 50;
constexpr const static std::array<const char *, max_number   1> results{
    type(0),
    type(1),
    type(2),
    type(3),
    type(4),
    type(5),
    type(6),
    type(7),
    type(8),
    type(9),
    type(10),
    type(11),
    type(12),
    type(13),
    type(14),
    type(15),
    type(16),
    type(17),
    type(18),
    type(19),
    type(20),
    type(21),
    type(22),
    type(23),
    type(24),
    type(25),
    type(26),
    type(27),
    type(28),
    type(29),
    type(30),
    type(31),
    type(32),
    type(33),
    type(34),
    type(35),
    type(36),
    type(37),
    type(38),
    type(39),
    type(40),
    type(41),
    type(42),
    type(43),
    type(44),
    type(45),
    type(46),
    type(47),
    type(48),
    type(49),
    type(50)
};
  

Результатом этого является то, что когда программа скомпилирована, вы уже разделили ее на gropus. Вы можете увидеть это здесь. Результирующий ассемблер будет выглядеть примерно так:

 .L.str:
        .asciz  "Both"

.L.str.2:
        .asciz  "Two"

.L.str.3:
        .asciz  "Three"

results:
        .quad   .L.str // 0 both
        .quad   0 // 1 none
        .quad   .L.str.2 // 2 Two
        .quad   .L.str.3 // 3 Three
        .quad   .L.str.2 // 4 Two
        .quad   0  // 5 none
        .quad   .L.str // etc
        .quad   0
        // ...  and it continues for all values
  

И, наконец, во время выполнения вы просто проверяете, равно ли оно нулю или нет:

 int main() {
    Timer t{};
    for (int j = 1; j <= max_number; j  ) {
        if (results[j]) {
            cout << results[j] << 'n';
        } else {
            cout << j << 'n';
        }
    }
}
  

Результаты:

• Первоначальный способ занял от 0,05 до 0,08 миллисекунд на моей машине.
• Новый способ занял от 0,04 до 0,07 миллисекунд.

Так что да, это быстрее. Но так быстро, что это что-то изменит.

Теперь я действительно хочу прояснить этот момент. Не оптимизируйте, пока вам это не понадобится!. Вот краткое описание того, как они оба скомпилированы -O3 . Разница действительно минимальна, а код намного больше и сложнее. Предпочитаете простой способ

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

Тем не менее, вопрос заключается в том, «как улучшить», и для этого есть несколько битов:

1. включите оптимизацию -O2
2. удалить std::cout в циклах. Вместо этого создайте, например std::string , добавьте вывод к этой переменной в цикле и после цикла выведите его. Измеряйте только цикл, а не std::cout
3. используйте вложенные циклы, как предложил @MichaelDorgan.

Всего 50 итераций? Разверните его в конечный автомат (50 состояний, 1 оператор переключения, без математики). Или превратите его в единую печать предварительно вычисленных значений. Все еще не отвечает, почему программа работает так медленно, как это происходит…

Для выполнения того же кода на моей машине требуется 12-66 мс. Я думаю, что проблема заключается в вашем измерении времени. Вы можете измерить время выполнения с помощью стандартных средств C , таких как chrono библиотека:

 #include<iostream>
#include<chrono>

using namespace std;

int main() {
    using clock = chrono::high_resolution_clock;

    auto start = clock::now();

    for (int j = 1; j <= 50; j  ) {
        if (j % 2 == 0 amp;amp; j % 3 == 0) {
            cout << "Both" << endl;
        } else if (j % 2 == 0) {
            cout << "Two" << endl;
        } else if (j % 3 == 0) {
            cout << "Three" << endl;
        } else {
            cout << j << endl;
        }
    }

    auto end = clock::now();
    cout << "Total runtime: " << chrono::duration_cast<chrono::milliseconds>(end - start).count() << "ms." << endl;
}
  

Этот код измерит продолжительность фактического цикла в миллисекундах и выведет его. Он будет игнорировать любые накладные расходы на запуск, инициализацию и остановку программы и сообщит вам о фактической производительности кода, а не о производительности средств запуска процессов ОС. Бьюсь об заклад, это значительно увеличит скорость, для меня он печатает «Общее время выполнения: 4 мс». в конце.