优化复杂对象比较

Question

我有一个模型 class 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.他们有相同的Name
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 和 obj2 需要大约 12 秒。

有没有更快的方法来做到这一点？我能以某种方式利用散列来加快速度吗？

此外，obj1 和 obj2 中的 Class2、Class3 和 Class4 对象的数量将始终相同

Answer 1

对列表进行排序只是为了比较它们对我来说似乎效率很低。您可以尝试使用其他方法来比较列表

而不是

Class2s.OrderBy(c => c.Id).SequenceEqual(other.Class2s.OrderBy(c => c.Id)

你可以试试

!Class2s.Except(other.Class2s).Any()

如果大多数对象不相等，您还可以添加额外的测试以确保列表在大小不相同时不会循环：

Class2s.Count == other.Class2s.Count && !Class2s.Except(other.Class2s).Any()

当然，您也可以对 Class2.Equals() 和 Class3.Equals 方法执行相同的操作。

Answer 2

以提供的 classes 为例，考虑以下结构。没有基于您的示例的示例数据来对其进行测试，因此您将不得不使用现有的进行测试。

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

    public static bool operator ==(Class1 left, Class1 right) {
        return Equals(left, right);
    }

    public static bool operator !=(Class1 left, Class1 right) {
        return !(left == right);
    }

    public bool Equals(Class1 other) {
        if (ReferenceEquals(null, other)) return false;
        if (ReferenceEquals(this, other)) return true;
        return string.Equals(this.ToString(), other.ToString());
    }

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

    public override int GetHashCode() {
        return ToString().GetHashCode();
    }

    public override string ToString() {
        var cs = Class2s == null ? "" : string.Join("", Class2s.OrderBy(_ => _.Id).Select(_ => _.ToString()));
        return string.Join("", Id, Name, cs);
    }
}

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

    public static bool operator ==(Class2 left, Class2 right) {
        return Equals(left, right);
    }

    public static bool operator !=(Class2 left, Class2 right) {
        return !(left == right);
    }

    public bool Equals(Class2 other) {
        if (ReferenceEquals(null, other)) return false;
        if (ReferenceEquals(this, other)) return true;
        return string.Equals(this.ToString(), other.ToString());
    }

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

    public override int GetHashCode() {
        return ToString().GetHashCode();
    }

    public override string ToString() {
        var cs = Class3s == null ? "" : string.Join("", Class3s.OrderBy(_ => _.Id).Select(_ => _.ToString()));
        return string.Join("", Id, Name, cs);
    }
}

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

    public static bool operator ==(Class3 left, Class3 right) {
        return Equals(left, right);
    }

    public static bool operator !=(Class3 left, Class3 right) {
        return !(left == right);
    }

    public bool Equals(Class3 other) {
        if (ReferenceEquals(null, other)) return false;
        if (ReferenceEquals(this, other)) return true;
        return string.Equals(this.ToString(), other.ToString());
    }

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

    public override int GetHashCode() {
        return ToString().GetHashCode();
    }

    public override string ToString() {
        var cs = Class4s == null ? "" : string.Join("", Class4s.OrderBy(_ => _.Id).Select(_ => _.ToString()));
        return string.Join("", Id, Name, cs);
    }
}

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

    public static bool operator ==(Class4 left, Class4 right) {
        return Equals(left, right);
    }

    public static bool operator !=(Class4 left, Class4 right) {
        return !(left == right);
    }

    public bool Equals(Class4 other) {
        if (ReferenceEquals(null, other)) return false;
        if (ReferenceEquals(this, other)) return true;
        return string.Equals(this.ToString(), other.ToString());
    }

    public override bool Equals(object obj) {
        return obj is Class4 other && Equals(other);
    }

    public override int GetHashCode() {
        return ToString().GetHashCode();
    }

    public override string ToString() {
        return string.Format("{0}{1}", Id, Name);
    }
}

所有对象的结构都相似，除了 Class4 显然，因为它没有内部列表。

虽然只是一个例子，但很多重复的代码都可以重构为一个公共基础class。

Answer 3

我已经对您的代码和想法进行了一些 BenchmarkDotNet 基准测试，我不得不优化您的代码。

对于每个测试，我创建了 1 个 Class1 实例，其中有 150 个 children 类型 Class2，每个实例有 150 个 children 类型Class3，每个都有150个children类型Class4.

我测量过将 object 与自身进行比较，因为比较不同的 object 会快得多，因为任何 returns 错误的比较都会缩短整个过程。此外，没有 ReferenceEquals() 快捷方式，因此我没有费心克隆 object.

测量值

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

Original code：这是你的代码。我将其用作比较基准。
Custom dictionary-based SequenceEquals：然后，我尝试优化列表相等比较。首先，我尝试了受 this answer 启发的 Dictionary 解决方案。事实证明，它慢了 12 倍，因为 Dictionary 必须经常计算 hashcode，而 hashcode 在我们的例子中意味着遍历 children 并嵌套 children.
Custom dictionary-based SequenceEquals, classes cache their HashCode：我认为如果我开始缓存哈希码可能会做得更好。基于 Dictionary 的解决方案现在只比原来慢两倍。
Custom Except()-based SequenceEquals：然后就是Except()方法了。在幕后，它创建了类似于 HashSet 的东西。据我了解，它只需要为两个可枚举的每个元素计算一次哈希码。该解决方案花费的时间是原始解决方案的 4.26 倍。
Custom Except()-based SequenceEquals, classes cache their HashCode：和以前一样，我开始缓存哈希码，因此每个 object 只真正计算一次。生成的解决方案花费原始解决方案的 0.48 倍时间。不错。
No OrderBy()：然后我停止使用 OrderBy()，只使用 SequenceEquals()，考虑到我正在将 object 与其自身进行比较，你可以说数据已经排序，所以这样比较是安全的:-)。由此产生的解决方案是一个巨大的加速，占用原始时间的 0.14 倍。

总结：

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

使您的 object 不可变，缓存哈希码，并使用基于 Except() 的比较。小心，因为 Set-based 解决方案假定您不关心重复项，所以您必须在 Except().;

Count

或者，不用列表，而是使用某种排序列表来避免必须使用 OrderBy() 并使用普通的 SequenceEquals() 比较。这是一种权衡，因为插入物会更昂贵。看看这是否适用于您的场景。

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

优化复杂对象比较

Optimize complex objects comparison

c#

list

performance

linq

comparison

测量值

总结：