1

非常に高速な入出力が必要な問題を解決しています。より正確には、入力データ ファイルは最大 15 MB になります。整数値を読み取り/印刷する高速な方法はありますか。

注:役立つかどうかはわかりませんが、入力ファイルの形式は次のとおりです。

  • 1 行目: 数値 n
  • 行 2..n+1: 3 つの数値 a、b、c。
  • n+2 行目: 数値 r
  • 行 n+3..n+4+r: 4 つの数字 a、b、c、d

注2：入力ファイルはstdin.

編集:次のようなものは十分に高速ではありません:

void fast_scan(int &n) {
  char buffer[10];
  gets(buffer);
  n=atoi(buffer);
}

void fast_scan_three(int &a,int &b,int &c) {
  char buffval[3][20],buffer[60];
  gets(buffer);
  int n=strlen(buffer);
  int buffindex=0, curindex=0;
  for(int i=0; i<n; ++i) {
    if(!isdigit(buffer[i]) && !isspace(buffer[i]))break;
    if(isspace(buffer[i])) {
      buffindex++;
      curindex=0;
    } else {
      buffval[buffindex][curindex++]=buffer[i];
    }
  }
  a=atoi(buffval[0]);
  b=atoi(buffval[1]);
  c=atoi(buffval[2]);
}
4

5 に答える 5

3

一般的な入出力最適化の原則は、可能な限り少ないI / O操作で、可能な限り多くのデータの読み取り/書き込みを実行することです。

したがって、パフォーマンスを意識したソリューションは通常、次のようになります。

  1. デバイスからすべてのデータをバッファに読み込みます（上記の原則を使用）
  2. 結果のデータを生成するデータを処理して、（場所または別の）バッファに移動します
  3. バッファからデバイスへの出力結果（上記の原理を使用）

std::basic_istream::readたとえば、データを1行ずつ入力する代わりに、大きなチャンクでデータを入力するために使用できます。出力に関する同様のアイデア-結果としてラインフィードシンボルを手動で追加して単一の文字列を生成し、それを一度に出力します。

于 2012-10-25T17:43:02.783 に答える
1

物理I/O操作のオーバーヘッドを最小限に抑えたい場合は、メモリマップトファイルと呼ばれる手法でファイル全体をメモリにロードします。ただし、パフォーマンスが大幅に向上することはないと思います。ほとんどの場合、解析にはかなりのコストがかかります。

于 2012-10-25T18:05:18.557 に答える
0

複数の入力行をバッファーに入れ、それらを分割してから、異なるスレッドで同時に解析します。

于 2012-10-25T18:01:47.780 に答える
0

スレッドの使用を検討してください。スレッド化は多くのことに役立ちますが、これはまさにスレッドの発明を動機付けた種類の問題です。

基本的な考え方は、入力、処理、および出力を分離して、これらのさまざまな操作を並行して実行できるようにすることです。正しく実行すると、大幅なスピードアップが見られます。

1つのスレッドで純粋な入力に近づけます。行を行のバッファに読み込みます。2番目のスレッドにすばやく事前解析を実行させ、生の入力をブロックに編成します。解析する必要があるのは、トリプルを含む行の数を含む行と、クワッドを含む行の数を含む行の2つです。このスレッドは、生の入力をブロックに形成しますが、それでもほとんどがテキストです。3番目のスレッドは、トリプルとクワッドを解析し、入力を完全に解析された構造に再形成します。データは独立したブロックに編成されているため、この3番目の操作の複数のインスタンスを使用して、コンピューター上の複数のプロセッサーをより有効に活用できます。最後に、他のスレッドはこれらの完全に解析された構造で動作します。注：これらの操作のいくつかを組み合わせた方がよい場合があります。

于 2012-10-25T18:05:28.117 に答える
0

わずか15MBです。全体をメモリ バッファに丸呑みしてから、解析します。解析は、およそ次のようになります。

#define DIGIT(c)((c) >= '0' && (c) <= '9')
while(*p == ' ') p++;
if (DIGIT(*p)){
    a = 0;
    while(DIGIT(*p){
        a *= 10; a += (*p++ - '0');
    }
}
// and so on...

この種のコードは、睡眠中に書けるはずです。

それが よりも速いかどうかはわかりませんがatoi、数字の始まりと終わりを理解するのに苦労していません。scanfフォーマット文字列を理解するのに9ヤードかかるので、私は近づきません。

この全体を 1000 回ループして実行し、いくつかのスタック サンプルを取得すると、ファイルの読み取りと出力の生成 (言及されていません) のほぼ 100% が費やされていることがわかります。あなたはそれを打ち負かすことはできません。実際の解析にかなりの時間が費やされていることがわかった場合は、重複した I/O を実行できる可能性がありますが、マシンが非常に遅いか、I/O が非常に高速である必要があります (ソリッド ステート ドライブの場合など)。その前に意味があります。

于 2012-10-25T19:44:49.180 に答える