これはC++での入力方法の中で最も速いものです

Question

私は様々なプログラミングのオリンピックをコーディングしていますので、時間効率を向上させるために、余分なライブラリを追加する必要なしに入力を得るための最速の方法を探しています。コンテスト中にgccコンパイラごとに、私たちは明らかにコンパイラにライブラリを追加することはできません。これまでのC++では、cinとcoutを使っていましたが、scanfとprintfはそれよりもはるかに高速であることが分かったので、もっと複雑な方法を教えてください。私はもっ​​と時間が好きです。 ありがとうございます。

Answer 1

ストリームは常にC-API関数よりも低速ですが、デフォルトではC層と同期するので、よくある誤解です。そうです、それは機能でありバグではありません。

（あなたの好みに応じて、と読みやすさ、）型の安全性を犠牲にすることなく、あなたはおそらく使用してストリームのパフォーマンスを得る：

std::ios_base::sync_with_stdio (false); 

---

少しインジケータ：

#include <cstdio> 
#include <iostream> 

template <typename Test> 
void test (Test t) 
{ 
    const clock_t begin = clock(); 
    t(); 
    const clock_t end = clock(); 
    std::cout << (end-begin)/double(CLOCKS_PER_SEC) << " sec\n"; 
} 

void std_io() { 
    std::string line; 
    unsigned dependency_var = 0; 

    while (!feof (stdin)) { 
     int c; 
     line.clear(); 
     while (EOF != (c = fgetc(stdin)) && c!='\n') 
      line.push_back (c); 
     dependency_var += line.size(); 
    } 

    std::cout << dependency_var << '\n'; 
} 

void synced() { 
    std::ios_base::sync_with_stdio (true); 
    std::string line; 
    unsigned dependency_var = 0; 
    while (getline (std::cin, line)) { 
     dependency_var += line.size(); 
    } 
    std::cout << dependency_var << '\n'; 
} 

void unsynced() { 
    std::ios_base::sync_with_stdio (false); 
    std::string line; 
    unsigned dependency_var = 0; 
    while (getline (std::cin, line)) { 
     dependency_var += line.size(); 
    } 
    std::cout << dependency_var << '\n'; 
} 

void usage() { std::cout << "one of (synced|unsynced|stdio), pls\n"; } 

int main (int argc, char *argv[]) { 
    if (argc < 2) { usage(); return 1; } 

    if (std::string(argv[1]) == "synced") test (synced); 
    else if (std::string(argv[1]) == "unsynced") test (unsynced); 
    else if (std::string(argv[1]) == "stdio") test (std_io); 
    else { usage(); return 1; } 

    return 0; 
} 

グラムで++ -O3、大きなテキストファイル：

cat testfile | ./a.out stdio 
... 
0.34 sec 

cat testfile | ./a.out synced 
... 
1.31 sec 

cat testfile | ./a.out unsynced 
... 
0.08 sec 

これはあなたのケースにどのように当てはまるかによって異なります。このおもちゃのベンチマークを修正し、テストを追加してください。 std::cin >> a >> b >> cとscanf ("%d %d %d", &a, &b, &c);のようなものです。私は最適化（すなわち、デバッグモードではない）を保証します。性能の差は微妙です。

あなたのニーズを満たしていない場合は、他の方法、たとえばファイル全体を最初に読み込む（パフォーマンスを向上させるかどうか）、またはメモリマップ（ポータブルではないソリューションですが、大きなデスクトップにはそれらがあります）。

---

更新

書式付き入力：scanfの対

#include <cstdio> 
#include <iostream> 

template <typename Test> 
void test (Test t) 
{ 
    const clock_t begin = clock(); 
    t(); 
    const clock_t end = clock(); 
    std::cout << (end-begin)/double(CLOCKS_PER_SEC) << " sec\n"; 
} 

void scanf_() { 
    char x,y,c; 
    unsigned dependency_var = 0; 

    while (!feof (stdin)) { 
     scanf ("%c%c%c", &x, &y, &c); 
     dependency_var += x + y + c; 
    } 

    std::cout << dependency_var << '\n'; 
} 

void unsynced() { 
    std::ios_base::sync_with_stdio (false); 
    char x,y,c; 
    unsigned dependency_var = 0; 
    while (std::cin) { 
     std::cin >> x >> y >> c; 
     dependency_var += x + y + c; 
    } 
    std::cout << dependency_var << '\n'; 
} 

void usage() { std::cout << "one of (scanf|unsynced), pls\n"; } 

int main (int argc, char *argv[]) { 
    if (argc < 2) { usage(); return 1; } 

    if (std::string(argv[1]) == "scanf") test (scanf_); 
    else if (std::string(argv[1]) == "unsynced") test (unsynced); 
    else { usage(); return 1; } 

    return 0; 
} 

結果ストリーム：

scanf: 0.63 sec 
unsynced stream: 0.41 

Answer 2

おそらく、scanfはストリームを使用するよりもいくぶん高速です。ストリームは多くの型安全性を提供し、実行時に書式文字列を解析する必要はありませんが、通常は過剰なメモリ割り当てを必要としないという利点があります（コンパイラと実行時によって異なります）。つまり、パフォーマンスが唯一の最終目標であり、クリティカルパスにいなければ、より安全な（より遅い）メソッドを本当に優先してください。

sscanf関数とのlexical_castのような文字列フォーマッタのパフォーマンスの詳細の多くに入り、それらが実行物事の種類を作っていたハーブサッター

http://www.gotw.ca/publications/mill19.htm

でここに書かれた非常においしい記事がありますゆっくりまたは迅速に。これは、CスタイルIOとC++スタイルの間のパフォーマンスに影響するようなものに類似しています。フォーマッタとの主な違いは、型の安全性とメモリ割り当ての数である傾向がありました。

Answer 3

通常、バッファリングされた入力が最も高速になります。あまり頻繁に入力バッファをフラッシュしなければならないほど、入力はより速くなります。詳しくは、this questionを参照してください。要するに、大きなバッファサイズのread（）は、あなたのOSの対応するシステムコールのほぼすぐ上にあるので、できるだけ速いです。