在C#中有效地加入两个有序序列

发布时间：2020-12-15 22:44:41 所属栏目：百科来源：网络整理

导读：设定这两个有序序列： var outer = new char[] { 'a','b','c','d','e' };var inner = new char[] { 'a','d' }; 知道两个序列中的元素是有序的,它们如何比Enumerable.Join更有效地内部连接以产生以下序列的元组？ { 'a','a' }{ 'b','b' }{ 'b','b' }{ 'c','c'

设定这两个有序序列：

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

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

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

请注意,与Enumerable.Intersect不同,Enumerable.Intersect只生成两个序列中的不同元素,此处的输出序列返回元组,这些元组表示一对一,一对多或多对多关系中的每个元素组合.

语义与SQL Server中的INNER JOIN非常相似.但是,更具体地说,我正在寻找具有merge join算法(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,TResult> resultSelector)

解决方法

我不知道任何现有的Enumerable扩展方法可以实现这一点,并且没有人应该花费比我更多的时间来提出这个.

public static IEnumerable<TResult> MergeJoin<TOuter,TResult>(this IEnumerable<TOuter> outer,TResult> resultSelector)
{
    if (outer == null)
        throw new ArgumentNullException(nameof(outer));

    if (inner == null)
        throw new ArgumentNullException(nameof(inner));

    if (outerKeySelector == null)
        throw new ArgumentNullException(nameof(outerKeySelector));

    if (innerKeySelector == null)
        throw new ArgumentNullException(nameof(innerKeySelector));

    if (resultSelector == null)
        throw new ArgumentNullException(nameof(resultSelector));

    return MergeJoinIterator(outer,inner,outerKeySelector,innerKeySelector,resultSelector,Comparer<TKey>.Default);
}

public static IEnumerable<TResult> MergeJoin<TOuter,TResult> resultSelector,IComparer<TKey> comparer)
{
    if (outer == null)
        throw new ArgumentNullException(nameof(outer));

    if (inner == null)
        throw new ArgumentNullException(nameof(inner));

    if (outerKeySelector == null)
        throw new ArgumentNullException(nameof(outerKeySelector));

    if (innerKeySelector == null)
        throw new ArgumentNullException(nameof(innerKeySelector));

    if (resultSelector == null)
        throw new ArgumentNullException(nameof(resultSelector));

    if (comparer == null)
        throw new ArgumentNullException(nameof(comparer));

    return MergeJoinIterator(outer,comparer);
}

