iostreamのパフォーマンスの問題は、アイドル状態の問題ではありません。 特に、コンソールI / Oパフォーマンスの問題は、優れたアルゴリズムを使用しても、I / Oだけで時間を逃すことができないスポーツプログラミングシステムで発生する可能性があります。 また、科学データをテキスト形式で処理するときにこの問題が発生しました。
今日の投稿のコメントでは、iostreamsの遅さについての議論がありました。 特に、 Freopenの書き込み
cinを読んで横にある最適化を見るのは面白いです:)
そしてaesamsonはそのような推薦をします
* nixの場合はgetchar_unlocked（）に、それ以外の場合はgetchar（）に置き換えることができます。
getchar_unlocked> getchar> scanf> cin、「>」は高速を意味します。
この投稿では、いくつかの神話を払拭して確認し、いくつかの推奨事項を示します。
この投稿のすべての測定値は、キーを使用してコンパイルされたGCC 4.9.1コンパイラーを備えたUbuntu 14.10システムのものです
g++ -Wall -Wextra -std=c++11 -O3
打ち上げは、Intel Core2 Duo P8600プロセッサー（2.4 GHz）を搭載したラップトップで実行されました。
問題の声明
UNIXのようにスポーツプログラミングでは、通常、入力データが入力ストリームに送られます。 したがって、タスク：
入力ストリーム（stdin）は、1行に1つずつ、多くの負でない整数を受け取ります。 プログラムは、最大入力数を出力する必要があります。
入力データを形成します
seq 10000000 > data
データファイルには、合計で76メガバイトの1000万個の連続した整数を書き込みました。
このようなプログラムを実行します
time ./a.out < data
それでは、始めましょう。
1. scanf
古き良きscanfを使用して問題を解決しましょう。
int max_scanf() { int x; int max = -1; while (scanf("%d", &x) == 1) { max = std::max(x, max); } return max; }
scanfを使用する場合、戻り値を常に確認することを忘れないことが重要です。これは、実際に読み取られて入力される引数の数です（-Wallを指定したGCCはこれを思い出させます）。 この場合、読み取りに成功すると、戻り値は1になります。
主な機能
int main() { std::cout << max_scanf() << std::endl; return 0; }
稼働時間： 1.41 c
2. Naive std::cin
次に、iostreamを使用して最も簡単な方法で問題を解決します。
int max_iostream(std::istream & f) { int x; int max = -1; while(f >> x) max = std::max(x, max); return max; }
動作時間： 4.41秒
わあ！ スレッドはscanfの3倍遅い！ つまり、iostreamの速度は本当に役に立たないことがわかりますか？
3. Fast std::cin
実際、状況を修正するには、プログラムに1行追加するだけで十分です。 メイン関数の最初に、以下を挿入します：
std::ios::sync_with_stdio(false);
これはどういう意味ですか？
プログラムがiostreamとstdioを混在させるために、この同期が導入されました。 デフォルトでは、標準ストリーム（
std::cin, std::cout, std::cerr
...）で作業する場合、データが混同されないように、各I / O操作の後にバッファーがフラッシュされます。 iostreamのみを使用する場合は、この同期をオフにすることができます。 詳細はcppreferenceをご覧ください 。
稼働時間： 1.33 c
完全に異なる問題！ さらに、scanf よりも高速です！ つまり、すべてがそれほど悪いわけではありません。 iostreamの利点には、使いやすさ、型の安全性、簡単なエラー処理が含まれます。
std :: cinを使用する後続のオプションはすべて、この最適化を使用します。
4.ナイーブstd::istringstream
標準ライブラリには、ファイルからの入力に加えて、同じインターフェイスを持つ文字列からの入力用のクラスも用意されています。 それがどれほど遅いか見てみましょう。 入力ストリームから1行を読み取り、
std::istringstream
を使用して解析し
std::istringstream
。
int max_iostream_iss(std::istream & f) { int x; int max = -1; std::string line; while (std::getline(f, line)) { std::istringstream iss(line); if(! (iss >> x)) break; max = std::max(x, max); } return max; }
稼働時間： 7.21 c
とても遅い！
5. std::istringstream
再利用std::istringstream
驚くかもしれませんが、
istringstream
最も遅いのはその作成です。 そして、入力行ごとに再作成します。 同じオブジェクトを再利用してみましょう：
int max_iostream_iss_2(std::istream & f) { int x; int max = -1; std::string line; std::istringstream iss(line); while (std::getline(f, line)) { iss.clear(); // iss.str(line); // if(! (iss >> x)) break; max = std::max(x, max); } return max; }
ステータスフラグをクリアするにはclearを、読み取り元の新しいバッファを設定するにはstrを2回呼び出す必要があることに注意してください。
稼働時間： 2.16 c
これは別の問題です。 これは、
std::cin
（データがストリームクラスを2回通過する）から直接読み取るよりも遅いと予想されますが、壊滅的ではありません。
6.さらに速くしたい！ （getchar / getchar_unlocked）
パフォーマンスがまだ不足している場合はどうなりますか？ 下位レベルのI / Oとカスタムパーサーを使用します。 前述のトピックへのコメントで、 aesamsonは整数の最も単純なパーサー（おそらくStackOverflowから取られた）を実装するコードの例を示しました。 入力ストリームから
getchar_unlocked
は、
getchar_unlocked
が使用されます
getchar_unlocked
のスレッドセーフバージョンです。 余分な文字のスキップとファイル処理の最も簡単な終了を追加しました：
bool read_int_unlocked(int & out) { int c = getchar_unlocked(); int x = 0; int neg = 0; for (; !('0'<=c && c<='9') && c != '-'; c = getchar_unlocked()) { if (c == EOF) return false; } if (c == '-') { neg = 1; c = getchar_unlocked(); } if (c == EOF) return false; for (; '0' <= c && c <= '9' ; c = getchar_unlocked()) { x = x*10 + c - '0'; } out = neg ? -x : x; return true; } int max_getchar_unlocked() { int x; int max = -1; while(read_int_unlocked(x)) max = std::max(x, max); return max; }
動作時間：
getchar
0.82秒、
getchar_unlocked
0.28秒！
とても良い結果です！ また、スレッドセーフのためのロックが原因でスローダウンがどれほど大きいかを確認できます。
しかし、このアプローチには欠点があります-使用されるすべてのデータ型のパーサーを記述する必要があり（浮動小数点数でも簡単ではありません）、エラー処理の複雑さ、
getchar_unlocked
の場合のスレッド
getchar_unlocked
。 または、
re2c
、
boost::Spirit::Qi
などのパーサージェネレーターを使用して試すこともできます。 （それらの多く）。
7. C ++ 11： std::stoi
C ++ 11に登場した関数
std::stoi/std::stol/std::stoll
についてのコメントを思い出してくれたLol4t0に感謝します。 getlineを使用して一度に1行ずつ読み取り、次にstolを使用して解析します。 コードは次のようになります。
int max_stoi(std::istream & f) { int max = -1; std::string line; while (std::getline(f, line)) { int x = std::stoi(line); max = std::max(x, max); } return max; }
稼働時間： 1.04 c
これは、整数を読み取るための最速の標準的な方法です。 （浮動小数点数については、同様の関数stof / stodがあります）。
8.ボーナス：大きなブロックで読む+ブースト::スピリット
最速のオプションを作成してみましょう。 入力データを大きなブロックで読み取り、 Boost :: Spirit :: Qiを使用して解析します。これは、非常に高速なパーサーのジェネレーターであると主張しています。 これはコンパイル時のジェネレーターです。BNFに似た表記でC ++の文法を記述し、コンパイル中にパーサーメタプログラミングマジックを使用して生成されます。
コード（注意、ブースト、メタプログラミングが検出されました！）
#include <boost/spirit/include/qi.hpp> #include <boost/spirit/include/phoenix_core.hpp> #include <boost/spirit/include/phoenix_operator.hpp> #include <boost/spirit/include/phoenix_statement.hpp> template <typename Iterator> Iterator max_parser(Iterator first, Iterator last, int& max) { namespace qi = boost::spirit::qi; namespace ascii = boost::spirit::ascii; namespace phoenix = boost::phoenix; using qi::int_; using qi::_1; using ascii::space; using phoenix::ref; using phoenix::if_; using qi::eoi; using qi::lexeme; bool r = qi::phrase_parse(first, last, // Begin grammar ( *lexeme[int_ >> (!eoi)][if_(_1 > ref(max))[ref(max) = _1]] ) , // End grammar space); return first; } int max_spirit(std::istream & f) { size_t chunk_size = 1 << 20; std::unique_ptr<char[]> buffer(new char[2*chunk_size]); char * middle = buffer.get() + chunk_size; char * begin = middle; int max = -1; while(true) { f.read(middle, chunk_size); if (f.gcount() == 0) break; char * end = middle + f.gcount(); char * last = max_parser(begin, end, max); if (last < middle) break; // copy the remaining data just before the middle: begin = middle - (end - last); std::copy(last, end, begin); } return max; }
動作時間： 0.18秒
これは記録です！
結果とヒント
作業時間：
| いや | 方法 | GCC 4.9.1 | clang 3.5.0 + libc ++ | GCC 100M * |
|---|---|---|---|---|
| 1 | scanf | 1.41 | 1.48 | |
| 2 | std :: cin | 4.41 | 13.30 | |
| 3 | std :: cinおよびstd :: ios :: sync_with_stdio（false） | 1.33 | 13.24 | |
| 4 | std :: istringstream | 7.21 | 9.16 | |
| 5 | std ::再利用可能なistringstream | 2.16 | 7.92 | |
| 6a | ゲッチャー | 0.82 | 0.84 | 9.14 |
| 6b | getchar_unlocked | 0.28 | 0.26 | 2.94 |
| 7 | std :: getline + std :: stoi | 1.04 | 3.53 | 10.8 |
| 8 | ビッグブロック+ブースト::スピリット | 0.18 | 1.67 | 1.90 |
*-1億個のファイル（ファイルサイズ848メガバイト）の測定。
推奨事項：
- C ++ 11では、ストリームから数値を読み取る最も速い標準的な方法は
std::getline
+std::stol
（標準ストリームstd::cin
場合はstd::stol
sync_with_stdio(false)
と組み合わせて）です。 このメソッドはscanfよりも著しく高速で、getcharメソッドに次いで2番目です。 -
std::cin/std::cout
を高速化するには、std::ios::sync_with_stdio(false);
この場合、速度はscanfと同等以上になります。 （同じスレッドでストリーミング操作とstdio操作を混在させないでください） - Istringstreamのコンストラクターは非常に低速です。 したがって、ストリームオブジェクトを再利用すると、パフォーマンスが大幅に向上する可能性があります。
-
getchar_unlocked
（またはスレッドセーフが必要な場合はgetchar
）とカスタムパーサーを使用して、より高いパフォーマンスを実現できます。 - データを大きなチャンクで読み取り、メモリ内で排他的に動作する場合、パフォーマンスをさらに向上させることができます。
注意！ 結果は特定のシステムでのみ有効であり、他のシステムでは大きく異なる場合があります！ 特に、私はすぐにclang + libc ++を試してみましたが、スレッドのパフォーマンスははるかに悪くなりました（libstdc ++とclangおよびgccを使用してもほぼ同じ結果が得られました）。 ヒントを適用するときは、必ずパフォーマンスをテストしてください！ （そして、理想的には、他の人が利用できるようにコメントであなたのシステムの結果を報告してください）。 完全なコードはこちらから入手できます 。
更新1. Lol4t0のアドバイスにより、メソッド番号7が追加されました。
更新2. clang + libc ++のランタイムがテーブルに追加されました（バージョン3.5.0、同じシステムで実行されました）。 スレッドのパフォーマンスが非常に低く、さらに、同期をオフにするトリックが機能しないことがわかります。 その結果、stoiはscanfの2倍遅くなります。
更新3。オプション番号8を追加しました。大きなブロックで読み取り、Boost :: Spiritを使用して解析します。 そしてこれがチャンピオンです！