c# - 优化复杂物体比较

Question

我有一个模型类 Class1，我想比较 Class1 的两个实例是否相同(结构相等)。

public class Class1 : IEquatable<Class1>
{
    public string Id { get; set; }
    public string Name { get; set; }
    public IList<Class2> Class2s { get; set; }

    public bool Equals(Class1 other)
    {
       return QuestName.Equals(other.QuestName)
            && Class2s.OrderBy(c => c.Id).SequenceEqual(other.Class2s.OrderBy(c => c.Id));
                    //Below method is very fast but not so accurate
                    //because 2 objects with the same hash code may or may not be equal
        //return GetHashCode() == other.GetHashCode();
    }

    public override bool Equals(object obj)
    {
        return obj is Class1
            && this.Equals(obj as Class1);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 13;
            hash = (hash * 7) + Name.GetHashCode();
            foreach (var c2 in Class2s.OrderBy(c => c.Id))
            {
                hash = (hash * 7) + c2.GetHashCode();
            }
            return hash;
        }
    }
}

public class Class2 : IEquatable<Class2>
{
    public int Id { get; set; }
    public string Name { get; set; }
    public IList<Class3> Class3s { get; set; }

    public bool Equals(Class2 other)
    {
        return Id == other.Id
             && Name.Equals(other.Name)
             && Class3s.OrderBy(c => c.Id).SequenceEqual(other.Class3s.OrderBy(c => c.Id));
    }

    public override bool Equals(object obj)
    {
        return obj is Class2
            && this.Equals(obj as Class2 );
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 13;
            hash = (hash * 7) + Id.GetHashCode();
            hash = (hash * 7) + Name.GetHashCode();
            foreach (var c3 in Class3s.OrderBy(c => c.Id))
            {
                hash = (hash * 7) + c3.GetHashCode();
            }
            return hash;
        }
    }
}

public class Class3 : IEquatable<Class3>
{
    public int Id { get; set; }
    public string Name { get; set; }
    public IList<Class4> Class4s { get; set; }

    public bool Equals(Class3 other)
    {
        return Id == other.Id
            && Name.Equals(other.Name)
            && Class4s.OrderBy(c => c.Id).SequenceEqual(other.Class4s.OrderBy(c => c.Id));
    }

    public override bool Equals(object obj)
    {
        return obj is Class3
            && this.Equals(obj as Class3);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 13;
            hash = (hash * 7) + Id.GetHashCode();
            hash = (hash * 7) + Name.GetHashCode();
            foreach (var c in Class4s.OrderBy(c => c.Id))   
            {
                hash = (hash * 7) + c.GetHashCode();
            }                
            return hash;
        }
    }
}

public class Class4 : IEquatable<Class4>
{
    public int Id { get; set; }
    public string Name { get; set; }

    public bool Equals(Class4 other)
    {
        return Id.Equals(other.Id)
            && Name.Equals(other.Name);
    }

    public override bool Equals(object obj)
    {
        return obj is Class4
            && this.Equals(obj as Class4);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 13;
            hash = (hash * 7) + Id.GetHashCode();
            hash = (hash * 7) + Name.GetHashCode();
            return hash;
        }
    }
}

在以下情况下，我说两个 Class1 对象相等:
1. 他们有相同的名称
2. 它们具有相同的 Class2 对象(它们的顺序无关紧要)

两个 Class2 对象相等:
1. 他们有相同的Id
2. 他们有相同的名字
3. 它们具有相同的 Class3 对象(它们的顺序无关紧要)

两个 Class3 对象相等:
1. 他们有相同的Id
2. 他们有相同的名字
3. 它们具有相同的 Class4 对象(它们的顺序无关紧要)

两个 Class4 对象相等:
1. 他们有相同的Id
2.他们有相同的名字

我使用 Equals 方法比较它们并测量运行时间，如下所示:

