C# (.Net 2.0) 微优化第 2 部分：查找网格内的连续组

Question

我有一个非常简单的函数，它接受一个匹配的位字段、一个网格和一个正方形。 它曾经使用委托，但我做了很多重新编码，并最终使用位字段 & 操作来避免委托，同时仍然能够在合理范围内执行匹配。 基本上，挑战是从特定的“前导”方块开始，找到网格内与 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);

  公共静态列表   GetGroup(int match, 模型网格, 方形领导者) 
    { 
        堆栈<正方形>   curStack = new Stack(); 
        字典   Retval = new Dictionary(); 
        curStack.Push(领导者); 
        while (curStack.Count != 0) 
        { 
            方形 curItem = curStack.Pop(); 
            if (Retval.ContainsKey(curItem)) 继续； 
            Retval.Add(curItem, true); 
            foreach（curItem.Neighbors 中的 Square） 
            { 
                if (0 != ((int)(s.RoomType) & match)) 
                { 
                    curStack.Push(s); 
                } 
            } 
        } 
        返回新列表(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 来跟踪它们。 最后，您只需创建一个包含具有 true 值的项目的 List 即可。

    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;
    }

Answer 2

这里有一些建议 -

如果您使用 .NET 3.5，您可以将 RetVal 更改为 HashSet而不是 Dictionary，因为您从不使用字典中的值（仅使用键）。 这将是一个小小的改进。

另外，如果将返回更改为 IEnumerable，则可以直接返回 HashSet 的枚举器。 根据结果​​的使用情况，在某些区域可能会更快（如果您确实需要列表，您始终可以在结果上使用 ToList() ）。

然而，这里可以添加一个很大的优化 -

现在，您总是添加每个邻居，即使该邻居已经被处理过。 例如，当处理leader时，它会添加leader+1y，然后当处理leader+1y时，它会将BACK放入leader中（即使你已经处理了那个Square），下次领导者从堆栈中弹出，你继续。 这是很多额外的处理。

尝试添加：

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

这样，如果您已经处理了邻居的平方，它不会被重新添加到堆栈中，只是在稍后弹出时被跳过。