C와 C++에서 거의 동일한 코드 간의 실행 시간에서 큰 차이(x9)

C와 C++에서 거의 동일한 코드 간의 실행 시간에서 큰 차이(x9)

www.spoj.com에서 이 연습문제를 풀려고 했는데: FCTRL - 요인

꼭 읽을 필요는 없고, 궁금하면 그냥 해 :)

먼저 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

이제 코드는 거의 똑같다"고 덧붙였다.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";.

하지만 나는 여전히 c 대 c에서 x9의 성능과 낮은 메모리 사용량을 보았다.C++ 코드.

왜 그런 것일까요?

편집

내가 고쳤다.unsigned long로unsigned intC 코드로.그랬어야 했다.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);의 일후에printfC++ 버전과 유사한 성능을 제공한다.출력이 한 번에 1바이트가 아닌 작은 청크로 시스템에 기록되기 때문에 버퍼링을 완전히 비활성화하는 것만큼 느리지 않다.

이것은 당신의 C++ 라이브러리의 특정한 행동을 가리키는 것 같다: 나는 당신의 시스템이cin그리고cout에 생산량을 플러시하다.cout이 때.cin일부 C 라이브러리도 이 작업을 수행하지만, 일반적으로 터미널을 읽고 쓸 때만 이 작업을 수행한다.www.spoj.com 사이트에 의해 수행된 벤치마킹은 아마도 입력과 출력을 파일로 또는 파일로 리디렉션한다.

알렉스롭은 또 다른 테스트를 했다: 벡터에서 모든 입력을 한 번에 읽고 그 후에 모든 출력을 계산하고 쓰는 것이 C++ 버전이 왜 그렇게 느린지 이해하는 데 도움이 된다.C 버전에 비해 성능이 높아지는데, 이것은 내 요점을 증명하고 C++ 포맷 코드에 대한 의심을 없애준다.

또을 Blastfurnace의 Dada스 Stepsw, 든든을l에 .std::ostringstream마지막 한 번의 블라스팅으로 C++의 성능을 기본 C 버전으로 향상시켜 주는 것이다.QED.

인터레이싱 입력 위치cin로 출력하다.cout스트림 버퍼링 계획을 무효화하여 매우 비효율적인 I/O 처리를 야기하는 것으로 보인다.성능 10배 감소

PS: 알고리즘이 에 대해 잘못됨fact_num >= UINT_MAX / 5때문에fives *= 5 되기 에.> fact_num이것을 수정하는 방법은 다음과 같다.fivesa의unsigned long또는 aunsigned long long이 유형 중 하나가 다음보다 크면unsigned int. 또한 사용%u처럼scanf형식을 갖추다www.spoj.com에 있는 사람들이 그들의 벤치마크에 너무 엄격하지 않다니 운이 좋구나.

편집: 나중에 vitaux에 의해 설명되었듯이, 이러한 행동은 실제로 C++ 표준에 의해 강제된다.cin에 묶여 있다cout결석하여다음에서 입력 작업cin한 경우, 이 경우 에에 따라 리필이 수 있음.cout보류 중인 출력을 플러시하십시오. OP의 실행에서,cin홍수가 나는 것 같다cout조직적으로, 약간 과잉 살상적이고 눈에 띄게 비효율적이군

일리야 포포프는 이에 대한 간단한 해결책을 제공했다.cin에서 풀 수 있다cout에 덧붙여 또 하나의 마법 주문을 걸면서.std::ios_base::sync_with_stdio(false);:

cin.tie(nullptr);

또한 이러한 강제 플러시는 사용 시에도 발생한다는 점에 유의하십시오.std::endl대신에'\n'에 대해 종말을 고하다cout. 출력 라인을 C++ 관용적이고 순수한 외관으로 변경cout << 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을 이다.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손으로 직접 파싱하는 것은 여전히 더 나은 성능을 제공한다.

PS. 온라인 판사에게 유용한 C++로 숫자를 입력하는 여러 방법을 비교하는 글을 썼지만, 러시아어로만 쓸 수 있어, 미안해.그러나 코드 샘플과 최종 표는 이해할 수 있어야 한다.

문제는 cppreference를 인용하면 다음과 같다.

std::cin, std::cerr 또는 프로그램 종료로 인해 std::cout.program termination으로 호출되는 모든 입력

테스트가 간편함: 교체할 경우

cin >> fact_num;

와 함께

scanf("%d", &fact_num);

에 대해서도 마찬가지.cin >> num_of_inputs그러나 보관하다coutC++ 버전(또는 IOStream 버전)에서 C 1 버전과 거의 동일한 성능을 얻을 수 있음:

계속하면 똑같은 일이 일어난다.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 덕택)의 인용구가 있다.

클래스 basic_istream::sentry : 첫째, is.tie()가 null 포인터가 아닌 경우 함수 호출.tie()->flush()로 출력 시퀀스를 연관된 외부 C 스트림과 동기화한다.의 put 영역이 .tie()인 경우 이 호출을 억제할 수 있다는 점을 제외한다.추가로 구현은.rdbuf()->언더플로()의 호출이 발생할 때까지 통화를 플러시하도록 연기할 수 있다.보초 물체가 파괴되기 전에 이러한 호출이 발생하지 않으면 플러시 호출이 완전히 제거될 수 있다.

참조URL: https://stackoverflow.com/questions/34122193/big-difference-x9-in-the-execution-time-between-almost-identical-code-in-c-and