0

我有三个从零到 n 的嵌套循环。n 是一个很大的数，大约 12000th 这三个循环在 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

通常我会建议使用 Parallel Linq - 例如Ray Tracer示例，但是这假设您正在操作的项目是独立的。在您的示例中，您正在使用上一次迭代的结果，在当前一次迭代中，无法并行化。

由于您的代码非常简单并且没有任何开销，因此您无法做任何事情来加快速度。如前所述，您可以将列表切换为数组。您可能还想在目标机器上比较 Double 算术和 Integer 算术。

于 2013-04-17T12:30:29.207 回答
1

在简单地查看您的代码之后，您似乎正在走向溢出，因为条件检查将无法阻止它。

在您的代码中，以下条件不会增加任何值，因为我们可以让 distance[v][i] < Int.MaxValue & distance[i][w] < Int.MaxValue 但 distance[v][i] + distance[i ][w] > 整数最大值。

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 回答