c# - 对于大量自定义对象集合，Intersection() 和 Except() 太慢

Question

我正在从另一个数据库导入数据。

我的进程正在将数据从远程数据库导入到 List<DataModel>名为 remoteData并将数据从本地数据库导入 List<DataModel>名为 localData .

然后我使用 LINQ 创建不同记录的列表，以便我可以更新本地数据库以匹配从远程数据库中提取的数据。像这样:

var outdatedData = this.localData.Intersect(this.remoteData, new OutdatedDataComparer()).ToList();

然后我使用 LINQ 创建一个不再存在于 remoteData 中的记录列表, 但确实存在于 localData ，以便我从本地数据库中删除它们。

像这样:

var oldData = this.localData.Except(this.remoteData, new MatchingDataComparer()).ToList();

然后我使用 LINQ 执行与上述相反的操作，将新数据添加到本地数据库。

像这样:

var newData = this.remoteData.Except(this.localData, new MatchingDataComparer()).ToList();

每个集合导入大约 70k 条记录，3 个 LINQ 操作中的每一个都需要 5 到 10 分钟才能完成。 我怎样才能让它更快？

这是集合使用的对象:

internal class DataModel
{
        public string Key1{ get; set; }
        public string Key2{ get; set; }

        public string Value1{ get; set; }
        public string Value2{ get; set; }
        public byte? Value3{ get; set; }
}

用于检查过时记录的比较器:

class OutdatedDataComparer : IEqualityComparer<DataModel>
{
    public bool Equals(DataModel x, DataModel y)
    {
        var e =
            string.Equals(x.Key1, y.Key1) &&
            string.Equals(x.Key2, y.Key2) && (
                !string.Equals(x.Value1, y.Value1) ||
                !string.Equals(x.Value2, y.Value2) ||
                x.Value3 != y.Value3
                );
        return e;
    }

    public int GetHashCode(DataModel obj)
    {
        return 0;
    }
}

用于查找新旧记录的比较器:

internal class MatchingDataComparer : IEqualityComparer<DataModel>
{
    public bool Equals(DataModel x, DataModel y)
    {
        return string.Equals(x.Key1, y.Key1) && string.Equals(x.Key2, y.Key2);
    }

    public int GetHashCode(DataModel obj)
    {
        return 0;
    }
}

Answer 1

通过使用常量哈希码，您已经破坏了性能。这是 Intersect 使用的内部代码(通过反编译器获得)

public static IEnumerable<TSource> Intersect<TSource>(this IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
    if (first == null)
    {
        throw Error.ArgumentNull("first");
    }
    if (second == null)
    {
        throw Error.ArgumentNull("second");
    }
    return Enumerable.IntersectIterator<TSource>(first, second, comparer);
}

private static IEnumerable<TSource> IntersectIterator<TSource>(IEnumerable<TSource> first, IEnumerable<TSource> second, IEqualityComparer<TSource> comparer)
{
    Set<TSource> set = new Set<TSource>(comparer);
    foreach (TSource current in second)
    {
        set.Add(current);
    }
    foreach (TSource current2 in first)
    {
        if (set.Remove(current2))
        {
            yield return current2;
        }
    }
    yield break;
}

请注意，它在内部使用了一个Set，如果您实现了哈希码，将会大大提高它的性能。

MatchingDataCompaer 是两者中较简单的一个，所以我会为您做一个。

internal class MatchingDataComparer : IEqualityComparer<DataModel>
{
    public MatchingDataComparer()
    {
        comparer = StringComparer.Ordnal; //Use whatever comparer you want.
    }

    private readonly StringComparer comparer;

    public bool Equals(DataModel x, DataModel y)
    {
        return comparer.Equals(x.Key1, y.Key1) && comparer.Equals(x.Key2, y.Key2);
    }

    //Based off of the advice from http://stackoverflow.com/questions/263400/what-is-the-best-algorithm-for-an-overridden-system-object-gethashcode
    public int GetHashCode(DataModel obj)
    {    
        unchecked // Overflow is fine, just wrap
        {
            int hash = 17;
            hash = hash * 23 + comparer.GetHashCode(obj.Key1);
            hash = hash * 23 + comparer.GetHashCode(obj.Key2);
            return hash;
        }
    }
}

您可能会在 OutdatedDataComparer 中使用 MatchingDataComparer 的哈希码函数，它可能不是“最佳”哈希码¹，但它将是一个“合法的”²，并且比硬编码的 0 快得多。

---

<sup>1。或者可能是，我不确定如何包含第 3 个 && 条件
2. 如果 a.Equals(b) == true 则 a.GetHashCode() = b.GetHashCode()。
如果 a.Equals(b) == false 则 a.GetHashCode() = b.GetHashCode() || a.GetHashCode() != b.GetHashCode()</sup>