0

C++ を使用して「標準 stdin プロシージャ」を使用するコンテスト用のプログラムを作成しています。取り込まれた最初の行は、それ以降の入力として期待される行数 (x) を示します。これらの入力行は、文字列、整数、またはその 2 つの組み合わせであり、各行にはスペースで区切られた正確に 2 つの要素が含まれます。現時点では、次のような方法で各行を 1 つずつ取り込んでいます (次の行を要求する前に情報を処理しています)。

  string initial;
  getline (cin,initial);
  istringstream stringStream (initial);
  vector<string> parsedString;
  vector<int> data;
  char splitToken = ' ';
  while ( !stringStream.eof() )
  {
    string subString;
    getline( stringStream, subString, splitToken);
    parsedString.push_back( subString );
  }

  for (int i = 0; i <parsedString.size(); i++)
  {
    string temp = parsedString[i];
    int intTemp = atoi(temp.c_str());
    data.push_back(intTemp);
  }
  unsigned int n = data[0];
  unsigned int m = data[1];

この特定のケースでは、受信データが 2 つの整数になることはわかっていますが、常にそうとは限りません。アプローチを変更するか (おそらく、期待される数を知った後にすべての入力行を一度に取得する)、または組み込みの C++ 関数を使用して入力行を分割することにより、コードを高速化する方法があるかどうか疑問に思っていました。それらを構成する 2 つの要素にスペースを入れます。

ありがとう

4

3 に答える 3

1

わかりました、他のアプローチについて話したい場合は、ここに別のアプローチがあります：文字列で重く動作するほとんどすべてのコードの大きな（パフォーマンス）問題、コピー操作がたくさんある...素朴なアプローチ（使用初心者による）文字列またはメモリバッファからsmthを検索/解析/抽出するときに、多くの一時的な文字列を作成することです...

別の方法（ソースバッファの存続期間が許す場合）は、ソース文字列の特定の部分をコピーせずに、バッファからデータを検索、解析、または抽出することです。そのためには、boost::rangeライブラリとboost::iterator_rangeクラスを（boost string_algoと組み合わせて）使用できます。このようにして、通常の検索/解析タスクを実行し、部分的な文字列のコピーを回避できます。

私の経験からの一例：少し前に（パフォーマンステストのために）私の同僚が同じ構成パーサーの3つのバージョンを作成しました（構成ファイルは約数メガバイトでした）：

  • を使用してstd::string::find
  • を使用してboost::tokenizer
  • とboost::iterator_range

結果は驚くべきものでした：

  • -O0最適化のstd::string::find勝利（ベースのパーサーの約3倍boost::tokenizerおよび約5倍）iterator_range
  • しかし、-O3ではすべてが変わりました：boost::iterator_range絶対的な勝者でした！（約12倍以上std::string::find！）

結果は非常に予測可能です：高度にテンプレート化されたコードboost::string_algoや友人も高度に非難されました...

それが私が個人的にboost::iterator_range文字列の解析に使用するのが好きな理由です...

したがって、すべてを（できるだけ多く）1つに読み取ることをお勧めしますstd::string（std::vector<char>より良いものは、メモリの隣接性が保証されているためread()、コンテナに直接ストリームすることができます）またはstd::deque<char>、を使用boost::string_algoしboost::iterator_rangeて解析します。ソース文字列から一時的な場所への（役に立たない）コピーを避けてください...またboost::lexical_cast、数値の変換（または独自の範囲対応数値コンバーター）にも使用してみてください

もう1つのアドバイス：メモリ（多くの場合）の割り当てを避けるようにしてください-それは本当に重い操作です。rserve()保存したいデータの可能なサイズについての手がかりがある場合は、コンテナーのメンバーを使用します。そして最後に、（通常はばかげた）デフォルトのアロケータではなく、カスタムの（トリッキーな）アロケータで遊んでみてください。

C ++ 11ではstd::string、メモリの隣接性が保証されていることに注意std::vectorしてください。

于 2013-01-24T00:25:02.903 に答える
1

通常、C++ で入力を読み取るイディオムは、次のようなものです。

std::ios_base::sync_with_stdio(false); //tell iostreams to be fast
int number_of_lines;
std::cin >> number_of_lines;
if (!std::cin) *ERROR*;

for( ; number_of_lines>0; --number_of_lines) {
    unsigned n, m;
    std::cin >> n >> m;
    if (!std::cin) *ERROR*;
    //process n and m here
}

「これらの入力行は、文字列、整数、またはその 2 つの組み合わせにすることができます」とあなたは言いますが、どれがどれであるかをどうやって知るのでしょうか? 上記のコードは、すべてが数値であると想定しています。型がわからない場合、入力は役に立たないからです。

于 2013-01-24T00:10:59.927 に答える
0

多くのシステム (Linux 上の GCC を含む) では、C++ I/O ストリームが非常に遅くなります。速度が主な関心事である場合は<stdio.h>、たとえばscanf()and (さらに高速:) を使用getchar()し、次のステート マシンのように手動で解析を行います。

int c;
int state = 0;
while ((c = getchar()) >= 0) {
  switch (c) {
   case ' ': case '\t':
    ...;
    ... if (state == ...) { ...; state = ...; }
    break;
   case '\n':
    ...;
    break;
   default:
    ...;
  }
}

データのコピーはできるだけ少なくしてください。(たとえば、質問でstring temp = ...は不要なコピーを行いますが、これは参照を使用して削除できstring &temp = ...ますc:将来的にコピーまたは移動します。

于 2013-01-24T00:11:46.177 に答える