6

cachegrind を使用して、Linux で計算負荷の高い C++ プログラムのプロファイリングを行いました。驚いたことに、私のプログラムのボトルネックはソートや計算方法にあるのではなく、入力の読み取りにあることがわかりました。

プロファイラーの結果を誤解している場合に備えて、cachegrind のスクリーンショットを次に示します ( 「 」を参照 scanf())。

プロファイラーの結果

scanf()私の実行時間の 80.92% がこれにかかっていると言うのが正しいことを願っています。

cin >> int_variable_here次のように、を使用して入力を読み取ります。

std::ios_base::sync_with_stdio (false); // Supposedly makes I/O faster
cin >> NumberOfCities;
cin >> NumberOfOldRoads;
Roads = new Road[NumberOfOldRoads];

for (int i = 0; i < NumberOfOldRoads; i++)
{
    int cityA, cityB, length;    

    cin >> cityA;
    //scanf("%d", &cityA);    // scanf() and cin are both too slow
    cin >> cityB;
    //scanf("%d", &cityB);
    cin >> length;
    //scanf("%d", &length);

    Roads[i] = Road(cityA, cityB, length);
}

この入力読み取りコードに問題が見つからない場合は、入力を読み取るためのより高速な方法をお勧めできますか? やってみようと思ってgetline()ます(返事待ちながらやってます)。私の推測では、 getline() はより少ない変換を行う必要があり、ストリームを解析する回数が少ないため、より高速に実行される可能性があります (私の推測ですが、最終的には文字列を整数として解析する必要があります)。

「遅すぎる」とは、これが一定時間 (90 秒だと思います) 後にタイムアウトになる大きな宿題の一部であることを意味します。プログラムの残りの大部分を意図的にコメントアウトしましたが、それでもタイムアウトしたため、ボトルネックがここにあると確信しています。インストラクターが私のプログラムで実行するテスト ケースはわかりませんが、巨大な入力ファイルである必要があります。では、入力を最速で読み取るには何を使用すればよいでしょうか?

入力形式は厳密です: 行ごとに 1 つのスペースで区切られた 3 つの整数、多くの行の場合:

サンプル入力:

7 8 3
7 9 2
8 9 1
0 1 28
0 5 10
1 2 16

Road各行の整数からa を作成する必要があります。

また、私のプログラムでは、入力が標準入力 ( myprogram < whatever_test_case.txt) にリダイレクトされることに注意してください。特定のファイルを読んでいません。から読んだところcinです。

アップデート

スラバの方法を使用する：

入力の読み取りにかかる時間は短くなっているようですが、まだタイムアウトしています (入力の読み取りが原因ではない可能性があります)。Slava のメソッドはRoad() ctor(から 2 つ下main) に実装されています。そのため、80% ではなく 22% の時間がかかります。SortRoadsComparator()2600万回ということなので最適化を考えています。

ここに画像の説明を入力

コンパレータ コード:

// The complexity is sort of required for the whole min() max(), based off assignment instructions
bool SortRoadsComparator(const Road& a, const Road& b)
{
    if (a.Length > b.Length) 
        return false;

    else if (b.Length > a.Length) 
        return true;

    else
    {
        // Non-determinism case
        return ( (min(a.CityA, a.CityB) < min(b.CityA, b.CityB)) ||
            (
            (min(a.CityA, a.CityB) == min(b.CityA, b.CityB)) && max(a.CityA, a.CityB) < max(b.CityA, b.CityB)                                     
            )
            );
    }
}

enhzflep の方法を使用する

ここに画像の説明を入力

解決したと考える

ボトルネックが入力の読み取りになくなったため、この問題は解決したと考えます。Slavaの方法は私にとって最速でした。

4

3 に答える 3

4

ストリームは非常に遅いことをよく知っています。大きな驚きではありませんが、ローカリゼーションや条件などを処理する必要があります。考えられる解決策の 1 つは、 std::getline( std:::cin, str ) によってファイルを 1 行ずつ読み取り、次のような方法で文字列を数値に変換することです。これ：

