Быстрый ввод-вывод для соревновательного программирования

Опубликовано: 15 Июля, 2021

В соревновательном программировании важно как можно быстрее считывать вводимые данные, чтобы сэкономить драгоценное время.

Вы, должно быть, видели различные постановки задач, в которых говорилось: « Предупреждение: большие данные ввода-вывода, будьте осторожны с некоторыми языками (хотя большинство из них должно быть в порядке, если алгоритм хорошо спроектирован)» . Ключом к решению таких проблем является использование методов более быстрого ввода-вывода.

Часто рекомендуется использовать scanf / printf вместо cin / cout для быстрого ввода и вывода. Однако вы все равно можете использовать cin / cout и достичь той же скорости, что и scanf / printf, включив следующие две строки в свою функцию main ():

 ios_base :: sync_with_stdio (ложь);

Он включает или выключает синхронизацию всех стандартных потоков C ++ с соответствующими стандартными потоками C, если он вызывается до того, как программа выполнит свою первую операцию ввода или вывода. Добавление ios_base :: sync_with_stdio (false); (что по умолчанию верно) до того, как любая операция ввода-вывода предотвратит эту синхронизацию. Это статический член функции std :: ios_base.

 cin.tie (NULL);

tie () - это метод, который просто гарантирует очистку std :: cout до того, как std :: cin примет ввод. Это полезно для интерактивных консольных программ, которые требуют постоянного обновления консоли, но также замедляют работу программы при больших объемах ввода-вывода. Часть NULL просто возвращает указатель NULL.

Более того, вы можете включить стандартную библиотеку шаблонов (STL) одним включением:

 # включить <бит / stdc ++. h>

Итак, ваш шаблон для соревновательного программирования может выглядеть так:

 # включить <бит / stdc ++. h>
используя пространство имен std;

int main ()
{
    ios_base :: sync_with_stdio (ложь);
    cin.tie (NULL);
    возврат 0;
}

Рекомендуется использовать cout << « n»; вместо cout << endl ;. endl работает медленнее, потому что вызывает промывку потока, что обычно не требуется (подробности см. здесь). (Вам нужно будет сбросить, если вы пишете, скажем, интерактивный индикатор выполнения, но не при записи миллиона строк данных.) Напишите ' n вместо endl.

Мы можем протестировать наши методы ввода и вывода на задаче INTEST - Enormous Input Teston SPOJ. Перед дальнейшим чтением я предлагаю вам сначала решить эту проблему.

Решение в C ++ 4.9.2

Обычный ввод-вывод: в приведенном ниже коде используются cin и cout. Решение принимается со временем выполнения 2,17 секунды.




// A normal IO example code
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, k, t;
int cnt = 0;
cin >> n >> k;
for ( int i=0; i<n; i++)
{
cin >> t;
if (t % k == 0)
cnt++;
}
cout << cnt << " " ;
return 0;
}

Быстрый ввод-вывод Однако мы можем добиться большего и значительно сократить время выполнения, добавив две строки. Приведенная ниже программа принимается со временем выполнения 0,41 секунды.




// A fast IO program
#include <bits/stdc++.h>
using namespace std;
int main()
{
// added the two lines below
ios_base::sync_with_stdio( false );
cin.tie(NULL);
int n, k, t;
int cnt = 0;
cin >> n >> k;
for ( int i=0; i<n; i++)
{
cin >> t;
if (t % k == 0)
cnt++;
}
cout << cnt << " " ;
return 0;
}

Теперь, говоря о соревнованиях, таких как ACM ICPC, Google CodeJam, TopCoder Open, вот эксклюзивный код для наиболее быстрого чтения целых чисел.




void fastscan( int &number)
{
//variable to indicate sign of input number
bool negative = false ;
register int c;
number = 0;
// extract current character from buffer
c = getchar ();
if (c== '-' )
{
// number is negative
negative = true ;
// extract the next character from the buffer
c = getchar ();
}
// Keep on extracting characters if they are integers
// ie ASCII Value lies from '0'(48) to '9' (57)
for (; (c>47 && c<58); c= getchar ())
number = number *10 + c - 48;
// if scanned input has a negative sign, negate the
// value of the input number
if (negative)
number *= -1;
}
// Function Call
int main()
{
int number;
fastscan(number);
cout << number << " " ;
return 0;
}

getchar_unlocked () для более быстрого ввода на C для соревновательного программирования

Эта статья предоставлена Vinay Garg. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью и отправить ее по электронной почте на deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене.

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.