C # Intersection la plus rapide de 2 séries de nombres triés

Si vous avez deux ensembles qui sont à la fois triés, vous pouvez mettre en œuvre une intersection plus rapide que tout prévu sur la boîte avec LINQ.

En gros, garder deux IEnumerator code> curseurs ouverts, un pour chaque ensemble. À tout moment, l'avance selon celui qui a la plus petite valeur. S'ils correspondent à n'importe quel point, avancez-les à la fois, etc. jusqu'à ce que vous atteigniez la fin de l'un ou l'autre itérateur. P>

La bonne chose à ce sujet est que vous n'avez besoin que d'itérer sur chaque ensemble une fois, et vous pouvez . le faire en O (1) mémoire p>

Voici une exemple d'implémentation - non testé, mais il ne compile :) il suppose que les deux séquences entrantes sont sans doublons et triés, à la fois selon le comparateur prévu (passe dans Comparer .Default code>): p>

(Il y a plus de texte à la fin de la réponse!) p>

static IEnumerable<T> IntersectSorted<T>(this IEnumerable<T> sequence1,
    IEnumerable<T> sequence2,
    IComparer<T> comparer)
{
    using (var cursor1 = sequence1.GetEnumerator())
    using (var cursor2 = sequence2.GetEnumerator())
    {
        if (!cursor1.MoveNext() || !cursor2.MoveNext())
        {
            yield break;
        }
        var value1 = cursor1.Current;
        var value2 = cursor2.Current;

        while (true)
        {
            int comparison = comparer.Compare(value1, value2);
            if (comparison < 0)
            {
                if (!cursor1.MoveNext())
                {
                    yield break;
                }
                value1 = cursor1.Current;
            }
            else if (comparison > 0)
            {
                if (!cursor2.MoveNext())
                {
                    yield break;
                }
                value2 = cursor2.Current;
            }
            else
            {
                yield return value1;
                if (!cursor1.MoveNext() || !cursor2.MoveNext())
                {
                    yield break;
                }
                value1 = cursor1.Current;
                value2 = cursor2.Current;
            }
        }
    }
}