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 의 솔루션으로 업로드했습니다.
이번 결과는 다음과 같습니다. 시간 0.02 Mem 2.1M
이제 코드는 거의 동일 합니다. C 라이브러리의 stdio 버퍼와의 동기화를 해제하기 위해 여기std::ios_base::sync_with_stdio(false); 에 제안 된대로 C ++ 코드에 추가 했습니다 . 나는 또한 in의 이중 호출을 보상하기 위해 to 를 분할 했습니다 .printf("%d\n", num_of_trailing_zeros);printf("%d", num_of_trailing_zeros); printf("%s","\n");operator<<cout << num_of_trailing_zeros << "\n";
그러나 나는 여전히 C 대 C ++ 코드에서 x9 더 나은 성능 과 낮은 메모리 사용량을 보았습니다 .
왜 그런 겁니까?
편집하다
나는 C 코드에서 수정 unsigned long했습니다 unsigned int. 그것은 했어야 unsigned int위에서 도시 된 결과는 새로운 (관련된 unsigned int) 버전.
답변
두 프로그램 모두 똑같은 일을합니다. 그들은 똑같은 정확한 알고리즘을 사용하고 복잡성이 낮기 때문에 성능은 대부분 입력 및 출력 처리의 효율성과 관련이 있습니다.
scanf("%d", &fact_num);한쪽과 cin >> fact_num;다른 한쪽으로 입력을 스캔하는 것은 어느 쪽이든 비용이 많이 들지 않습니다. 실제로 C ++에서는 변환 유형이 컴파일 시간에 알려지고 올바른 구문 분석기가 C ++ 컴파일러에 의해 직접 호출 될 수 있으므로 비용이 적게 듭니다. 출력도 마찬가지입니다. 에 대한 별도의 호출을 작성하는 것도 중요 printf("%s","\n");하지만 C 컴파일러는이를에 대한 호출로 컴파일하기에 충분합니다 putchar('\n');.
따라서 I / O와 계산의 복잡성을 모두 살펴보면 C ++ 버전이 C 버전보다 빠릅니다.
버퍼링을 완전히 비활성화하면 stdoutC 구현 속도가 C ++ 버전보다 훨씬 느려집니다. 와 AlexLop에 의해 또 다른 테스트 fflush(stdout);마지막 후에 printf는 C ++ 버전으로 수익률과 유사한 성능을 제공합니다. 출력이 한 번에 1 바이트가 아닌 작은 청크로 시스템에 기록되기 때문에 버퍼링을 완전히 비활성화하는 것만 큼 느리지 않습니다.
이것은 C ++ 라이브러리의 특정 동작을 가리키는 것 같습니다. 시스템의 구현을 의심 cin하고 에서 입력을 요청할 때 cout출력을 플러시합니다 . 일부 C 라이브러리도이 작업을 수행하지만 일반적으로 터미널에서 읽고 쓸 때만 가능합니다. www.spoj.com 사이트에서 수행 한 벤치마킹은 입력 및 출력을 파일로 또는 파일에서 리디렉션합니다.coutcin
AlexLop은 또 다른 테스트를 수행했습니다. 벡터에서 한 번에 모든 입력을 읽고 이후에 모든 출력을 계산하고 작성하면 C ++ 버전이 훨씬 느린 이유를 이해하는 데 도움이됩니다. 그것은 C 버전의 성능을 향상시키고 이것은 내 요점을 증명하고 C ++ 형식화 코드에 대한 의심을 제거합니다.
Blastfurnace의 또 다른 테스트는 모든 출력을 an에 저장 std::ostringstream하고 마지막에 한 번의 폭발로 플러시하는 것으로 C ++ 성능이 기본 C 버전의 성능으로 향상됩니다. QED.
입력
cin과 출력을 인터레이스 하는cout것은 매우 비효율적 인 I / O 처리를 유발하여 스트림 버퍼링 체계를 무너 뜨립니다. 성능을 10 배 감소시킵니다.
PS : 당신의 알고리즘에 대한 잘못된 fact_num >= UINT_MAX / 5때문에 fives *= 5오버 플로우와이되기 전에 주변에 포장됩니다 > fact_num. 당신함으로써이 문제를 해결 할 수 또는를 이러한 유형 중 하나가보다 큰 경우 . 형식으로 도 사용 하십시오 . www.spoj.com의 사람들이 벤치 마크에서 너무 엄격하지 않다는 것은 운이 좋습니다.fivesunsigned longunsigned long longunsigned int%uscanf
편집 : 나중에 vitaux에서 설명했듯이이 동작은 실제로 C ++ 표준에 의해 요구됩니다. 기본적으로 cin연결되어 cout있습니다. cin입력 버퍼를 다시 채워야 하는 입력 작업으로 인해 cout보류중인 출력이 플러시됩니다. OP의 구현에서 약간 과잉이고 눈에 띄게 비효율적 인 체계적으로 cin플러시 cout되는 것 같습니다 .
Ilya Popov는 이에 대한 간단한 해결책을 제공했습니다. 다음과 같은 추가 마법 주문을 시전하여 cin풀 수 있습니다 .coutstd::ios_base::sync_with_stdio(false);
cin.tie(nullptr);
또한 에서 줄의 끝을 생성하는 std::endl대신 사용할 때 이러한 강제 플러시가 발생합니다 . 출력 라인을 더 C ++ 관용적이고 순진한 모습으로 변경하면 동일한 방식으로 성능이 저하됩니다.'\n'coutcout << num_of_trailing_zeros << endl;
답변
메이크업의 또 다른 트릭 iostream의 빨리 당신이 모두를 사용할 때 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);
}
이 방법은 성능면에서 C 스타일에 가깝거나 scanf. getchar특히 getchar_unlocked손으로 쓴 구문 분석과 함께 사용하면 여전히 더 나은 성능을 제공합니다.
추신. 온라인 심사 위원에게 유용한 C ++로 숫자를 입력하는 여러 가지 방법을 비교 하는 글 을 작성 했지만 러시아어로만 작성되었습니다. 죄송합니다. 그러나 코드 샘플과 최종 테이블은 이해할 수 있어야합니다.
답변
문제는 cppreference를 인용하는 것입니다 .
std :: cin의 모든 입력, std :: cerr 로의 출력 또는 프로그램 종료는 std :: cout.flush ()에 대한 호출을 강제합니다.
테스트하기 쉽습니다.
cin >> fact_num;
와
scanf("%d", &fact_num);
동일 cin >> num_of_inputs하지만 coutC ++ 버전 (또는 오히려 IOStream 버전)에서 C one과 거의 동일한 성능을 얻을 수 있습니다.
보관 cin하지만 교체해도 마찬가지입니다.
cout << num_of_trailing_zeros << "\n";
와
printf("%d", num_of_trailing_zeros);
printf("%s","\n");
간단한 해결책은 풀어이다 cout및 cin리아 포포로 언급 :
cin.tie(nullptr);
표준 라이브러리 구현은 특정 경우에 flush 호출을 생략 할 수 있지만 항상 그런 것은 아닙니다. 다음은 C ++ 14 27.7.2.1.3의 인용문입니다 (chqrlie 덕분에).
class basic_istream :: sentry : 먼저 is.tie ()가 널 포인터가 아닌 경우 함수는 is.tie ()-> flush ()를 호출하여 출력 시퀀스를 연결된 외부 C 스트림과 동기화합니다. is.tie ()의 넣기 영역이 비어 있으면이 호출을 억제 할 수 있다는 점을 제외하고. 또한 구현은 is.rdbuf ()-> underflow () 호출이 발생할 때까지 flush 호출을 연기 할 수 있습니다. 센트리 개체가 파괴되기 전에 그러한 호출이 발생하지 않으면 flush 호출이 완전히 제거 될 수 있습니다.
