...воспользоваться простой советской содой:
#include <iostream>
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
// Ваш код тут
int n;
std::cin >> n;
long long sum = 0;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
sum += x;
}
std::cout << sum << std::endl;
}
Это ускорит код настолько, что вам в жизни больше не придется думать о скорости ввода-вывода. Ставьте классы и подписывайтесь на мой канал!
Ага, размечтались. Это не так работает. Мы строили культуру и... У нас все еще используется <iostream>
, а значит, в коде появляется виртуальное наследование и все вытекающие из этого деоптимизации. Даже если вы нашли на задворках интернета сниппет "быстрый-ввод-вывод-от-васяна", вы все равно опираетесь на блочно буфферизованный вывод. (К тому же никакая из этих библиотек и знать не знает, что такое эти ваши флоаты.) В большинстве случаев большая часть процессорного времени растрачивается на кодирование и раскодирование чисел, а не взаимодействие с файловой системой.
Можно ли лучше? ...Тупой вопрос. Поста бы не было, будь это не так. Смотрите, к чему за полмесяца привело мое СДВГ:
Результаты с Linux, поэтому они выглядят адекватно.
На Винде моя библиотека по крайней мере настолько же быстрая, как на этом графике, но при этом она умудряется значительно обходить <iostream>
для целых чисел и <cstdio>
для чисел с плавающей точкой. Это подтверждает байку "используйте cstdio пока вам не понадобятся флоаты", которая на моей машине не воспроизводилась, потому что, внезапно, относительная производительность cstdio и iostream под Линуксом ровно противоположная. Мда. (Тем, кто любит есть гнилые яблоки: ваш <iostream>
отстой из-за использования libc++. Установите GCC вместе с Linux (brew тоже отстой), перейдите на cstdio или (что еще лучше (да, я завлекаю людей в свое болото, и что вы мне сделаете?)) мой I/O.)
Дальнейшие лучи любви будут направлены в сторону Windows Min-"как это вообще можно было зарелизить"-GW:
Производительность сравнивается с <iostream>
и <cstdio>
, а также с вводом Копелиовича как самым частым примером быстрого ввода-вывода среди спортивных "я не буду идти километр до магазина" программистов.
"Random length" обозначает числа, длина которых распределена равномерно, а "random value" — числа, сами значения которых равномерно выбраны среди всех допустимых значений типа. В частности, в этом случае большинство чисел будет максимальной длины. Это предсказуемое поведение в некоторых случаях ускоряет обработку.
rng
распределено равномерно. Разница между rng
и e^rng
такая же, как между "random value" и "random length". Единицы измерения между разными тестами, кстати, несравнимы.
Тут ничего интересного. Можно покекать с того, что if (flag) std::cout << "YES"; else std::cout << "NO";
быстрее, чем std::cout << (flag ? "YES" : "NO");
.
Еще у меня быстрый std::bitset
есть. Вот бы он еще был кому-то нужен...
Заметьте, что по некоторой причине вывод несколько медленнее ввода. Дело в том, что руки кривые тут не у меня, а у разработчиков операционных систем, у которых запись в RAM-диск медленнее записи в пайп. В общем и целом, на интерактивных задачах скорость ввода ухудшается — поскольку входной файл нельзя mmap'ать, — а вывода увеличивается — поскольку в выходной пайп можно писать в обход обработчиков vfs. К сожалению, вывод ускоряется только если flush вывода не происходит, что к интерактивным задачам применимо очень слабо. Наверное, это больше интересно разработчикам тестирующих систем.
Дай потыкать свою поделку
Держи:
#include <iostream>
/* Скопипастите сюда blazingio */
int main() {
// Если вы привыкли писать эти две строчки, можете их оставить, они просто ничего не будут делать.
// std::ios_base::sync_with_stdio(false);
// std::cin.tie(nullptr);
// Если вы используете std::cout.tie(nullptr);, вы неправы.
// Поддержка этого не будет добавлена.
// Оно вам не нужно. Удалите.
// Вы наверняка добавили в каждое из своих решений лишние 12 байт. Они заняли место на диске.
// Диски не резиновые, их производят маленькие дети на фабриках. Вы хотите, чтобы маленьким
// детям из-за вас пришлось больше работать? Подумайте о детях.
// Ну и о себе тоже. Одна из картинок загружается с моего домена. Я вас по IP вычислю.
// Изливайте душу здесь
int n;
std::cin >> n;
long long sum = 0;
for (int i = 0; i < n; i++) {
int x;
std::cin >> x;
sum += x;
}
std::cout << sum << std::endl;
}
А вот большая синия ссылка на библиотеку, потому что иначе вы ее пропустите:
blazingio.min.hpp
Библиотека называется blazingio потому, что я профессиональная Rust-программистка и подписала соглашение, которое заставляет меня использовать слово "blazing" хотя бы по разу в каждом проекте, даже если он не написан на Rust. Она замещает std::cin
и std::cout
из <iostream>
, поэтому их можно продолжать использовать как раньше.
Если вы привыкли к cin
/cout
, просто вставьте эту библиотеку в свой шаблон. Если она начинает творить какую-то дичь или вам просто захотелось ее отключить, просто удалите ее. Никаких изменений в других местах делать не нужно. Круто! Да это ж круто!
Минусы будут?
C-- на Codeforces нет, так что минусов нет, только плюсы.
А вообще, думать о минусах как-то пессимистично с вашей стороны. нет бы спросить "а еще будет?" или погладить по головке.
Главный минус в том, что код библиотеки большой. Размер около 9 KB, что примерно в 7 раз меньше ограничения размера посылки на Codeforces. В репозитории есть человекочитаемый код этого кода и инструкция о том, как собрать ужатую версию, если вы печетесь о размере сорсов. С другой стороны, если вы не используете большой шаблон помимо blazingio, это не должно быть проблемой.
Еще один минус в том, что blazingio держит огромные буфферы в памяти, то есть использование оперативки может быть увеличено на размер входных и выходных файлов. Обычно он не превышает 20 мебибайт. В большинстве случаев это не проблема, но это может быть полезно знать. Еще в скриптах ejudge есть легаси, из-за которого на многих инстансах ejudge приходится аллоцировать под буффер вывода ровно 24 МиБ: т.е. и место зря используется, и в редких случаях может оказаться недостаточно. Ждем фиксов.
Напоследок: эта библиотека может оказаться бесполезной. Когда-то существовали задачи, которые нельзя было решить без быстрого ввода-вывода, но теперь делать такие задачи — моветон. Однако даже если быстрый ввод-вывод не является необходимым, он может дать вам фору и позволить использовать менее эффективные алгоритмы в других местах.
Как это работает?
Я продала душу дьяволу. Вопросы?
Большинство спортпрогеров, к сожалению, не умеют применять трюки из олимпиадных задач в вещах, которые кажущится низкоуровневыми. У олпрогеров есть и другие проблемы: грустная менталка, отрицательное число друзей в реальной жизни, а еще они считают нормальными симптомы выгорания и заметают под ковер мелтдауны. Еще они меньше знакомы с внутренностями ОС и железа. Может быть, это повод научиться чему-то новому.
К сожалению, у меня особо нет времени на полноценный разбор. Вот короткий список оптимизаций:
mmap
на входном файле (аналогично на Windows)- Основанная на
MAP_NORESERVE
аллокация буффера вывода на Linux - Расширяемый без условных прыжков буффер на основе
PAGE_GUARD
на Windows - Оптимизироавнные fast paths для а) чтения из обычного файла, б) чтения из пайпа при непустом буффере
- Костыли для плохого кодгена GCC при условном вызове сисколлов в hot loop с помощью инлайн-ассемблера (пришлось залезть в код XNU для поддержки таких методов и на M1, бррр)
- Оптимизированное загрузкой цифр в u64 пока хватает точности чтение вещественных чисел
- "Корневая декомпозиция" (ах если бы) для экспонент флоатов
- Оптимизированные SIMD'ом ввод строк и ввод-вывод битсетов, включая SWAR на таргетах без SIMD
FILE_FLAG_NO_BUFFERING
,FILE_FLAG_WRITE_THROUGH
для вывода в файл на Windows- Вывод целых чисел без деления трюком Terje Mathisen, в том числе применительно к мантиссам
Если кому-то интересно почитать про такое поподробнее, скажите об этом, возможно, напишу пост про это.