8

私は現在、隣接行列を含むいくつかのグラフ計算を行っており、そのすべてを少しずつ最適化する過程にあります。

最適化できると思う指示の1つは、元の形式のタイトルの指示です。

if ((adjMatrix[i][k] > 0) && (adjMatrix[k][j] > 0) && (adjMatrix[i][k] + adjMatrix[k][j] == w))

ただし、簡単にするために、タイトルに記載されているフォームに固執します。

if (a > 0 && b > 0 && a + b == c)

私が気に入らないのは>0の部分です（隣接行列であるため、初期の形式では0と1しか含まれていませんが、プログラムが進むにつれて、ゼロがなくなるまで2以降の数値に置き換えられます。

テストを行い、aとbの両方で> 0の部分を削除しましたが、大幅な改善が見られました。60088回の反復で、3762ミリ秒から2880ミリ秒に792ミリ秒の減少がありました。これは、元の時間の78％であり、私にとっては優れています。

だから私の質問は：C＃でこのようなステートメントを最適化して同じ結果を得る方法を考えられますか？たぶん、いくつかのビット演算または類似のもの、私はそれらにあまり精通していません。

たとえそれが適切でなくても、あなたの心を横切るあらゆる考えで答えてください。自分で速度テストを行い、結果をお知らせします。

編集：これは、自分のコンピューターで自分で実行するコンパイラー用です。私が今説明したことは、私が不満を言っている問題/ボトルネックではありません。現在の形式のプログラムは私のニーズには問題なく動作しますが、私はそれを前進させ、可能な限り基本的で最適化したものにしたいと思っています。これが少し明確になることを願っています。

編集私は完全なコードを提供することは有用なことだと信じているので、ここにありますが、下の太字で言ったことを覚えておいてください。ifステートメントに厳密に集中したいと思います。プログラムは基本的に隣接行列を取り、存在するすべてのルートの組み合わせを保存します。次に、いくつかの係数に従ってソートおよびトリミングされますが、これは含まれていません。

int w, i, j, li, k;
int[][] adjMatrix = Data.AdjacencyMatrix;
List<List<List<int[]>>> output = new List<List<List<int[]>>>(c);

for (w = 2; w <= 5; w++)
{
    int[] plan;

    for (i = 0; i < c; i++)
    {
        for (j = 0; j < c; j++)
        {
            if (j == i) continue;
            if (adjMatrix[i][j] == 0)
            {
                for (k = 0; k < c; k++) // 11.7%
                {
                    if (
                        adjMatrix[i][k] > 0 && 
                        adjMatrix[k][j] > 0 && 
                        adjMatrix[i][k] + adjMatrix[k][j] == w) // 26.4%
                    {
                        adjMatrix[i][j] = w;

                        foreach (int[] first in output[i][k])
                            foreach (int[] second in output[k][j]) // 33.9%
                            {
                                plan = new int[w - 1];
                                li = 0;

                                foreach (int l in first) plan[li++] = l;
                                plan[li++] = k;
                                foreach (int l in second) plan[li++] = l;

                                output[i][j].Add(plan);
                            }
                    }
                }

                // Here the sorting and trimming occurs, but for the sake of
                // discussion, this is only a simple IEnumerable<T>.Take()
                if (adjMatrix[i][j] == w)
                    output[i][j] = output[i][j].Take(10).ToList();
            }
        }
    }
}

プロファイラーの結果にコメントを追加すると、ビルドが最適化されます。

ちなみに、タイミングの結果はまさにこのコードで得られました（実行時間を劇的に増加させるソートとトリミングなしで）。私の測定に含まれている他の部分はありませんでした。このコードの直前にStopwatch.StartNew（）があり、直後にConsole.WriteLine（EllapsedMilliseconds）があります。

サイズについて考えたい場合、隣接行列には406行/列があります。つまり、基本的には、多くの反復を実行するfor-命令が組み合わされているだけなので、最適化のオプションはあまりありません。速度は今のところ問題ではありませんが、いつになるかを確認したいと思います。

そして、「別の部分を最適化する」問題を除外するために、この主題についても話し合う余地がありますが、この特定の問題については、抽象的な問題/概念としてこれに対する解決策を見つけたいと思います。私や他の人がC＃コンパイラがどのように機能し、ifステートメントと比較を処理するかを理解するのに役立つかもしれません。それがここでの私の目標です。

4

6 に答える 6

6

a>0 && b>0符号付き(a-1)|(b-1) >= 0変数aおよびbをに置き換えることができます。

同様に、式の左または右の部分が符号ビットを切り替えると、ビット単位またはで保持されるため、条件x == wはとして表現できます。すべてをまとめると、単一の比較として表現されます。(x - w)|(w - x) >= 0x != w(a-1)|(b-1)|(a+b-w)|(w-a-b) >= 0

