[解決済み] CとC++のほぼ同じコードの実行時間に大きな差(9倍)

質問

私は 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 メモリ 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 メモリ 2.1M

このコードは ほとんど同じ ですが、私は std::ios_base::sync_with_stdio(false); をC++のコードに追加しました。 ここで を追加して、Cライブラリのstdioバッファとの同期をオフにしました。また、私は 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 vs. C++ コードでより低いメモリ使用量でした。

それはなぜでしょうか？

EDIT

修正したのは 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版より速いはずです。

のバッファリングを完全に無効にして stdout を完全に無効にすると、C実装はC++版よりさらに遅くなります。 AlexLopによる別のテストでは fflush(stdout); の後に printf は C++ 版と同様の性能を発揮します。出力は一度に1バイトずつではなく、小さなチャンクでシステムに書き込まれるため、バッファリングを完全に無効にするほど遅くありません。

これは、C++ ライブラリにおける特定の動作を指しているようです。私は、あなたのシステムの cin と cout に出力をフラッシュします。 cout から入力が要求されたとき cin . いくつかの C ライブラリも同様ですが、通常はターミナルとの間で読み書きをするときだけです。www.spoj.com のサイトで行われているベンチマークでは、おそらくファイルへの入力とファイルからの出力をリダイレクトしているのでしょう。

AlexLop は別のテストを行いました。ベクトルですべての入力を一度に読み、その後すべての出力を計算し書き込むことは、C++ バージョンがなぜこれほど遅いのかを理解するのに役立ちます。これは、私の主張を証明し、C++ フォーマット コードに対する疑念を取り除きます。

Blastfurnace による別のテストでは、すべての出力を std::ostringstream に格納し、最後にそれを一度にフラッシュすることで、C++ のパフォーマンスは基本的な C バージョンに改善されます。QED。

からの入力をインターレースする cin への出力と cout は非常に非効率的な I/O 処理を引き起こすようで、ストリーム バッファリング スキームを打ち負かすようです。

PS: あなたのアルゴリズムは fact_num >= UINT_MAX / 5 なぜなら fives *= 5 になる前にオーバーフローして回り込んでしまうからです。 > fact_num . これを修正するには fives を unsigned long または unsigned long long よりも大きい場合、これらのタイプのいずれかが unsigned int . また %u として scanf という形式を採用しています。 www.spoj.com の連中がベンチマークに厳しすぎないのは幸いです。

編集: 後で vitaux が説明したように、この動作は確かに C++ 標準で義務付けられています。 cin は cout に結びつけられます。 からの入力操作は cin からの入力操作で、入力バッファの再充填が必要な場合は cout が保留中の出力をフラッシュします。 OPの実装では cin をフラッシュしているように見えますが cout を系統的にフラッシュしているように見えますが、これは少しやりすぎで、目に見えて非効率です。

Ilya Popovはこれに対する簡単な解決策を提供しました。 cin を解くことができます。 cout に加えて、別の魔法をかけることで std::ios_base::sync_with_stdio(false); :

cin.tie(nullptr);

また、このような強制フラッシュは std::endl の代わりに '\n' で行末を表示するように cout . 出力行をより C++ 的で無害そうな cout << num_of_trailing_zeros << endl; に変更すると、同じようにパフォーマンスが低下します。