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

您发布的代码假定该leader方块与位域匹配.这是设计的吗？

我假设你的Square课程已经实现了GetHashCode一种快速且提供良好分布的方法.

你确实说过微优化...

如果你很清楚你期望有多少项,你可以通过预先分配字典节省一点时间.也就是说,如果你知道你不会有超过100个匹配的项目,你可以写:

Dictionary Retval = new Dictionary(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 GetGroup(int match, Model grid, Square leader)
    {
        Stack curStack = new Stack(); 
        Dictionary Retval = new Dictionary(); 
        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 matches = new List(numMatch);
        foreach (KeyValuePair kvp in Retval)
        {
            if (kvp.Value == true)
            {
                matches.Add(kvp.Key);
            }
        }
        return matches;
    }