あるいは、確率を昇順で並べることで、速度がわずかに向上する場合があります。

どちらがより可能性が高いです(a|b)>=0か(a+b)==w？

于 2012-10-15T17:14:35.743 に答える
4

C# がこのようなことをどの程度最適化するかはわかりませんが、 メモリを 2 回読み取らないように一時変数adjMatrix[i][k]に保存しようとすることはそれほど難しくありません。adjMatrix[k][j]それが何らかの形で物事を変えるかどうかを確認してください。

ここで算術演算と比較演算がボトルネックになっているとは信じがたいです。ほとんどの場合、メモリ アクセスまたは分岐です。理想的には、メモリーは直線的にアクセスする必要があります。より直線的にするために何かできることはありますか？

より具体的なものを提案するコードをもっと見るとよいでしょう。

更新:int[,]ギザギザの配列 ( ) の代わりに2 次元配列 ( ) を使用してみてくださいint[][]。これにより、メモリの局所性と要素のアクセス速度が向上する可能性があります。

于 2012-10-15T17:32:29.593 に答える
3

論理テストの順序は重要になる可能性があります（他の回答で述べたように）。短絡論理テスト (& の代わりに &&) を使用しているため、条件は左から右に評価され、最初に false であることが検出されると、プログラムは条件の評価を停止し、実行を継続します (ブロックを実行しifます)。falseしたがって、1 つの条件が残りの条件よりもはるかに可能性が高い場合、その条件を最初に実行し、次の条件を次に高い条件にする必要がありますfalse。

もう 1 つの優れた最適化 (いくつかの条件を単純に除外するのではなく、実際にパフォーマンスの向上をもたらしたのではないかと思います) は、配列から取得した値をローカル変数に割り当てることです。

adjMatrix[i][k]2 回 (および) を使用しadjMatrix[k][j]ているため、コンピューターは配列を掘り下げて値を取得する必要があります。代わりに、if ステートメントの前に、それらを毎回ローカル変数に設定し、それらの変数に対してロジック テストを実行します。

于 2012-10-15T17:31:29.033 に答える
1

関数を呼び出さない限り、条件を最適化しません。無意味です。ただし、本当にやりたい場合は、覚えておくと簡単なことがいくつかあります

何かがゼロであるかどうか (またはそうでないか)、最上位ビットが設定されているかどうか (またはそうでないか)、および比較 (== または !=) が本質的に a - b であるかどうかがチェックされ、そのゼロ (==0) かどうかがチェックされます。 (!=0)。したがって、a が符号なしの場合、a>0 は a!=0 と同じです。a が署名されている場合、a<0 はかなり良好 (これは最上位ビットのチェックを使用) であり、a<=0 よりも優れています。とにかく、これらのルールを知っているだけでも役に立ちます。

また、プロファイラーを起動すると、条件分岐に 001% の時間がかかることがわかります。何かあれば、条件を必要としないものを書く方法を尋ねる必要があります。

于 2012-10-15T18:04:45.580 に答える
1

この単純なステートメントがボトルネックになる可能性は低いと言う他の人に同意し、この特定の行の最適化を決定する前にプロファイリングを提案します. ただし、理論的な実験として、いくつかのことを行うことができます。

  1. ゼロチェック: のチェックa != 0 && b != 0は、おそらくa >= 0 && b >= 0. 隣接行列は非負であるため、これを安全に行うことができます。

  2. 並べ替え: テストのa + b == c方が速い場合は、最初にこのテストを使用してからa、b個別にテストしてください。加算および等価チェックはゼロチェックよりもコストがかかるため、これが高速になるとは思えませんが、特定のケースでは機能する可能性があります。

  3. 二重のインデックス作成を避ける: 結果の IL を ILDASM または同等のもので調べて、配列インデックスが 2 回ではなく 1 回だけ逆参照されていることを確認します。そうでない場合は、チェックの前にローカル変数に入れてみてください。

于 2012-10-15T17:50:43.070 に答える
0

ロジックを逆にすることを検討しましたか?

if (a > 0 && b > 0 && a + b == c)

次のように書き換えることができます。

if (a == 0 || b == 0 || a + b != c) continue;

ステートメントのいずれかが false の場合、ループ内で何もしたくないので、できるだけ早く中止するようにしてください (ランタイムがそれほどスマートである場合は、そう思います)。

最初のステートメントが true の場合、他のステートメントをチェックする必要がないため、最も重い操作を最後にする必要があります。追加が最も重い部分だと思いましたが、プロファイリングすると別の話になるかもしれません.

ただし、これらのシナリオを自分でプロファイルしたことはありません。そのような些細な条件では、欠点になることさえあります。あなたの調査結果を見るのは興味深いでしょう。

于 2012-10-15T18:22:53.377 に答える