Join two ordered sequences efficiently in C#

user_2707705 0
Viewed 359

Presume these two ordered sequences:

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

Knowing that elements from both sequences are ordered, how can they be inner-joined more efficiently than with Enumerable.Join to produce the following sequence of tuples?

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

Notice that, unlike with Enumerable.Intersect that produces only distinct elements from both sequences, the output sequence here returns tuples that represent every combination of elements from a one-to-one, one-to-many or many-to-many relationship.

The semantics are much the same as INNER JOIN in SQL Server. But, more specifically, I'm looking for a C# implementation with the performance characteristics of the merge join algorithm (INNER MERGE JOIN) that returns an IEnumerable with deferred execution.

The required method signature might look something like this:

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)
enumeration linq performance c#
2 Answers

MoreEnumerable.OrderedMerge from MoreLinq library does the job if both sequences are sorted.

https://github.com/morelinq/MoreLINQ

using MoreLinq;

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

Efficiency is good, compared to inner join. When N and M are the length of each sequence, Inner join makes a cartesian product so time is proportional to NxM OrderedMerge traverse each collection once so time is proportional to N+M

If the sequences are not sorted, the standard Linq Enumerable.OrderBy will do the job.

There are also some overloads:

// 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
user_52957970
Related