std::vector<int> getNumbers( const std::string &str )
{
   std::vector<int> res;
   int value = 0;
   bool gotValue = false;
   for( int i = 0; i < str.length(); ++i ) {
      if( str[i] == ' ' ) {
         if( gotValue ) res.push_back( value );
         value = 0;
         gotValue = false;
         continue;
      }
      value = value * 10 + str[i] - '0';
      gotValue = true;
   }
   if( gotValue ) res.push_back( value );
   return res;
}

私はこのコードをテストせず、アイデアを示すために書きました。入力にスペースと数字以外は何も期待していないので、入力を検証しません。

並べ替えを最適化するには、まずシーケンス全体を並べ替える必要があるかどうかを確認する必要があります。コンパレータの場合、メソッド getMin() getMax() を記述し、その値をオブジェクトに格納します (常に計算しないようにします)。

bool SortRoadsComparator(const Road& a, const Road& b)
{
    if( a.Length != b.Length ) return a.Length < b.length;
    if( a.getMin() != b.getMin() ) return a.getMin() < b.getMin();
    return a.getMax() < b.getMax();
}

現在のコンパレータがどのように正しく機能するかを理解していれば。

于 2013-02-23T04:07:46.673 に答える
3

Slava が言うように、ストリーム (つまり cin) は、パフォーマンス (および実行可能ファイルのサイズ) の点で絶対的な豚です。

次の 2 つの方法を検討してください。

start = clock();
std::ios_base::sync_with_stdio (false); // Supposedly makes I/O faster
cin >> NumberOfCities >> NumberOfOldRoads;
Roads = new Road[NumberOfOldRoads];
for (int i = 0; i < NumberOfOldRoads; i++)
{
    int cityA, cityB, length;
    cin >> cityA >> cityB >> length;
    Roads[i] = Road(cityA, cityB, length);
}
stop = clock();
printf ("time: %d\n", stop-start);

と

start = clock();
fp = stdin;
fscanf(fp, "%d\n%d\n", &NumberOfCities, &NumberOfOldRoads);
Roads = new Road[NumberOfOldRoads];
for (int i = 0; i < NumberOfOldRoads; i++)
{
    int cityA, cityB, length;
    fscanf(fp, "%d %d %d\n", &cityA, &cityB, &length);
    Roads[i] = Road(cityA, cityB, length);
}
stop = clock();
printf ("time: %d\n", stop-start);

各方法を 5 回実行すると (1,000,000 エントリの入力ファイル + 最初の 2 つの「制御」行)、次の結果が得られます。

  1. stdio 8291、8501、8720、8918、7164 (平均 8318.3) と同期しないように指示なしでcin を使用する

  2. stdio 4875、4674、4921、4782、5171 (平均 4884.6) と同期しない方向でcinを使用する

  3. fscanf 1681、1676、1536、1644、1675 を使用 (平均 1642.4)

したがって、明らかに、sync_with_stdio(false) 方向が役立つことがわかります。また、fscanf が cin を使用する各アプローチに勝っていることもわかります。実際、fscanf アプローチは、より優れた cin アプローチよりもほぼ3 倍高速であり、stdio との同期を避けるように指示されていない場合、cinよりもなんと5 倍高速です。

于 2013-02-23T05:30:43.870 に答える
1 
inline void S( int x ) {
x=0;
while((ch<'0' || ch>'9') && ch!='-' && ch!=EOF) ch=getchar_unlocked();
if (ch=='-')
sign=-1 , ch=getchar_unlocked();
    else
sign=1;
do
x = (x<<3) + (x<<1) + ch-'0';
while((ch=getchar_unlocked())>='0' && ch<='9');
x*=sign;
}

この関数は、任意のタイプの数値入力に使用できます。パラメーターのタイプを変更するだけです。これは、std scanf よりもかなり高速に実行されます。

もっと時間を節約したい場合は、fread() と fwrite() を使用するのが最善ですが、その場合は自分で入力を操作する必要があります。時間を節約するには、fread() を使用して、1 回の呼び出しで標準入力ストリームから大量のデータを読み取る必要があります。これにより、I/O 呼び出しの数が減少するため、時間に大きな違いが見られます。

于 2013-02-23T04:29:04.343 に答える