8

我目前正在做一些涉及邻接矩阵的图形计算，并且我正在优化它的每一点。

我认为可以优化的指令之一是标题中的指令，它的原始形式：

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 次迭代减少了 792ms，从 3672ms 减少到 2880ms，这是原始时间的 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) >= 0，因为x != 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# 优化这样的事情有多好，但尝试存储 adjMatrix[i][k]和adjMatrix[k][j]在临时变量中不读取两次内存并不难。看看这是否会以任何方式改变事情。

很难相信算术和比较运算是这里的瓶颈。很可能是内存访问或分支。理想情况下，应该以线性方式访问内存。你能做点什么让它更线性吗？

看到更多代码来提出更具体的建议会很好。

更新：您可以尝试使用二维数组 ( int[,]) 而不是锯齿状数组 ( int[][])。这可能会提高内存局部性和元素访问速度。

于 2012-10-15T17:32:29.593 回答
3

逻辑测试的顺序可能很重要（如其他答案中所述）。由于您使用的是短路逻辑测试（&& 而不是 &），因此从左到右评估条件，并且它发现的第一个为假的，将导致程序停止评估条件并继续执行（没有执行if块）。因此，如果有一种情况比其他情况更有可能发生false，则应该首先出现，下一个应该是下一个最有可能出现的情况false，依此类推。

另一个很好的优化（我怀疑这确实是您提高性能的原因——而不是简单地放弃一些条件）是将您从数组中提取的值分配给局部变量。

您正在使用adjMatrix[i][k]两次（以及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. 避免双重索引：使用 ILDASM 或等效方法查看生成的 IL，以确保数组索引仅被取消引用一次，而不是两次。如果不是，请尝试在检查之前将它们放入局部变量中。

于 2012-10-15T17:50:43.070 回答
0

你考虑过颠倒逻辑吗​​？

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

可以改写为：

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

由于如果任何语句为假，您不想在循环中执行任何操作，因此请尝试尽快中止（如果运行时很聪明，我假设）。

最重的操作应该放在最后，因为如果第一个语句为真，则不需要检查其他语句。我认为添加是最重的部分，但分析它可能会讲述一个不同的故事。

但是，我自己并没有描述过这些场景，而且对于这些微不足道的条件，它甚至可能是一个缺点。看到你的发现会很有趣。

于 2012-10-15T18:22:53.377 回答