0

私は最近、DNA 鎖の 2 つのシーケンス (長くなる可能性があります) 間の類似性 (変更された編集距離) を計算する動的プログラムを作成しました。

私のコードは次のようなものです（割り当てであるため、実際のコードではありません）：

while(!file.eof){
   string line;
   int sizeY, sizeX;

   //get first strand
   getline(db, line)

   //second strand
   getline(db, line)

   double ** ary = new double[sizeY];
   //loop to initialize array

   for(i to sizeY)
   {
      for(i to sizex)
      {
            pair<string,string> p,d;
            p.first = "A";
            p.second = "T";
            d.first = "G";
            d.second = "C";
            //do some comparisons
      }
   }
}

上記のコードは、約 2400 行のファイルで完了するのに約 40 分かかります。p,d と代入のペアをネストされた for ループの外に移動し、まったく同じファイルを実行すると、約 1 分で完了します。

パフォーマンスはほぼ同じであると他のスレッドで読みました。また、-O2 でコンパイルしました。

上記のコードが非常に遅いのはなぜですか?

4

4 に答える 4

2

内部ループの反復ごとに発生する必要があるさまざまな割り当て/割り当て解除を検討してください。

  1. ペア オブジェクトをスタックに割り当てます
  2. 4 つの空の文字列を割り当てます。おそらくそれぞれがヒープに 1 バイト割り当てられます
  3. 4 つのヒープ割り当て解除と新しい割り当てが必要になる可能性のある 4 つの文字列割り当て
  4. 4 つのヒープ割り当て解除を含む文字列の破棄
  5. ペアオブジェクトの破棄

合計 8 回のヒープ割り当てと別の 8 回の割り当て解除 (または 4/4 の最良のケース) であるスタック割り当て (比較的安価なはずです) を無視します。これがデバッグ ビルドの場合、各ヒープ操作をチェックする際に追加のオーバーヘッドが発生する可能性があります。

sizeX/sizeY 定数が 2400 の場合、合計9200 万回のヒープ操作を行っています。運が良ければ、ループごとに同じサイズのオブジェクトを割り当てているため、これらの操作のそれぞれにほぼ同じ時間がかかります。運が悪いと、ヒープの断片化が原因で、一部のヒープ操作の実行にかなりの時間がかかる場合があります。

あなたが見つけたように、明白な解決策は、変数の定義と代入をループの外に置くことです。ある時点でペアの値がループ内で上書きされる場合にのみ、ペアの値を再割り当てする必要があります。

于 2011-06-02T02:22:12.600 に答える
0

一般的な回答: gcc (つまり g++) を使用しているようです。いつでも g++ -S [stuff] を実行して、G++ がコードに対して何を行っているかを確認できます (アセンブリを十分に読み取ることができると仮定します)。

具体的な回答: 違いが 40 回あることに驚いていますが、あなたのコードでは、ループを終了するたびに create_new_pair を 2 回呼び出す必要があります (そして、"古いペアを解放しますが、それがスタック上にあることを考えると、それは私が思っていたほど難しくはないか、少なくとも私はそれを見ていないと思います... Gccからコードを読み取ることは、読み取るよりもはるかに簡単でしたC++ コードは現時点で)

于 2011-06-02T01:55:09.497 に答える
0

おそらく変数がオブジェクトだからです。p と d はプリミティブ型ではないため、コンパイラがコンストラクタとデストラクタをインライン化しない限り (-O2 の代わりに -O3 を使用すると発生する可能性があります)、2 つの std::pair (結果として 4 つの std) を構築および破棄します。 ::string) 各反復。プリミティブ変数 (int など) の場合、インライン最適化が有効になっていない場合でも、コンパイラはこれを最適化できます。

編集: std::string は内部的にヒープ割り当てを使用するため、インラインでさえそれらの割り当てを最適化しないことに注意してください (ただし、インラインでオーバーヘッドを節約できます)。-O3 を指定した int の std::pair の場合、パフォーマンスはループの内外で同じになります。

于 2011-06-02T02:57:21.107 に答える
-1

優れたコンパイラ (少なくとも平凡な最適化を行う) を備えたコンパイル済み言語では、ループ内で宣言された変数を持つことは決して「敗者」になることはなく、多くの場合 (特に適度な最適化のみを行うコンパイラの場合) は「勝者」になります。

ただし、インタープリター言語では異なる可能性があります。ループを通過するたびに、インタープリターは変数の場所を割り当てる必要があり、それにはコストがかかる可能性があります。

また、スタックに変数を割り当てるのにコストがかかる、設計が不十分なコンパイル済み環境では、「敗者」の状況になる可能性もあります。

ただし、これらのシナリオのいずれでも、40:1 の違いを説明するのは難しいでしょう。省略されたコードには、いくつかの重要な手がかりが含まれているのではないかと思います。

[ああ、再読すると (そしておそらくポスターの再編集で)、単に変数の宣言ではなく、オブジェクトの作成がループの外に移動していることがわかります。]

于 2011-06-02T01:49:31.503 に答える