4

Объясните, пожалуйста, почему этот код:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<long long> in;
    for(size_t i = 0; i < n; i++)
    {
        int j;
        cin >> j;
        in.push_back(j);
        if(in[i] != in[i - 1])
        {
            cout << in[i] << '\n';
        }
    }
}

работает дольше, чем этот:

using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<long long> out;
    vector<long long> in;
    for(size_t i = 0; i < n; i++)
    {
        int j;
        cin >> j;
        in.push_back(j);
    }
    for(size_t i = 0; i < n; i++)
    {
        if(in[i] != in[i - 1])
        {
            cout << in[i] << '\n';
        }
    }
}

Ведь по идее должно быть наоборот, потому что в первом коде мы используем только один вектор и один цикл for, а во втором два вектора и два цикла for. Заранее спасибо за ответ.

4
  • а как вы измеряли время? если разница небольшая, то скажу я вам, что разница во времени работы довольна интересная величина, которая может варьироваться не только из-за кода самой программы, но и других различных факторов 23 янв 2021 в 3:33
  • @VladislavTikhomirov, есть подозрение, что этот вопрос поинтереснее и разница там существенная.
    – Qwertiy
    23 янв 2021 в 3:47
  • @VladislavTikhomirov разница довольна существенная, порядка 250 мс, при том, что занятая память примерно одинакова.
    – prostak
    23 янв 2021 в 4:03
  • 1
    В обеих случаях вы выходите за пределы вектора при первом сравнении. Компилятор может пропустить это каким то образом, но и для этого время может быть потрачена. А второй раз он уже понимает, что вы игнорируете ошибку и оптимизацию, и сам может вместо вас это сделать. Во вторых вы не знаете что делает в это время операционная система, которая работает не зависимо от вашего кода. Так что эта доля секунды зависит от компилятора и ОС. Лично у меня на данный момент, с конкретным компилятором получается обратный результат 23 янв 2021 в 7:11

3 ответа 3

7

Предполагаю, что наблюдаемая вами разница в скорости работы потоков ввода/вывода связана с буферизацией.

Стандартный объект вывода std::cout привязан к стандартному объекту ввода std::cin. Это означает, что перед любой операцией ввода объект std::cin вызывает std::cout.flush(). Вот что пишет cppreference.com:

