Differenza simmetrica stabile, basata su hash

Un sacco di pensiero è andato nell'implementazione degli algoritmi dell'insieme in LINQ: Distinct , Except , Intersect e Union . Garantiscono che gli articoli vengano restituiti nello stesso ordine in cui appaiono prima di chiamare il metodo. Quindi, queste due espressioni restituiscono gli articoli nello stesso ordine:

var authors1 = books.Select(b => b.Author).OrderBy(a => a).Distinct();
var authors2 = books.Select(b => b.Author).Distinct().OrderBy(a => a);

L'implementazione di Distinct sarebbe simile a questa:

public IEnumerable<T> Distinct<T>(this IEnumerable<T> source)
{
    HashSet<T> set = new HashSet<T>();
    foreach (T item in source)
    {
        if (set.Add(item))
        {
            yield return item;
        }
    }
}

L'implementazione di Except sarà simile a questa:

public static IEnumerable<T> Except<T>(this IEnumerable<T> source1, IEnumerable<T> source2)
{
    HashSet<T> set = new HashSet<T>(source2);
    foreach (T item in source1)
    {
        if (set.Add(item))
        {
            yield return item;
        }
    }
}

L'implementazione di Intersect sarebbe simile a questa:

public static IEnumerable<T> Intersect<T>(this IEnumerable<T> source1, IEnumerable<T> source2)
{
    HashSet<T> set = new HashSet<T>(source2);
    HashSet<T> found = new HashSet<T>();
    foreach (T item in source1)
    {
        if (set.Contains(item) && found.Add(item))
        {
            yield return item;
        }
    }
}

Ho aggiunto un secondo set per rimuovere i duplicati dalla lista.

Infine, Union è un po 'più complesso, ma fondamentalmente la stessa cosa:

public static IEnumerable<T> Union<T>(this IEnumerable<T> source1, IEnumerable<T> source2)
{
    HashSet<T> set = new HashSet<T>();
    foreach (T item in source1)
    {
        if (set.Add(item))
        {
            yield return item;
        }
    }
    foreach (T item in source2)
    {
        if (set.Add(item))
        {
            yield return item;
        }
    }
}

Quindi, l'unica operazione non supportata da LINQ è la differenza simmetrica o SymmetricExcept . Ho giocato con la creazione di una versione "stabile" di questo algoritmo e per pura curiosità mi chiedo se ci sia una migliore implementazione. L'implementazione più immediata consiste nel chiamare semplicemente Except due volte:

public static IEnumerable<T> SymmetricExcept<T>(this IEnumerable<T> source1, IEnumerable<T> source2)
{
    var except1 = source1.Except(source2);
    var except2 = source2.Except(source1);
    return except1.Concat(except2);
}

Sebbene ciò richieda di esaminare entrambe le liste due volte. Così ho scritto una versione che richiede solo di passare attraverso la seconda lista due volte:

public static IEnumerable<T> SymmetricExcept<T>(this IEnumerable<T> source1, IEnumerable<T> source2)
{
    HashSet<T> set = new HashSet<T>(source2);
    HashSet<T> found = new HashSet<T>();
    foreach (T item in source1)
    {
        if (!set.Contains(item) && found.Add(item))
        {
            yield return item;
        }
    }
    foreach (T item in source2)
    {
        if (found.Add(item))
        {
            yield return item;
        }
    }
}

Non ho verificato la correttezza di questi algoritmi. C'è qualche ambiguità su come LINQ gestisce i duplicati. Sono curioso di sapere se esiste un modo più efficiente di fare SymmetricExcept , qualcosa di meglio di O(m + 2n) .