Тут стал вопрос производительности операций чтения/записи. Напомню, что в С++ есть замечательная функция-флаг ios_base::sync_with_stdio() с помощью которой можно отключить синхронизацию стандартных потоков C и С++, и тем самым повысить производительность. Замечательный компилятор от не менее замечательной фирмы Microsoft этот флаг тупо игнорирует. Т.к. я не директор Microsoft и даже не ответственный за выпуск Visual Studio — мне глубоко всё равно кто в этом виноват. Для меня главное — результат.
Простой тест показал:
1255626 — G++ с выключенным sync_with_stdio — 50 мс
1255624 — G++ c включенным sync_with_stdio — 200 мс
1255627 — MS C++ с проигнорированным sync_with_stdio — 230 мс
Но, т.к. на этом сайте GNU C++ используется через одно место, т.е. через Microsoft Windows, используя непонятный порт под названием MinGW, то мне стало интересно какова реальная ситуация. Я взял две одинаковые виртуальные машины, запущенные на одной и той же физической — одну с 32-хбитной Windows, другую с 32-хбитным Linux. Сгенерировал файл с 10 млн. рандомных чисел (около 100МБ, генерировал, между прочим, кодом из этого поста). Взял простой код, считывающий эти 10 млн. чисел. И вот скриншоты того, что получилось:
Windows/MSVS с проигнорированным sync_with_stdio ~15 с
Windows/MinGW c включенным sync_with_stdio ~14 с
Windows/MinGW c выключенным sync_with_stdio ~3 с
Linux/GCC c включенным sync_with_stdio ~8 с
Linux/GCC c выключенным sync_with_stdio <3 с
Т.о. в некоторых случаях можно добиться несколько кратного увеличения производительности простой сменой ОС и компилятора. Можете попробовать сами ;)
Уверены, что можно доверять тестам под виртуальной машиной в разных операционных системах? У меня есть сомнения по этому поводу, учитывая, что современные виртуальные машины весьма сложны и далеки от простого линейного "имитирования" машинного кода.
(Из этой же серии у меня вот под VMWare недавно получилось, что на языке D map работает якобы в 3 раза быстрее, чем в C++ — что выглядит весьма подозрительно)
В целом уверен — оно использует аппаратную виртуализацию (AMD-V) и затраты на это минимальны. Можете убедится сами без виртуализации (хотя сейчас чуть ли не половина серверов виртуализирована, и я не уверен, что на всех контест-сайтах используются не виртуализированные сервера).
А в том, что разные операционные системы и был прикол — разница между MinGW и оригинальным GCC значительна, т.к. сами операционные системы сильно отличаются.
Ну а конкретные тесты map-а на языке D стоит проверить... Потому как, например, вот это решение на Java (1255811) почти в два раза быстрее решения на MS C++ (1255627), что тоже выглядит весьма подозрительно. ;)
Какие результаты дает clang на линуксе на такой же виртуалке? Мне кажется, что от компилятора должно мало зависеть в таком тесте.
Какие результаты показывает stdio, если выполнять те же самые действия?
От компилятора может зависеть используемая реализация стандартной библиотеки C++, а от неё уже весь I/O, в т.ч. и ios_base::sync_with_stdio() — это можно увидеть на примере MS C++, где реализация стандартной библиотеки от Dinkumware игнорирует sync_with_stdio, и в итоге один и тот же код работает в 4-5 раз медленнее, нежели с использованием gcc.
Компилирование clang-ом ничего не дает по той простой причине, что результирующий файл всё-равно зависит от libstdc++.so, т.е. используется та же самая gnu'шная реализация стандартной библиотеки C++, что и при компилировании gcc. Ситуацию может изменить использование clang вместе с новой libcxx, но последняя пока в разработке.
scanf работает немного быстрее, нежели cin даже с выключенным синком — 1,9-2,0 секунды (на линуксе с gcc).
Кстати, есть ещё один способ ускорить ввод данных с iostreams. По умолчанию
coutпривязан кcin, что означает, что при каждой операции надcinвызываетсяcout.flush(). Это сделано, чтобы такой код работал нормально:Чтобы такого не происходило, надо вызвать
cin.tie(NULL);.если ввод чередуется с выводом, то так делать нельзя, верно?
Так делать нельзя только на интерактивных задачах, где нужно вывести строку обязательно перед вводом новой (ну или надо использовать
endl/flushявно). В остальных случаях хоть как чередуй, ничего плохого не будет — всё равно при закрытии файла весь буферcoutбудет сброшен.