C#(.Net 2.0)微优化第2部分:在网格中查找连续组

Question

我有一个非常简单的函数,它接受匹配的位域,网格和正方形.它过去常常使用委托,但我做了大量的重新编码,最后进行了一个位域&操作,以避免委托,同时仍能在合理范围内执行匹配.基本上,挑战是match从特定的"前导"方块开始,在网格中找到与位域匹配的所有连续元素.Square有点小(但不是很小).关于如何推动这个更快的任何提示？请注意,网格本身非常小(此测试中有500个元素).

编辑:值得注意的是,此函数每秒调用超过200,000次.事实上,从长远来看,我的目标是不经常调用它,但这真的很难,因为我的最终目标是使用脚本处理分组系统而不是硬编码.也就是说,这个函数总是被称为比任何其他函数更多.

编辑:为了澄清,该功能不会检查是否leader匹配位域,按设计.目的是领导者不需要匹配位域(尽管在某些情况下它会).

事情尝试失败:

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

事情尝试成功:

• 编写哈希码函数而不是使用默认值:哈希码是预先计算的并且等于x + y * parent.Width.感谢提醒,Jim Mischel.
• 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方块与位域匹配.这是设计的吗？

我假设你的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);
}

我真的在最后一个延伸.你的内循环中有你的演员.我知道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;
    }