创建不同的数据结构有什么好处:HashSet或Linq的Distinct()？

Question

我想知道我是否可以就哪种方法创建一组不同的元素更好的方法达成共识:a C# HashSet或using IEnumerable's .Distinct(),这是Linq函数？

假设我正在使用DataReader循环查询数据库中的查询结果,我的选项是将我构造的对象添加到a List<SomeObject>或者HashSet<SomeObject>使用该List选项,我最终必须执行以下操作:

myList = myList.Distinct().ToList<SomeObject>();

有了这个HashSet,我的理解是,假设你已经覆盖了SomeObject中的GetHashCode()and和Equals()方法,那么添加元素就可以自己处理非重复.我主要关注选项的风险和性能方面.

谢谢.

Answer 1

Anthony Pegram表示这是最好的.使用正确的工具完成工作.我之所以这么说Distinct,HashSet是因为在性能上有一个或者没有那么大的不同.使用HashSet时收集应始终只持有不同的东西.它还告诉程序员你不能添加重复项.当您必须添加重复项并稍后删除重复项时,请使用常规List<T>和正常.Distinct().意图很重要.

一般来说,

a)如果你从db添加新对象而你没有指定Equals自己的自定义,那么HashSet可能没有任何好处.db中的每个对象都可以是您的hashset的新实例(如果您只是新增的),这将导致集合中的重复.在那种情况下使用正常List<T>.

b)如果你确实为hashset定义了相等比较器,并且你的集合应该总是只保存不同的对象,那么使用hashset.

c)如果你确实为hashset定义了相等比较器,并且你只想要来自db的不同对象,但是收集不需要总是只保存不同的对象(即需要稍后添加重复项),更快的方法是从db获取项目到一个哈希集,然后从该哈希集返回一个常规列表.

d)你应该做的最好的事情是给数据库删除重复的任务,这是正确的工具和那是第一堂课!

至于性能差异,在我的测试中我总是发现HashSet更快,但那只是边缘.考虑到List方法,你必须首先添加然后对其进行区分.

测试方法:从两个通用函数开始,

public static void Benchmark(Action method, int iterations = 10000)
{
    Stopwatch sw = new Stopwatch();
    sw.Start();
    for (int i = 0; i < iterations; i++)
        method();

    sw.Stop();
    MsgBox.ShowDialog(sw.Elapsed.TotalMilliseconds.ToString());
}

public static List<T> Repeat<T>(this ICollection<T> lst, int count)
{
    if (count < 0)
        throw new ArgumentOutOfRangeException("count");

    var ret = Enumerable.Empty<T>();

    for (var i = 0; i < count; i++)
        ret = ret.Concat(lst);

    return ret.ToList();
}

执行:

var d = Enumerable.Range(1, 100).ToList().Repeat(100);
HashSet<int> hash = new HashSet<int>();

Benchmark(() =>
{
    hash.Clear();
    foreach (var item in d)
    {
        hash.Add(item);
    }
});

~3300毫秒

var d = Enumerable.Range(1, 100).ToList().Repeat(100);
List<int> list = new List<int>();

Benchmark(() =>
{
    list.Clear();
    foreach (var item in d)
    {
        list.Add(item);
    }

    list = list.Distinct().ToList();
});

~5800毫秒

当迭代另外10000次时,对于10000个对象的列表,差异为2.5秒也不错.对于正常情况,差异将难以察觉.

使用当前设计的最佳方法:

var d = Enumerable.Range(1, 100).ToList().Repeat(100);
HashSet<int> hash = new HashSet<int>();
List<int> list = new List<int>();

Benchmark(() =>
{
    hash.Clear();
    foreach (var item in d)
    {
        hash.Add(item);
    }

    list = hash.ToList();
});

~3300毫秒

没有任何显着差异,请参阅..

部分无关 - 在发布此答案后,我很想知道从正常列表中删除重复项的最佳方法是什么.

var d = Enumerable.Range(1, 100).ToList().Repeat(100);
HashSet<int> hash = new HashSet<int>();
List<int> list = new List<int>();

Benchmark(() =>
{
    hash = new HashSet<int>(d);
});

~3900毫秒

var d = Enumerable.Range(1, 100).ToList().Repeat(100);
List<int> list = new List<int>();

Benchmark(() =>
{
    list = d.Distinct().ToList();
});

~3200毫秒

这里正确的工具Distinct比黑客更快HashSet!也许是创建哈希集的开销.

我已经测试了各种其他组合,如引用类型,原始列表中没有重复等.结果是一致的.

Answer 2

更好的是描述你的意图最具表现力的是什么.内部实现细节或多或少会相同,不同之处在于"谁在编写代码？"

如果你打算从头开始创建一个来自不是所述项目集合的来源的不同项目集合,我会争辩的HashSet<T>.你必须创建项目,你必须构建集合,你也可以从一开始构建正确的项目.

否则,如果你已经有一个项目集合,并且你想要消除重复,我会争论调用Distinct().你已经有了一个集合,你只需要一种富有表现力的方式来获取它的不同项目.

Answer 3

“更好”这个词用起来很棘手——它对不同的人可能意味着很多不同的东西。

为了可读性，我会去，Distinct()因为我个人觉得这更容易理解。

对于性能，我怀疑手工制作的 HashSet 实现的执行速度可能会稍微快一些 - 但我怀疑它会非常不同，因为 的内部实现Distinct无疑会使用某种形式的散列。

对于我认为的“最佳”实现...我认为您应该使用Distinct但以某种方式将其推到数据库层 - 即在填充 DataReader 之前更改底层数据库 SELECT。