在 C# 中有效地连接两个有序序列

Question

假设这两个有序序列：

var outer = new char[] { 'a', 'b', 'b', 'c', 'd', 'd', 'e' };
var inner = new char[] { 'a', 'b', 'c', 'c', 'd', 'd' };

知道来自两个序列的元素是有序的，它们如何比 with 更有效地进行内部连接Enumerable.Join以产生以下元组序列？

{ 'a', 'a' }
{ 'b', 'b' }
{ 'b', 'b' }
{ 'c', 'c' }
{ 'c', 'c' }
{ 'd', 'd' }
{ 'd', 'd' }
{ 'd', 'd' }
{ 'd', 'd' }

请注意，与Enumerable.Intersect仅从两个序列中生成不同元素的方法不同，此处的输出序列返回表示一对一、一对多或多对多关系中元素的每个组合的元组。

语义与INNER JOINSQL Server 中的语义非常相似。但是，更具体地说，我正在寻找具有合并连接算法 ( INNER MERGE JOIN)性能特征的 C# 实现，该算法返回IEnumerable延迟执行。

所需的方法签名可能如下所示：

IEnumerable<TResult> MergeJoin<TOuter, TInner, TKey, TResult>(
    this IEnumerable<TOuter> outer, 
    IEnumerable<TInner> inner, 
    Func<TOuter, TKey> outerKeySelector, 
    Func<TInner, TKey> innerKeySelector, 
    Func<TOuter, TInner, TResult> resultSelector)

Answer 1

MoreEnumerable.OrderedMerge如果两个序列都已排序，则来自MoreLinq库的工作将完成。

https://github.com/morelinq/MoreLINQ

using MoreLinq;

IEnumerable<char> result = outer.OrderedMerge(innner);

与内连接相比，效率很好。当 N 和 M 是每个序列的长度时，内连接会生成笛卡尔积，因此时间与 NxM 成正比 OrderedMerge 遍历每个集合一次，因此时间与 N+M 成正比

如果序列未排序，标准Linq Enumerable.OrderBy将完成这项工作。

还有一些重载：

// to provide a custom comparison criteria
public static IEnumerable<T> OrderedMerge<T>(this IEnumerable<T> first, IEnumerable<T> second, IComparer<T> comparer);

// to provide the key for comparisons
IEnumerable<T> OrderedMerge<T, TKey>(this IEnumerable<T> first, IEnumerable<T> second, Func<T, TKey> keySelector);

// + other overloads to select element to be merged when first element is less than second, 
// when second element is less than first 
// when first and second element are equal