Once initialized, std::cout is tie()'d to std::cin and std::wcout is tie()'d to std::wcin, meaning that any input operation on std::cin executes std::cout.flush() (via std::basic_istream::sentry's constructor).

В вашем первом примере кода внутренний буфер std::cout работает не очень эффективно: только объект std::cout положит очередную порцию данных в свой внутренний буфер, как std::cin даёт команду опустошить его — отправить содержимое буфера во внешнее окружение.
Во втором примере кода std::cin также на каждой итерации цикла пытается опустошить буфер вывода, но так как он пуст (вывод происходит в другом цикле) — это не создаёт проблем с производительностью.

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

Если перенаправить стандартные потоки ввода вывода в файлы, то наблюдаемое вами поведение вроде бы не сложно повторить.

Сгенерируем текстовый файл "1.txt", хранящий 20'000'000 целых чисел из отрезка [0; 9]. Код генерации:

std::ofstream fout("1.txt", std::ios_base::out | std::ios_base::binary);
std::mt19937 mt;

const long data_size = 20'000'000;

char buf[] = {0, ' '};
for (long i = 0; i < data_size; ++i)
{
    buf[0] = "0123456789"[mt() % 10];
    fout.write(buf, sizeof(buf));
}
fout.close();

А теперь прочитаем его, записывая некоторые прочитанные числа в другой файл (немного изменённый ваш код):

//std::cin.tie(nullptr);
long long num_old = 0;
while (true)
{
    long long num_cur;
    std::cin >> num_cur;
    if (std::cin.fail())
        break;

    if ( num_cur != num_old )
        std::cout << num_cur << '\n';
    num_old = num_cur;
}

На моей системе приведённая программа выполнилась за 58 секунд. После отвязывания выходного потока от входного с помощью метода tie() (раскомментировав строку std::cin.tie(nullptr);) программа стала выполняться 24 секунды.

Теперь, оставив потоки связанными, разделим ввод данных и вывод:

std::vector <long long> vect;
long long num_old = 0;
while (true)
{
    long long num_cur;
    std::cin >> num_cur;
    if (std::cin.fail())
        break;

    if ( num_cur != num_old )
        vect.push_back(num_cur);
    num_old = num_cur;
}
for (std::size_t i = 0; i < vect.size(); ++i)
    std::cout << vect[i] << '\n';

Данная программа выполнилась на моей системе за 25 секунд.


но почему во втором примере буфер вывода пуст? мы же его наполняем содержимым in[i], точно так же, как и в первом примере

Да, наполняем, но во втором варианте вашего кода наполнение происходит после того как все данные считанны. Это означает что std::cin не вмешивается в работу буфера std::cout. (Точнее говоря вмешивается, но на момент вмешательства внутренний буфер std::cout пуст.) Таким образом буфер std::cout опустошается по мере заполнения, а не принудительно на каждой итерации цикла. На практике опустошение буфера означает обращение к ресурсоёмким функциям ОС, которые отображают содержимое буфера на экране или пишут в файл. И чем реже происходит обращение к этим функциям, тем лучше для производительности.

Ещё один пример:

std::ofstream f("out.txt");

for (long i = 0; i < 10'000'000; ++i)
{
    //f.flush(); // <- Раскомментируем данную строку.
    f << '*';
}

В приведённом коде на каждой итерации в файловый поток выводится символ '*', но непосредственная запись звёздочек в файл на диск происходит далеко не на каждой итерации цикла. Поток буферизует вывод. Он накапливает символы во вспомогательном внутреннем буфере в оперативной памяти. И только когда буфер заполняется, поток вызывает необходимые функции операционной системы, и происходит запись содержимого внутреннего буфера — сразу множество символов пишутся в файл одной большой группой. Приведённый код у меня работает меньше одной секунды.

Но стоит только добавить принудительное опустошение буфера на каждой итерации цикла: f.flush();, как время работы резко возрастает. Теперь на моей системе на генерацию файла понадобилось больше 16 секунд! Вместо того, чтобы писать данные в файл крупными блоками, теперь поток пишет по одному симолу, что занимает уйму времени.

В вашем первом примере кода нет явного вызова std::cout.flush(), но есть неявный — на каждой итерации цикла в строке cin >> j; перед считыванием происходит принудительное опустошение буфера std::cout. Если бы буфер был пуст, то проблемы бы не было (т.к. нечего бы было опустошать), но ведь в этом же цикле происходит и наполнение буфера: cout << in[i] << '\n';, а значит буфер не пуст, значит потоку приходится обращаться к ресурсоёмким функциям ОС.

1
  • но почему во втором примере буфер вывода пуст? мы же его наполняем содержимым in[i], точно так же, как и в первом примере
    – prostak
    23 янв 2021 в 13:54
5

Небольшой отчет.

Создал файл из 10000 случайных чисел, на вывод попадают примерно 4500 чисел. При запуске программы передача данных - через перенаправление в командной строке. Вывод на экран. VC++2019, включены все оптимизации, 64 разряда. Три запуска.

Первый вариант - 2238, 2191, 2245 мс на моей машине.
Второй вариант - 2202, 2339, 2161 мс.

Говорить о какой-то разнице не могу... Просто сам консольный вывод слишком длинный, он забивает все различия. Или вы значения руками вводили? :)

Для сравнения - OpenWatcom на тех же условиях :) в обоих случаях дал по 850 мс.

Но!...
Вот если перенаправлять вывод в файл - да, тогда примерно 36 мс в первом варианте и 16 мс во втором (и по 12 мс в Open Watcom). И вот здесь я могу согласиться с гипотезой Qwertiy.

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

Кстати, когда в VC++ заменил cin и cout на scanf и printf - время в обоих случаях упало до 850 мс, а при выводе в файл - до примерно 9,8 и 9,6 мс. Что еще раз говорит о том, что все несуразицы связаны - по крайней мере в VC++ - с реализацией потоков...

2
  • а что вы имеете ввиду под выводом в файл? что то я не очень понял
    – prostak
    23 янв 2021 в 5:33
  • 3
    test.exe < input - чтение данных из файла и вывод на экран, test.exe < input > output - чтение данных из файла, вывод перенаправлен в файл.
    – Harry
    23 янв 2021 в 6:30
4

Если смешивать ввод и вывод, перед вводом может оказываться flush вывода, который тоже потребует времени. Если в твоём замере этот flush использовался, то в первом случае он вызывался на каждый элемент, а вот втором - только один раз.

Попробуй замерить в перенаправлением вывода в файл и/или в nul - возможно результат изменится по сравнению с консолью.

6
  • но почему в первом случае он вызывался один раз, а во втором несколько раз? в чем отличие?
    – prostak
    23 янв 2021 в 4:02
  • 1
    @prostak, во-первых, наоборот, а во-вторых, потому что между cin и cout.
    – Qwertiy
    23 янв 2021 в 4:46
  • так во втором случае между cin и cout есть цикл for, то есть по идее именно в нем flush должен вызываться несколько раз. или я что то не таки понял?
    – prostak
    23 янв 2021 в 4:48
  • 1
    @prostak, между, а не перед.
    – Qwertiy
    23 янв 2021 в 4:50
  • 1
    @prostak, что-то я немного не то написал, точнее попутал порядок. Между выводом и вводом, а не между вводом и выводом.
    – Qwertiy
    23 янв 2021 в 17:27

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.