Class1 obj1 = GetFirstClass1Object();
Class1 obj2 = GetSecondClass1Object();
var startTime = DateTime.Now;
bool equals = obj1.Equals(obj2);
var elaspedTime = DateTime.Now.Substract(startTime)

上述解决方案工作得很好，但速度很慢。我知道，如果我们压平 obj1 和 obj2，它们各自包含 3500 个 Class4 对象，并且比较 obj1< 大约需要 12 秒 和 obj2。

有没有更快的方法？我可以以某种方式利用散列来加快速度吗？

此外，obj1 和 obj2 中的 Class2、Class3 和 Class4 对象的数量 永远是一样的

Answer 1

我已经做了一些BenchmarkDotNet您的代码的基准和我必须优化您的代码的想法。

对于每个测试，我创建了 1 个 Class1 实例，它有 150 个 Class2 类型的子级，每个实例都有 150 个 Class3 类型的子级，每个都有 150 个 Class4 类型的子级。

我测量了一个对象与其自身的比较，因为比较不同的对象会更快，因为任何返回错误快捷方式的比较都会导致整个事情的发生。另外，没有 ReferenceEquals() 快捷方式，因此我没有费心克隆该对象。

测量

|                                                                 Method |        Mean | Error | Ratio |
|----------------------------------------------------------------------- |------------:|------:|------:|
|                                                        'Original code' |   535.46 ms |    NA |  1.00 |
|                               'Custom dictionary-based SequenceEquals' | 6,606.23 ms |    NA | 12.34 |
| 'Custom dictionary-based SequenceEquals, classes cache their HashCode' | 1,136.91 ms |    NA |  2.12 |
|                                 'Custom Except()-based SequenceEquals' | 2,281.12 ms |    NA |  4.26 |
|   'Custom Except()-based SequenceEquals, classes cache their HashCode' |   257.46 ms |    NA |  0.48 |
|                                                         'No OrderBy()' |    76.31 ms |    NA |  0.14 |

• 原始代码:这是您的代码。我用它作为比较的基准。
• 基于自定义字典的 SequenceEquals:然后，我尝试优化列表相等性比较。首先，我尝试了受 this answer 启发的 Dictionary 解决方案。 。事实证明，速度慢了 12 倍，因为 Dictionary 必须频繁计算 hashcode，而在我们的例子中，hashcode 意味着迭代子项和嵌套子项。
• 基于自定义字典的 SequenceEquals，类缓存其 HashCode:我认为如果开始缓存哈希码，可能会做得更好。基于字典的解决方案现在仅比原始解决方案慢两倍。
• 基于自定义 except() 的 SequenceEquals:然后是 Except() 方法。它在幕后创建了类似 HashSet 的东西。据我了解，它只需要为两个可枚举的每个元素计算一次哈希码。该解决方案花费的时间是原始解决方案的 4.26 倍。
• 基于自定义 except() 的 SequenceEquals，类缓存其 HashCode:与之前相同，我开始缓存哈希码，因此只为每个对象真正计算一次。生成的解决方案花费了原始解决方案 0.48 倍的时间。不错。
• No OrderBy():那么我就停止使用 OrderBy()，只使用 SequenceEquals()，并且考虑到我'当将一个对象与其自身进行比较时，您可以说数据已经排序，因此这样比较是安全的:-)。最终解决方案的速度大幅提升，所需时间是原始解决方案的 0.14 倍。

总结:

您最好的选择是检查您的模型和要求，您真的需要比较这样的巨大对象图吗？如果你真的必须这样做:

• 使您的对象不可变、缓存哈希码并使用基于 Except() 的比较。请小心，因为基于集合的解决方案假设您不关心重复项，因此您必须在 Except() 之前比较列表 Count。;<
• 或者，使用某种排序列表来代替列表，以避免使用 OrderBy() 并使用简单的 SequenceEquals() 比较。这是一个权衡，因为 Blade 会更贵。看看这是否适用于您的场景。

已将我的代码和测量结果上传到 this repo .