如何实现O(1)级三维数组比较？魔方求解算法遇比较失效问题

C#里数组属于引用类型，==运算符默认比较的是两个数组的内存引用地址，而非内部元素值。哪怕DefaultCube()每次返回的数组内容完全一致，它们也是不同的对象实例，引用地址不同，所以==必然返回false。同理，Dictionary<int[,,], ...>的ContainsKey方法默认用引用相等判断，导致你无法通过内容匹配找到已存在的数组。

针对你的超大规模运算需求，不能用遍历元素的方式做比较，必须实现自定义的相等比较器，让字典使用这个比较器来判断键的相等性，同时保证哈希计算的高效性。

1. 实现自定义三维数组相等比较器 #

创建一个实现IEqualityComparer<int[,,]>的类，重写Equals和GetHashCode方法：

public class CubeEqualityComparer : IEqualityComparer<int[,,]>
{
    public static readonly CubeEqualityComparer Instance = new CubeEqualityComparer();
    private CubeEqualityComparer() {} // 私有构造，强制单例

    public bool Equals(int[,,] x, int[,,] y)
    {
        // 快速路径：引用相同直接返回true
        if (ReferenceEquals(x, y)) return true;
        // 任一为null或维度不同返回false
        if (x == null || y == null) return false;
        if (x.GetLength(0) != y.GetLength(0) || 
            x.GetLength(1) != y.GetLength(1) || 
            x.GetLength(2) != y.GetLength(2))
            return false;
        
        // 魔方固定3x3x3，遍历27个元素的开销可忽略
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                for (int k = 0; k < 3; k++)
                    if (x[i,j,k] != y[i,j,k])
                        return false;
        return true;
    }

    public int GetHashCode(int[,,] cube)
    {
        if (cube == null) return 0;
        // 结合所有元素值计算哈希，保证内容相同的数组哈希一致
        int hash = 17;
        foreach (int val in cube)
        {
            hash = hash * 31 + val;
        }
        return hash;
    }
}

2. 修改字典初始化逻辑 #

创建字典时传入自定义比较器，替换默认的引用相等判断：

var fromSC = new Dictionary<int[,,], int[,,]>(CubeEqualityComparer.Instance);
var fromSOL = new Dictionary<int[,,], int[,,]>(CubeEqualityComparer.Instance);

3. 修正调试用的相等判断 #

把原来的==比较改成用自定义比较器判断：

if (CubeEqualityComparer.Instance.Equals(DefaultCube(), DefaultCube()))
    Console.WriteLine("Works");
else
    Console.WriteLine("Broken");

额外性能优化 #

• 缓存默认魔方实例：避免每次调用DefaultCube()创建新数组，提前创建静态实例复用：

  private static readonly int[,,] _defaultCube = DefaultCube();
  

• 减少对象创建：魔方是固定结构，所有数组操作尽量复用内存，避免频繁创建新数组实例。

public void Solving(int[,,] Tbs)
{
    bool found = false;
    List<char> movements = new() {'F','U','L', 'R','D', 'B' };
    Queue<int[,,]> activeFromSramble = new();
    Queue<int[,,]> activeFromSolved = new();

    // 调试用的相等判断
    if (CubeEqualityComparer.Instance.Equals(DefaultCube(), DefaultCube()))
        Console.WriteLine("Works");
    else
        Console.WriteLine("Broken");

    // 使用自定义比较器的字典
    var fromSC = new Dictionary<int[,,], int[,,]>(CubeEqualityComparer.Instance);
    var fromSOL = new Dictionary<int[,,], int[,,]>(CubeEqualityComparer.Instance);

    // 缓存默认魔方实例
    var defaultCube = DefaultCube();
    activeFromSramble.Enqueue(Tbs);
    activeFromSolved.Enqueue(defaultCube);
    fromSC.Add(Tbs, Tbs);
    fromSOL.Add(defaultCube, defaultCube);

    while (!found)
    {
        Console.WriteLine("It");
        int[,,] oldCube = activeFromSramble.Dequeue();
        if (fromSOL.ContainsKey(oldCube))
        {
            found = true;
            Console.WriteLine("FOUND");
        }
        foreach (char c in movements)
        {
            for (int i = 1; i < 4; i++)
            {
                int[,,] newCube = PermCube(oldCube, c, i);
                if (fromSC.ContainsKey(newCube))
                    continue;
                fromSC.Add(newCube, oldCube);
                activeFromSramble.Enqueue(newCube);
            }
        }
        
        oldCube = activeFromSolved.Dequeue();
        if (fromSC.ContainsKey(oldCube))
        {
            found = true;
            Console.WriteLine("FOUND");
        }
        foreach (char c in movements)
        {
            for (int i = 1; i < 4; i++)
            {
                int[,,] newCube = PermCube(oldCube, c, i);
                if (fromSOL.ContainsKey(newCube))
                    continue;
                activeFromSolved.Enqueue(newCube);
                fromSOL.Add(newCube, oldCube);
            }
        }
    }
}

内容的提问来源于stack exchange，提问作者Lukas van Dee