C# LINQ： 有序连接和分组惰性运算符
5.00/5 (12投票s)
用于有序序列的 IEnumerable 扩展，
引言
本文介绍了一种可能的 Join 和 GroupJoin LINQ 扩展的实现，该实现假设源数据是有序的（预先排序）。利用这个假设，让我们构建连接和分组逻辑，使用惰性求值，而不是标准 LINQ 的 Join 和 GroupJoin 运算符，后者需要将整个序列预先加载到内存中。
虽然本文使用 C#，但该技术适用于所有 .NET 语言。
背景
假设我们有两个数据集 – Master 和 Detail。它们都包含大量按 Master ID 字段排序的记录，并且具有主/从关系。数据集不一定存储在数据库中，它们可以位于任何位置（在我们的示例中，我们将动态生成假数据序列）。现在的任务是从两个序列中读取数据，按 Master ID 将结果连接在一起，并在结果序列上执行一些操作（在我们的示例中只是打印）。当然，如果数据存储在数据库中，我们可以编写一个 SQL JOIN 语句，让 SQL Server 执行连接。但为了演示，让我们尝试自己实现连接和分组，就在 C# 代码中。
数据结构
在我们的演示中，我们将使用以下名为 MasterData 和 DetailData 的数据结构
public struct MasterData
{
public int MasterId { get; set; }
public string Data
{
get { return string.Format("MASTER(Master ID: {0})", MasterId); }
}
}
public struct DetailData
{
public int MasterId { get; set; }
public int DetailId { get; set; }
public string Data
{
get { return string.Format("DETAIL(Master ID: {0}, Detail ID: {1})", MasterId, DetailId); }
}
}
我们还将使用 PrintData 辅助扩展方法来打印数据
public static class PrintingExtensions
{
public static void PrintData(this IEnumerable<Tuple<MasterData, MasterData>> data)
{
foreach (var masterItem in data)
Console.WriteLine("{0} <===> {1}", masterItem.Item1.Data, masterItem.Item2.Data);
}
public static void PrintData(this IEnumerable<Tuple<MasterData, IEnumerable<DetailData>>> data)
{
foreach (var masterItem in data)
{
Console.WriteLine(masterItem.Item1.Data);
foreach (var detailItem in masterItem.Item2)
Console.WriteLine("\t{0}", detailItem.Data);
}
}
}
最后是两种生成示例数据序列的方法
private static IEnumerable<MasterData> GetMasterData(int count)
{
return Enumerable.Range(1, count).Select(m => new MasterData {MasterId = m});
}
private static IEnumerable<DetailData> GetDetailData(int count)
{
return Enumerable.Range(1, count).SelectMany(m =>
Enumerable.Range(1, 5).Select(d => new DetailData {MasterId = m, DetailId = d}));
}
GroupJoin - 标准方法
以下是如何使用标准 GroupJoin LINQ 运算符来完成它
private const int c_count = 10*1000*1000;
private const int c_skipCount = 1*1000*1000;
private const int c_takeCount = 3;
void Main()
{
var masterData = GetMasterData(c_count);
var detailData = GetDetailData(c_count);
masterData.GroupJoin(detailData, m => m.MasterId, d => d.MasterId, Tuple.Create)
.Skip(c_skipCount).Take(c_takeCount).PrintData();
}
对于相对较短的序列，这可以很好地工作，但当项目数量很大时，例如在本例中，执行变得不是很理想，因为标准 LINQ GroupJoin 运算符需要首先将整个序列加载到内存中，以便连接和分组可以为甚至无序的序列正确工作。
但是，根据我们的初始要求，两个序列都应该按 Master ID 排序。 如果是真的，那么如果我们能以惰性的方式获得相同的结果，为什么要读取整个序列呢？ 让我们看看它可能是什么样子。
GroupJoin - 优化方法
为了利用数据集是有序的事实，我在 IEnumerable<T> 上创建了一些扩展方法。 这是一个例子，它给出了与前一个相同的结果，但更快更优化
private const int c_count = 10*1000*1000;
private const int c_skipCount = 1*1000*1000;
private const int c_takeCount = 3;
void Main()
{
var masterData = GetMasterData(c_count);
var detailData = GetDetailData(c_count);
masterData.OrderedEqualityGroupJoin(detailData, m => m.MasterId, d => d.MasterId, Tuple.Create)
.Skip(c_skipCount).Take(c_takeCount).PrintData();
}
OrderedEqualityGroupJoin 运算符以及 OrderedCompareGroupJoin 在内部使用以下类来实现惰性求值
private class FilteredEnumerator<T> : IDisposable
{
private bool m_hasData;
private readonly IEnumerator<T> m_enumerator;
public FilteredEnumerator(IEnumerable<T> sequence)
{
m_enumerator = sequence.GetEnumerator();
m_hasData = m_enumerator.MoveNext();
}
public IEnumerable<T> SkipAndTakeWhile(Predicate<T> filter)
{
while (m_hasData && !filter(m_enumerator.Current))
m_hasData = m_enumerator.MoveNext();
while (m_hasData && filter(m_enumerator.Current))
{
yield return m_enumerator.Current;
m_hasData = m_enumerator.MoveNext();
}
}
public IEnumerable<T> SkipAndTakeWhile(Func<T, int> comparer)
{
while (m_hasData && comparer(m_enumerator.Current) > 0)
m_hasData = m_enumerator.MoveNext();
while (m_hasData && comparer(m_enumerator.Current) == 0)
{
yield return m_enumerator.Current;
m_hasData = m_enumerator.MoveNext();
}
}
public void Dispose()
{
m_enumerator.Dispose();
}
}
FilteredEnumerator 将跳过所有 Detail 记录，直到找到与当前 Master 键匹配的记录，并且只会选择那些匹配的记录。 两者之间的区别在于 OrderedEqualityGroupJoin 基于键的相等性，而 OrderedCompareGroupJoin 基于比较键。 当存在一些没有相应 Detail 记录的 Master 记录时，这一点变得很重要。 在这种情况下，基于键的相等性的运算符可能会跳过整个序列，但基于比较键的运算符只会跳过键小于当前 Master ID 的详细信息记录。
内连接和外连接
到目前为止，我们讨论了 Group Joining，现在是时候看看 Join 运算符了。 附加的源代码包含内连接、外全连接、左连接和右连接的实现，同样，假设内部和外部序列都是有序的。
该实现基于 OrderedJoinIterator，它基本上遍历两个序列，并根据键的比较和连接类型，产生返回内部记录或外部记录，或它们的默认值。
static IEnumerable<TResult> OrderedJoinIterator<TOuter, TInner, TKey, TResult>(
this IEnumerable<TOuter> outer,
IEnumerable<TInner> inner,
Func<TOuter, TKey> outerKeySelector,
Func<TInner, TKey> innerKeySelector,
Func<TOuter, TInner, TResult> resultSelector,
JoinType jt, IComparer<TKey> comparer)
{
if (comparer == null)
comparer = Comparer<TKey>.Default;
var l = outer.GetEnumerator();
var r = inner.GetEnumerator();
var lHasData = l.MoveNext();
var rHasData = r.MoveNext();
while (lHasData || rHasData)
{
if (!lHasData)
{
if (jt == JoinType.Inner || jt == JoinType.Left)
yield break;
yield return resultSelector(default(TOuter), r.Current);
rHasData = r.MoveNext();
continue;
}
if (!rHasData)
{
if (jt == JoinType.Inner || jt == JoinType.Right)
yield break;
yield return resultSelector(l.Current, default(TInner));
lHasData = l.MoveNext();
continue;
}
var comp = comparer.Compare(outerKeySelector(l.Current), innerKeySelector(r.Current));
if (comp < 0)
{
if (jt == JoinType.Left || jt == JoinType.Full)
yield return resultSelector(l.Current, default(TInner));
lHasData = l.MoveNext();
}
else if (comp > 0)
{
if (jt == JoinType.Right || jt == JoinType.Full)
yield return resultSelector(default(TOuter), r.Current);
rHasData = r.MoveNext();
}
else
{
yield return resultSelector(l.Current, r.Current);
lHasData = l.MoveNext();
rHasData = r.MoveNext();
}
}
}
提供的 OrderedJoin 运算符的签名和行为与标准 LINQ Join 运算符相同。 以下是这些运算符的列表
OrderedInnerJoin：返回具有匹配键的内部和外部记录。OrderedFullJoin：返回所有内部和外部记录。 如果键在任何一侧都不匹配，则将返回类型的默认值。OrderedLeftJoin：返回所有外部记录，以及匹配的内部记录或其类型的默认值。OrderedRightJoin：返回所有内部记录，以及匹配的外部记录或其类型的默认值。
结论
LINQ 是一项非常强大的技术，可以非常容易地实现所需的功能，而无需用户代码添加额外的复杂性。 虽然 LINQ-to-Objects 中标准连接和分组运算符的行为并非针对有序序列，但扩展方法、lambda 和 yield 返回 IEnumerable<T> 元素的架构，可以很好地协同工作，并允许创建具有所需功能的新运算符。