时间戳

首页 > 解决方案 > 有没有比使用 Contains 方法更快的方法来搜索大型集合中是否存在实例？

c# - 有没有比使用 Contains 方法更快的方法来搜索大型集合中是否存在实例？

问题描述

我有一个 C# 控制台应用程序，可将数据保存到 2 个 db 表、一个实体表和一个关系表。每个实体与其他实体具有多对多关系。关系表存储了一对 ID，它们又是实体表的主键。

两个表中的数据应该是唯一的。最初，我在数据库存储过程中插入新的个人记录之前检查了这一点。当两个表中的数字开始变大时（实体表中> 50k，关系表中> 100k），我注意到性能确实开始受到影响。

我认为由于增加了 I/O 成本，去数据库执行重复记录检查对性能有帮助，所以我重构了我的代码，首先将两个表读入内存，然后在那里执行检查。这提高了性能，尽管我怀疑它可能仍然不理想。这是它现在的样子：

    private IEnumerable<long> _existingUsers = dao.GetUserIds();
    private IEnumerable<Relations> _existingRelations = dao.GetRelations();


                if (!_existingUsers.Contains(inputModel.ID))
                {
                    // db code to create the new Entity record
                }

                Relations rel = new Relations { Node = inputModel.Node, Follower = inputModel.ID };

                if (!_existingRelations.Contains(rel))
                {
                    // db code to create the new Relation entry
                }

关系类：

public class Relations : IEquatable<Relations>
{
    public long Node { get; set; }
    public long Follower { get; set; }

    public bool Equals(Relations other)
    {
        return (other.Node == this.Node) && (other.Follower == this.Follower);
    }
}

我可以通过调试器看到，现在大部分时间都用于确定内存中的 _existingRelations 集合是否包含“rel”实例。这反过来又反复命中了关系类的 Equals 方法。

我怀疑可能有更有效的方法来做到这一点，但我不知道那是什么。

标签： c#search

解决方案

这取决于 IEnumerable 的具体实现。

这就是您contains在列表中调用时发生的情况。在列表中搜索总是迭代所有列表以找到一个元素。所以没有更快的方法找到一个。

如果你称之为：https ://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.hashset-1.contains?view=netcore-3.1那么你会得到一个O(1)原样和HashSet字典。

不利的一面是，哈希集没有排序。

推荐阅读