private static IEnumerable<TResult> MergeJoinIterator<TOuter,TResult>(IEnumerable<TOuter> outer,IComparer<TKey> comparer)
{
    IEnumerator<TOuter> outerEnumerator = outer.GetEnumerator();

    if (!outerEnumerator.MoveNext())
        yield break;

    IEnumerator<TInner> innerEnumerator = inner.GetEnumerator();

    if (!innerEnumerator.MoveNext())
        yield break;

    TOuter outerElement = outerEnumerator.Current;
    TKey outerKey = outerKeySelector(outerElement);

    TInner innerElement = innerEnumerator.Current;
    TKey innerKey = innerKeySelector(innerElement);

    int comp = comparer.Compare(innerKey,outerKey);

    while (true)
    {
        if (comp < 0)
        {
            if (!innerEnumerator.MoveNext())
                break;

            innerElement = innerEnumerator.Current;
            innerKey = innerKeySelector(innerElement);
            comp = comparer.Compare(innerKey,outerKey);
            continue;
        }

        if (comp > 0)
        {
            if (!outerEnumerator.MoveNext())
                break;

            outerElement = outerEnumerator.Current;
            outerKey = outerKeySelector(outerElement);
            comp = comparer.Compare(innerKey,outerKey);
            continue;
        }

        yield return resultSelector(outerElement,innerElement);

        if (!outerEnumerator.MoveNext())
        {
            while (true)
            {
                if (!innerEnumerator.MoveNext())
                    break;

                innerElement = innerEnumerator.Current;
                innerKey = innerKeySelector(innerElement);
                comp = comparer.Compare(innerKey,outerKey);

                if (comp != 0)
                    break;

                yield return resultSelector(outerElement,innerElement);
            }

            break;
        }

        if (!innerEnumerator.MoveNext())
        {
            while (true)
            {
                outerElement = outerEnumerator.Current;
                outerKey = outerKeySelector(outerElement);
                comp = comparer.Compare(innerKey,innerElement);

                if (!outerEnumerator.MoveNext())
                    break;
            }

            break;
        }

        TOuter outerElementNext = outerEnumerator.Current;
        TKey outerKeyNext = outerKeySelector(outerElementNext);

        TInner innerElementNext = innerEnumerator.Current;
        TKey innerKeyNext = innerKeySelector(innerElementNext);

        comp = comparer.Compare(outerKeyNext,outerKey);
        bool stop = false;

        if (comp != 0)
        {
            comp = comparer.Compare(innerKeyNext,innerKey);

            if (comp == 0)
            {
                yield return resultSelector(outerElement,innerElementNext);

                while (true)
                {
                    if (!innerEnumerator.MoveNext())
                    {
                        stop = true;
                        break;
                    }

                    innerElementNext = innerEnumerator.Current;
                    innerKeyNext = innerKeySelector(innerElementNext);
                    comp = comparer.Compare(innerKeyNext,outerKey);

                    if (comp != 0)
                        break;

                    yield return resultSelector(outerElement,innerElementNext);
                }

                if (stop)
                    break;
            }

            outerElement = outerElementNext;
            outerKey = outerKeyNext;
            innerElement = innerElementNext;
            innerKey = innerKeyNext;
            comp = comparer.Compare(innerKey,outerKey);
            continue;
        }

        comp = comparer.Compare(innerKeyNext,innerKey);

        if (comp != 0)
        {
            yield return resultSelector(outerElementNext,innerElement);

            while (true)
            {
                if (!outerEnumerator.MoveNext())
                {
                    stop = true;
                    break;
                }

                outerElementNext = outerEnumerator.Current;
                outerKeyNext = outerKeySelector(outerElementNext);
                comp = comparer.Compare(innerKey,outerKeyNext);

                if (comp != 0)
                    break;

                yield return resultSelector(outerElementNext,innerElement);
            }

            if (stop)
                break;

            outerElement = outerElementNext;
            outerKey = outerKeyNext;
            innerElement = innerElementNext;
            innerKey = innerKeyNext;
            comp = comparer.Compare(innerKey,innerElementNext);
        var innerRest = new List<TInner>();

        TInner innerElementFollowing = default(TInner);
        TKey innerKeyFollowing = default(TKey);

        while (true)
        {
            if (!innerEnumerator.MoveNext())
            {
                stop = true;
                break;
            }

            innerElementFollowing = innerEnumerator.Current;
            innerKeyFollowing = innerKeySelector(innerElementFollowing);
            comp = comparer.Compare(innerKeyFollowing,outerKey);

            if (comp != 0)
                break;

            yield return resultSelector(outerElement,innerElementFollowing);
            innerRest.Add(innerElementFollowing);
        }

        yield return resultSelector(outerElementNext,innerElement);
        yield return resultSelector(outerElementNext,innerElementNext);

        for (int i = 0; i < innerRest.Count; i++)
            yield return resultSelector(outerElementNext,innerRest[i]);

        while (true)
        {
            if (!outerEnumerator.MoveNext())
            {
                stop = true;
                break;
            }

            outerElementNext = outerEnumerator.Current;
            outerKeyNext = outerKeySelector(outerElementNext);
            comp = comparer.Compare(innerKey,outerKeyNext);

            if (comp != 0)
                break;

            yield return resultSelector(outerElementNext,innerElement);
            yield return resultSelector(outerElementNext,innerElementNext);

            for (int i = 0; i < innerRest.Count; i++)
                yield return resultSelector(outerElementNext,innerRest[i]);
        }

        if (stop)
            break;

        outerElement = outerElementNext;
        outerKey = outerKeyNext;
        innerElement = innerElementFollowing;
        innerKey = innerKeyFollowing;
        comp = comparer.Compare(innerKey,outerKey);
    }
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!