Я пытался решить это упражнение с сайта www.spoj.com: FCTRL - Factorial
Вам не обязательно это читать, просто сделайте это, если вам интересно :)
Сначала я реализовал это на C ++ (вот мое решение):
#include <iostream>
using namespace std;
int main() {
unsigned int num_of_inputs;
unsigned int fact_num;
unsigned int num_of_trailing_zeros;
std::ios_base::sync_with_stdio(false); // turn off synchronization with the C library’s stdio buffers (from https://stackoverflow.com/a/22225421/5218277)
cin >> num_of_inputs;
while (num_of_inputs--)
{
cin >> fact_num;
num_of_trailing_zeros = 0;
for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
num_of_trailing_zeros += fact_num/fives;
cout << num_of_trailing_zeros << "\n";
}
return 0;
}
Я загрузил его как решение для g ++ 5.1
Результат был: Время 0,18 Mem 3,3M
Но затем я увидел некоторые комментарии, в которых утверждалось, что их время выполнения было меньше 0,1. Поскольку я не мог думать о более быстром алгоритме, я попытался реализовать тот же код на C :
#include <stdio.h>
int main() {
unsigned int num_of_inputs;
unsigned int fact_num;
unsigned int num_of_trailing_zeros;
scanf("%d", &num_of_inputs);
while (num_of_inputs--)
{
scanf("%d", &fact_num);
num_of_trailing_zeros = 0;
for (unsigned int fives = 5; fives <= fact_num; fives *= 5)
num_of_trailing_zeros += fact_num/fives;
printf("%d", num_of_trailing_zeros);
printf("%s","\n");
}
return 0;
}
Я загрузил его как решение для gcc 5.1
На этот раз результат был: Time 0.02 Mem 2.1M
Теперь код почти такой же , я добавил std::ios_base::sync_with_stdio(false);
в код C ++, как было предложено здесь, чтобы отключить синхронизацию с буферами stdio библиотеки C. Я также расколоть , printf("%d\n", num_of_trailing_zeros);
чтобы printf("%d", num_of_trailing_zeros); printf("%s","\n");
компенсировать двойной вызов operator<<
в cout << num_of_trailing_zeros << "\n";
.
Но я все еще видел лучшую производительность x9 и меньшее использование памяти в коде C по сравнению с кодом C ++.
Почему это?
РЕДАКТИРОВАТЬ
Я установил , unsigned long
чтобы unsigned int
в коде C. Так должно было быть, unsigned int
и результаты, показанные выше, относятся к версии new ( unsigned int
).
std::ostringstream
для накопления вывода и его одновременной отправкиstd::cout
всем в конце сокращает время до 0,02. Использованиеstd::cout
в цикле просто медленнее в их среде, и я не думаю, что есть простой способ улучшить его.Ответы:
Обе программы делают одно и то же. Они используют один и тот же точный алгоритм, и, учитывая его невысокую сложность, их производительность в основном зависит от эффективности обработки ввода и вывода.
сканирование ввода с
scanf("%d", &fact_num);
одной стороны, аcin >> fact_num;
с другой в любом случае не кажется очень дорогостоящим. Фактически, в C ++ это должно быть менее затратно, поскольку тип преобразования известен во время компиляции, и правильный синтаксический анализатор может быть вызван непосредственно компилятором C ++. То же самое и с выходом. Вы даже можете написать отдельный вызов дляprintf("%s","\n");
, но компилятор C достаточно хорош, чтобы скомпилировать это как вызовputchar('\n');
.Итак, учитывая сложность как ввода-вывода, так и вычислений, версия C ++ должна быть быстрее, чем версия C.
Полное отключение буферизации
stdout
замедляет реализацию C до чего-то даже более медленного, чем версия C ++. Другой тест AlexLop с пометкойfflush(stdout);
после последнегоprintf
дает такую же производительность, как и версия C ++. Это не так медленно, как полное отключение буферизации, потому что вывод записывается в систему небольшими порциями, а не по одному байту за раз.Похоже, это указывает на определенное поведение в вашей библиотеке C ++: я подозреваю, что ваша система реализует
cin
иcout
сбрасывает вывод,cout
когда вводится запрос отcin
. Некоторые библиотеки C делают это также, но обычно только при чтении / записи в терминал и из него. Тестирование, проводимое сайтом www.spoj.com, вероятно, перенаправляет ввод и вывод в файлы и из файлов.AlexLop провел еще один тест: чтение всех входных данных одновременно в векторе с последующим вычислением и записью всего вывода помогает понять, почему версия C ++ работает намного медленнее. Он увеличивает производительность по сравнению с версией C, это подтверждает мою точку зрения и устраняет подозрения в коде форматирования C ++.
Другой тест от Blastfurnace, сохраняющий все выходные данные в файле и сбрасывающий его за один проход
std::ostringstream
в конце, действительно улучшает производительность C ++ по сравнению с базовой версией C. QED.PS: ваш алгоритм неверен,
fact_num >= UINT_MAX / 5
потому чтоfives *= 5
он переполняется и оборачивается, прежде чем он станет> fact_num
. Вы можете исправить это путем или если один из этих типов больше . Также используйте как формат. Вам повезло, что ребята с www.spoj.com не слишком строги в своих тестах.fives
unsigned long
unsigned long long
unsigned int
%u
scanf
РЕДАКТИРОВАТЬ: как позже объяснил vitaux, такое поведение действительно предусмотрено стандартом C ++. по умолчанию
cin
привязан кcout
. Операция ввода,cin
для которой требуется пополнение входного буфера, приведетcout
к сбросу ожидающих вывода. В реализации OP,cin
похоже, происходитcout
систематическая очистка , что немного избыточно и явно неэффективно.Илья Попов предложил для этого простое решение: от него
cin
можно отвязатьсяcout
, наложив другое магическое заклинание в дополнение кstd::ios_base::sync_with_stdio(false);
:Также обратите внимание, что такая принудительная очистка также происходит при использовании
std::endl
вместо того,'\n'
чтобы произвести конец строкиcout
. Изменение выходной строки на более идиоматичный и невинный вид C ++ такжеcout << num_of_trailing_zeros << endl;
снизит производительность.источник
std::ostringstream
и вывод всего одного раза в конце сокращает время до паритета с версией C.ostringstream
для вывода, и он дал Time 0.02 QED :). Что касаетсяfact_num >= UINT_MAX / 5
, ДОБРЫЙ вопрос!vector
и последующая обработка вычислений (безostringstream
) дает тот же результат! Время 0,02. Сочетание обоихvector
иostringstream
не улучшит его больше. То же время 0,02sizeof(int) == sizeof(long long)
это: добавить тест в тело цикла после,num_of_trailing_zeros += fact_num/fives;
чтобы проверитьfives
, достиг ли он своего максимума:if (fives > UINT_MAX / 5) break;
Еще один способ сделать
iostream
s быстрее, если вы используете оба,cin
иcout
вызовитеcin.tie(nullptr);
По умолчанию, когда вы вводите что-либо из
cin
, он сбрасываетсяcout
. Чередование ввода и вывода может значительно снизить производительность. Это делается для интерфейса командной строки, когда вы показываете подсказку, а затем ждете данных:std::string name; cout << "Enter your name:"; cin >> name;
В этом случае вы хотите убедиться, что подсказка действительно отображается, прежде чем вы начнете ждать ввода. С линией выше вы разрываете эту связь
cin
иcout
становитесь независимыми.Начиная с C ++ 11, еще одним способом повышения производительности с помощью iostreams является использование
std::getline
вместе сstd::stoi
, например:std::string line; for (int i = 0; i < n && std::getline(std::cin, line); ++i) { int x = std::stoi(line); }
Этот способ может приблизиться к стилю Си по производительности или даже превзойти его
scanf
. Использование,getchar
особенноgetchar_unlocked
вместе с рукописным анализом, по-прежнему обеспечивает лучшую производительность.PS. Я написал пост, сравнивающий несколько способов ввода чисел на C ++, полезный для онлайн-судей, но он только на русском, извините. Однако примеры кода и итоговая таблица должны быть понятными.
источник
std::readline
иstd::stoi
не является функционально эквивалентной коду OPs. Обаcin >> x;
иscanf("%f", &x);
принимают пробелы муравья в качестве разделителя, в одной строке может быть несколько чисел.Проблема в том, что цитируя cppreference :
Это легко проверить: если вы замените
cin >> fact_num;
с участием
scanf("%d", &fact_num);
и то же самое,
cin >> num_of_inputs
но при этомcout
вы получите примерно такую же производительность в вашей версии C ++ (или, скорее, версии IOStream), что и в версии C:То же самое произойдет, если вы оставите,
cin
но заменитеcout << num_of_trailing_zeros << "\n";
с участием
printf("%d", num_of_trailing_zeros); printf("%s","\n");
Простое решение - развязать
cout
и,cin
как сказал Илья Попов:cin.tie(nullptr);
Реализациям стандартной библиотеки разрешено опускать вызов сброса в некоторых случаях, но не всегда. Вот цитата из C ++ 14 27.7.2.1.3 (спасибо chqrlie):
источник
is.tie()
это не нулевой указатель, функция вызываетis.tie()->flush()
синхронизацию выходной последовательности с любым связанным внешним потоком C. За исключением того, что этот вызов может быть подавлен, если область размещенияis.tie()
пуста. Кроме того, реализации разрешено отложить вызов для сброса до тех пор, пока неis.rdbuf()->underflow()
произойдет вызов . Если такой вызов не происходит до того, как часовой объект будет уничтожен, вызов flush может быть полностью исключен.