C# (.Net 2.0) 微优化第 2 部分 : Finding Contiguous Groups within a grid

Question

我有一个非常简单的函数，它接受一个匹配的位域、一个网格和一个正方形。它曾经使用委托(delegate)，但我做了很多重新编码，最后得到一个位域 & 操作来避免委托(delegate)，同时仍然能够在合理范围内执行匹配。基本上，挑战是从特定的“领导者”方 block 开始，在网格中找到与 match 位域匹配的所有连续元素。Square 有点小(但不小)类。关于如何插入它更快的任何提示？请注意，网格本身非常小(本次测试中有 500 个元素)。

编辑:值得注意的是，此函数每秒被调用超过 200,000 次。事实上，从长远来看，我的目标是减少调用它的次数，但考虑到我的最终目标是使用脚本而不是硬编码来处理分组系统，这真的很难。也就是说，此函数的调用次数总是多于任何其他函数。

编辑:澄清一下，该函数在设计上不会检查 leader 是否与位域匹配。目的是不需要领导者匹配位域(尽管在某些情况下会匹配)。

尝试失败的事情:

• 用容量初始化字典和堆栈。
• 将 int 转换为枚举以避免转换。
• 将字典和堆栈移到函数外部，并在每次需要时清除它们。这会让事情变慢!

尝试成功的事情:

• 编写哈希码函数而不是使用默认值:哈希码是预先计算的，等于 x + y * parent.Width。感谢您的提醒，吉姆·米歇尔。
• mquander 的技术:参见下面的 GetGroupMquander。

• 进一步优化:切换到 HashSets 后，我摆脱了 Contains 测试并将其替换为 Add 测试。 Contains 和 Add 都被强制寻找一个键，所以只检查添加是否成功比如果 Contains 失败则添加检查失败更有效.也就是说，if (RetVal.Add(s)) curStack.Push(s);

  public static List<Square> GetGroup(int match, Model grid, Square leader)
  {
      Stack<Square> curStack = new Stack<Square>();
      Dictionary<Square, bool> Retval = new Dictionary<Square, bool>();
      curStack.Push(leader);
      while (curStack.Count != 0)
      {
          Square curItem = curStack.Pop();
          if (Retval.ContainsKey(curItem)) continue;
          Retval.Add(curItem, true);
          foreach (Square s in curItem.Neighbors)
          {
              if (0 != ((int)(s.RoomType) & match))
              {
                  curStack.Push(s);
              }
          }
      }
      return new List<Square>(Retval.Keys);
  }
  

=====

    public static List<Square> GetGroupMquander(int match, Model grid, Square leader)
    {
        Stack<Square> curStack = new Stack<Square>();
        Dictionary<Square, bool> Retval = new Dictionary<Square, bool>();
        Retval.Add(leader, true);
        curStack.Push(leader);
        while (curStack.Count != 0)
        {
            Square curItem = curStack.Pop();

            foreach (Square s in curItem.Neighbors)
            {
                if (0 != ((int)(s.RoomType) & match))
                {
                    if (!Retval.ContainsKey(s))
                    {
                        curStack.Push(s);
                        Retval.Add(curItem, true);
                    }
                }
            }
        }
        return new List<Square>(Retval.Keys);
    }

Answer 1

您发布的代码假定 leader 方 block 与位域匹配。这是设计使然吗？

我假设您的 Square 类已经实现了一个 GetHashCode 方法，该方法速度快且分布良好。

您确实说过微优化。 . .

如果您很清楚自己需要多少项，您可以通过预分配字典来节省一点时间。也就是说，如果您知道匹配的项目不会超过 100 个，您可以这样写:

Dictionary<Square, bool> Retval = new Dictionary<Square, bool>(100);

这将避免增加字典和重新散列所有内容。您也可以对您的堆栈做同样的事情:将它预分配到某个合理的最大大小以避免以后调整大小。

既然你说网格非常小，那么将堆栈和字典分配给网格大小似乎是合理的，如果这很容易确定的话。您只是在谈论每个 grid_size 引用，因此除非您的网格变得非常大，否则内存不是问题。

在执行推送之前添加检查以查看某个项目是否在字典中可能会稍微加快速度。它取决于字典查找的相对速度，而不是堆栈中有重复项的开销。尝试一下可能是值得的，尽管如果它产生很大的不同我会感到惊讶。

if (0 != ((int)(s.RoomType) & match))
{
    if (!Retval.ContainsKey(curItem))
        curStack.Push(s);
}

最后一个我真的很紧张。你在你的内循环中有那个 Actor 。我知道 C# 编译器有时会为看似简单的强制转换生成数量惊人的代码，我不知道 JIT 编译器是否优化了这些代码。您可以通过创建枚举类型的局部变量并为其分配 match 的值来从内部循环中删除该强制转换:

RoomEnumType matchType = (RoomEnumType)match;

然后你的内循环比较变成:

if (0 != (s.RoomType & matchType))

没有强制转换，这可能会减少一些周期。

编辑:撇开微优化不谈，您可能会通过稍微修改算法来避免多次处理任何项目来获得更好的性能。就目前而言，匹配的项目可以多次出现在堆栈中，而不匹配的项目可以多次处理。由于您已经在使用字典来跟踪匹配的项目，因此您可以通过为它们指定 false 的值来跟踪不匹配的项目。然后在最后，您只需创建一个 List，其中包含那些具有 true 值的项目。

    public static List<Square> GetGroup(int match, Model grid, Square leader)
    {
        Stack<Square> curStack = new Stack<Square>(); 
        Dictionary<Square, bool> Retval = new Dictionary<Square, bool>(); 
        curStack.Push(leader);
        Retval.Add(leader, true);
        int numMatch = 1;
        while (curStack.Count != 0)
        {
            Square curItem = curStack.Pop(); 
            foreach (Square s in curItem.Neighbors) 
            {
                if (Retval.ContainsKey(curItem))
                    continue;
                if (0 != ((int)(s.RoomType) & match))
                {
                    curStack.Push(s);
                    Retval.Add(s, true);
                    ++numMatch;
                }
                else
                {
                    Retval.Add(s, false);
                }
            }
        }
        // LINQ makes this easier, but since you're using .NET 2.0...
        List<Square> matches = new List<Square>(numMatch);
        foreach (KeyValuePair<Square, bool> kvp in Retval)
        {
            if (kvp.Value == true)
            {
                matches.Add(kvp.Key);
            }
        }
        return matches;
    }