LINQ中的Distinct
一、从去重说起
去重一直是数据处理中的一个重要操作，保证处理的数据中没有冗余，而在编写代码的时候更是经常需要剔除重复的数据避免重复计算。LINQ中的Distinct方法可以很好的处理基本数据类型的去重操作，如下所示：
// int类型
List<int> ints = new List<int> {
4, 5, 2, 1, 4, 6, 3, 2, 1, 3
};
ints.Distinct().ToList().ForEach(x => Console.WriteLine(x));
// string类型
List<string> strings = new List<string> {
"Tom", "John", "Lily", "Tom", "Jess", "John"
};
strings.Distinct().ToList().ForEach(x => Console.WriteLine(x));但是在使用Distinct方法处理对象类型的数据时却没有这么好的体验了，假设我们有下面这个Person类，和类似的去重代码：
public class Person
{
public int Id { get; set; }
public string Name { get; set; }
public int Age { get; set; }
public override string ToString()
{
return string.Format("Id: {0}, Name: {1}, Age: {2}",
this.Id, this.Name, this.Age);
}
}
List<Person> personList = new List<Person>
{
new Person { Id = 1, Name = "Zhangsan", Age = 23 },
new Person { Id = 2, Name = "Lisi", Age = 22 },
new Person { Id = 3, Name = "Wangwu", Age = 25 },
new Person { Id = 2, Name = "Lisi", Age = 22 },
new Person { Id = 1, Name = "Zhangsan", Age = 23 }
};
var dist = personList.Distinct().ToList();
dist.ForEach(x => Console.WriteLine(x));得到的结果如下图，可以看到直接简单的使用Distinct来对对象列表进行去重，得到的结果和没去重的结果是一样的！原因在于Distinct方法默认的实现是根据对象的引用来进行的，而上面new了5个Person对象，是5个不同的引用。
我们查看Distinct方法的定义，发现该方法还可以带一个IEqualityComparer<TSource>类型的参数：
namespace System.Linq
{
public static class Enumerable
{
// ...
public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source);
public static IEnumerable<TSource> Distinct<TSource>(
this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer);
// ...
}
}下面我们通过实现IEqualityComparer接口来实现对象列表的去重。
二、实现IEqualityComparer
IEqualityComparer接口的定义如下：
namespace System.Collections.Generic
{
public interface IEqualityComparer<in T>
{
bool Equals(T x, T y);
int GetHashCode(T obj);
}
}可以看到通过实现IEqualityComparer接口封装了Equals和GetHashCode这两个函数的实现，而这两个正是用于判断对象是否相等的重要函数。因为这里我们是想通过Id字段来去重，所以我们新建一个PersonIdComparer类：
public class PersonIdComparer : IEqualityComparer<Person>
{
public bool Equals(Person x, Person y)
{
if (x == null)
return y == null;
return x.Id == y.Id;
}
public int GetHashCode(Person obj)
{
if (obj == null)
return 0;
return obj.Id.GetHashCode();
}
}使用Distinct去重的时候只需要这样就可以了：
var dist1 = personList.Distinct(new PersonIdComparer()).ToList();看起来很简单的一个去重操作，却要每次都要新建一个类，然后实现它的两个方法。而且在需求变更的同时，这个类还不能很好的适应变化，譬如现在我们需要根据Name字段去重，那么我们又需要新建一个PersonNameComparer类，当我们需要根据Age字段去重的时候，又需要新建一个PersonAgeComparer类，如此反复，非常繁琐，为什么我们不能写一个通用的类直接根据某个字段来去重呢？ LoveJenny在《Linq的Distinct太不给力了》这篇博文中使用泛型、反射和表达式树的方法实现了一个PropertyComparer类，这个类可以很好的适应上面的变化。另外这篇文章也有类似的实现。
三、简化IEqualityComparer的实现
LoveJenny的博文给出的解决方法虽然满足了适应变化的能力，但在使用上仍然感觉不是很便捷，为什么我们不能像LINQ中的其他方法如OrderBy(x => x.Id)这样使用lambda表达式来去重呢？鹤冲天在他的两篇博文《c# 扩展方法奇思妙用基础篇八：Distinct 扩展》和《何止 Linq 的 Distinct 不给力》中介绍了一种更简单通用的实现IEqualityComparer接口的方法，并通过结合C#的扩展方法使得LINQ中的Distinct使用起来非常便捷。下面直接上代码：
public static class Equality<T>
{
public static IEqualityComparer<T> CreateComparer<V>(Func<T, V> keySelector)
{
return new CommonEqualityComparer<V>(keySelector);
}
public static IEqualityComparer<T> CreateComparer<V>(
Func<T, V> keySelector, IEqualityComparer<V> comparer)
{
return new CommonEqualityComparer<V>(keySelector, comparer);
}
class CommonEqualityComparer<V> : IEqualityComparer<T>
{
private Func<T, V> keySelector;
private IEqualityComparer<V> comparer;
public CommonEqualityComparer(
Func<T, V> keySelector, IEqualityComparer<V> comparer)
{
this.keySelector = keySelector;
this.comparer = comparer;
}
public CommonEqualityComparer(Func<T, V> keySelector)
: this(keySelector, EqualityComparer<V>.Default)
{ }
public bool Equals(T x, T y)
{
return comparer.Equals(keySelector(x), keySelector(y));
}
public int GetHashCode(T obj)
{
return comparer.GetHashCode(keySelector(obj));
}
}
}
public static class DistinctExtensions
{
public static IEnumerable<T> DistinctBy<T, V>(
this IEnumerable<T> source, Func<T, V> keySelector)
{
return source.Distinct(Equality<T>.CreateComparer(keySelector));
}
public static IEnumerable<T> DistinctBy<T, V>(
this IEnumerable<T> source, Func<T, V> keySelector, IEqualityComparer<V> comparer)
{
return source.Distinct(Equality<T>.CreateComparer(keySelector, comparer));
}
}原文中的方法名保持了LINQ中的Distinct不变，我这里改成了DistinctBy，这样和OrderBy、GroupBy相一致，而且在使用的时候personList.DistinctBy(x => x.Id)在语义上感觉更清晰。而且这里的Equality静态类，可以为我们很方便的创建IEqualityComparer接口，直接通过lambda表达式就可以而不需要再另外定义一个类了，譬如：var idComparer = Equality<Person>.CreateComparer(x => x.Id)。
四、第三方库中的解决方法
4.1 morelinq
morelinq是一个关于linq的开源项目，添加了一些很实用的扩展方法，像Exclude、MinBy、MaxBy、TakeEvery等等，当然还有我们这里讲的DistinctBy，用法和上面的一样：personList.DistinctBy(x => x.Id)就可以了。我们这里主要关心它的实现方法，因为它并没有通过实现IEqualityComparer接口来，而是巧妙的利用了C#中的HashSet类型和yield关键字，实现了去重的目的。我将无关部分剔除，关键代码如下：
static partial class MoreEnumerable
{
public static IEnumerable<TSource> DistinctBy<TSource, TKey>(
this IEnumerable<TSource> source, Func<TSource, TKey> keySelector)
{
return source.DistinctBy(keySelector, null);
}
public static IEnumerable<TSource> DistinctBy<TSource, TKey>(
this IEnumerable<TSource> source,
Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
{
return DistinctByImpl(source, keySelector, comparer);
}
private static IEnumerable<TSource> DistinctByImpl<TSource, TKey>(
IEnumerable<TSource> source,
Func<TSource, TKey> keySelector, IEqualityComparer<TKey> comparer)
{
var knownKeys = new HashSet<TKey>(comparer);
foreach (var element in source)
{
if (knownKeys.Add(keySelector(element)))
{
yield return element;
}
}
}
}具体的实现在DistinctByImpl这个方法里，首先新建一个HashSet，然后通过Add方法将元素添加到HashSet中，如果元素已存在Add方法返回false，则会继续插入下一个元素直到下一个元素插入成功，然后通过yield返回。需要注意的是HashSet接受一个IEqualityComparer类型的参数，如果HashSet的key是个对象而不是简单类型，则需要和我们上面一样定义一个类实现IEqualityComparer接口了。
4.2 Miscellaneous Utility Library
MiscUtil是一个C#的工具包大杂烩，它有各种辅助方法可以方便我们的开发工作。其中有一个ProjectionEqualityComparer类是和上面介绍的鹤冲天的Equality<T>类几乎完全一样，具体实现可以去看下它的源代码。唯一的区别在于它提供了两个ProjectionEqualityComparer类的实现，一个是ProjectionEqualityComparer，另一个是ProjectionEqualityComparer<TSource>。如下：
public static class ProjectionEqualityComparer
{
public static ProjectionEqualityComparer<TSource, TKey>
Create<TSource, TKey>(Func<TSource, TKey> projection)
{
return new ProjectionEqualityComparer<TSource, TKey>(projection);
}
}
public static class ProjectionEqualityComparer<TSource>
{
public static ProjectionEqualityComparer<TSource, TKey>
Create<TKey>(Func<TSource, TKey> projection)
{
return new ProjectionEqualityComparer<TSource, TKey>(projection);
}
}这样当我们需要实现IEqualityComparer接口时可以有更多的选择，如下所示。我们注意到CreateComparer<int>可以简写成CreateComparer，所以ProjectionEqualityComparer<Person>.CreateComparer(x => x.Id)这种写法可能要更实用一点。
var c1 = ProjectionEqualityComparer.CreateComparer<Person, int>(x => x.Id);
var c2 = ProjectionEqualityComparer<Person>.CreateComparer<int>(x => x.Id);
var c3 = ProjectionEqualityComparer<Person>.CreateComparer(x => x.Id);4.3 AnonymousComparer
最后我们再来看下codeplex上的一个项目：AnonymousComparer，它可以通过lambda表达式直接创建匿名类实现IComparer<T>或IEqualityComparer<T>接口。所以通过AnonymousComparer不仅简化了IEqualityComparer接口的实现，还简化了IComparer接口，IComparer接口在LINQ中的很多方法如OrderBy、GroupBy、Contains等中有着广泛的应用。AnonymousComparer实现IEqualityComparer的方式大同小异，但是有一点不同的是，它提供了一种Full IEqualtyComparer<T> overload，这样我们可以在代码里完全通过lambda实现IEqualtyComparer的两个方法：Equals和GetHashCode。而上面所介绍的其他方法中都是将这两个方法封装起来的。
public static IEqualityComparer<T> Create<T, TKey>(Func<T, TKey> compareKeySelector)
{
if (compareKeySelector == null) throw new ArgumentNullException("compareKeySelector");
return new EqualityComparer<T>(
(x, y) =>
{
if (object.ReferenceEquals(x, y)) return true;
if (x == null || y == null) return false;
return compareKeySelector(x).Equals(compareKeySelector(y));
},
obj =>
{
if (obj == null) return 0;
return compareKeySelector(obj).GetHashCode();
});
}
public static IEqualityComparer<T> Create<T>(Func<T, T, bool> equals, Func<T, int> getHashCode)
{
if (equals == null) throw new ArgumentNullException("equals");
if (getHashCode == null) throw new ArgumentNullException("getHashCode");
return new EqualityComparer<T>(equals, getHashCode);
}
private class EqualityComparer<T> : IEqualityComparer<T>
{
private readonly Func<T, T, bool> equals;
private readonly Func<T, int> getHashCode;
public EqualityComparer(Func<T, T, bool> equals, Func<T, int> getHashCode)
{
this.equals = equals;
this.getHashCode = getHashCode;
}
public bool Equals(T x, T y)
{
return equals(x, y);
}
public int GetHashCode(T obj)
{
return getHashCode(obj);
}
}还是用Person列表根据Id去重的例子，这个Comparer可以写成这样（写起来可能会没有上面的方便快捷，但是可以实现更强大的定制功能，譬如要根据多列来去重或根据某种算法来去重而不是简单的根据单列去重）：
var idComparer = AnonymousComparer.Create<Person>(
(x, y) => x.Id == y.Id, // Equals
obj => obj.Id.GetHashCode() // GetHashCode
);五、最简单的解决方法
上面说了这么多，大多是通过实现IEqualityComparer接口的，也有根据HashSet和yield实现的。但是其实通过LINQ自带的GroupBy方法也可以实现去重的目的，像下面这样：
var dist = personList.GroupBy(x => x.Id).Select(x => x.First());尽管在性能上有一定的折扣，在可读性方面也不容易让人理解，但这确实应该算是最简单的做法。这让我想起了SQL中的去重，SQL语言中DISTINCT是根据所有字段来去重的，如果需要根据某一列或几列来去重也会使用GROUP BY，类似于：
SELECT * FROM Person GROUP BY Id从这一点看上去，LINQ真的和SQL有着惊人的相似。
参考
- Distinct() with lambda?
- Can I specify my explicit type comparator inline?
- Distinct list of objects based on an arbitrary key in LINQ
- Linq的Distinct太不给力了
- c# 扩展方法奇思妙用基础篇八：Distinct 扩展
- 何止 Linq 的 Distinct 不给力
- morelinq - Extensions to LINQ to Objects
- Miscellaneous Utility Library
- AnonymousComparer - lambda compare selector for Linq
- 快速创建 IEqualityComparer 和 IComparer 的实例
- A Generic IEqualityComparer for Linq Distinct()
