0

ゼロから n までの 3 つのネストされたループがあります。n は大きな数で、12000 番目前後です。これら 3 つのループは 2DList で動作します。それは実際にはフロイドアルゴリズムです。これらの大きなデータでは時間がかかりますが、それを改善する方法を教えていただけますか? ありがとう（私の英語でごめんなさい:)）

 List<List<int>> distance = new List<List<int>>();

 ...

  for (int i = 0; i < n; i++)

        for (int v = 0; v < n; v++)

            for (int w = 0; w < n; w++)
            {
                if (distance[v][i] != int.MaxValue &&
                    distance[i][w] != int.MaxValue)
                {
                    int d = distance[v][i] + distance[i][w];
                    if (distance[v][w] > d)
                        distance[v][w] = d;
                }

            }
4

5 に答える 5

3

場合によっては、if ステートメントの最初の部分をdistance[v][i] != int.MaxValue反復の外に移動しwて、オーバーヘッドを減らすことができます。ただし、値が int.MaxValue にある頻度はわかりません

于 2013-04-17T12:32:48.233 に答える
2

フロイドのアルゴリズムを変更することはできません。その複雑さは固定されています (そして、エッジの重みが負のグラフですべてのペアごとの最短パス距離を見つけるという一般的な問題に対する最も効率的なソリューションであることが証明されています)。

問題をより具体的にするか、データセットを小さくすることによってのみ、実行時間を改善できます。一般的な解決策については、あなたが持っているものにこだわっています。

于 2013-04-17T12:31:11.873 に答える
1

コードを簡単に見てみると、条件チェックでブロックできないため、オーバーフローに向かっている可能性があるようです。

あなたのコードでは、distance[v][i] < Int.MaxValue & distance[i][w] < Int.MaxValue を持てますが、distance[v][i] + distance[i ][w] > Int.Maxvalue。

if (distance[v][i] != int.MaxValue && distance[i][w] != int.MaxValue)
于 2013-04-17T12:38:13.140 に答える
0

他の人が述べたように、複雑さは固定されているため、正確には多くのオプションがありません。ただし、使用できます

  • 可能であれば、リストの代わりに配列を使用してください。
  • ポインタセマンティクスで「安全でない」ブロックを使用すると、配列データへのアクセスに必要な時間が短縮されます。
  • アルゴリズムを並列化できるかどうかを確認します。あなたの場合、データの複数のコピー（同期の必要性を取り除くための複数のコピー）を使用し、複数のスレッドで動作させることができます（たとえば、アウターループの範囲をいくつかのサブ範囲（1-1000、1001-2000）に分割することによって）例えば）。
于 2013-04-17T12:36:33.187 に答える