Come trovare gli oggetti in un superset che non sono in un sottogruppo

Question

So che c'è un "no" su IEnumerable grazie al LINQ che prende una collezione di non contro, ma sono preoccupato per grande oh prestazioni Qual è l'algoritmo più veloce per fare questo?

Answer 1

L'unico modo per rimuovere un sottoinsieme di articoli di un IEnumerable<T> è un ciclo tra il sovrainsieme e per ciascun elemento nel loop sovrainsieme attraverso il sottoinsieme, rimuovendo tale elemento dal superset se viene trovato nel sottoinsieme.

Questo vi darà O (n²) , in media.

Ora, se c'è ulteriori informazioni su queste raccolte (forse uno o di entrambi è un elenco o forse uno o entrambi delle sequenze sono ordinati) che potrebbero aiutare a creare una soluzione più performante.

Se siete interessati, qui è un metodo di estensione che farà quello che ho appena descritto:

public static IEnumerable<T> Exclude<T>
    (this IEnumerable<T> source, IEnumerable<T> items)
{
    foreach (T t in source)
        if (!items.Contains(t))
            yield return t;
}

---

Nevermind, utilizzare il Enumerable.Except metodo di estensione:

  

Produce la differenza di set di due sequenze.

Answer 2

Se è possibile scorrere i gruppi in ordine, è possibile garantire O (n) il comportamento (piuttosto che il "genere O (n), ma forse O (n²) nel caso peggiore" che un hashset ha) scorrendo entrambi in sincronia.

Ad esempio:

//loop boilerplate
if(itemA < itemB) {
    itemA = a.next();
    continue;
}
if(itemA > itemB) {
    itemB = b.next();
    continue;
}
a.remove(itemA);

È necessario aggiungere il controllo di frontiera ed altri boilerplate te stesso.

Answer 3

È possibile ottenere prestazioni migliori convertendo il superset in una tabella hash (O (n) in genere, ma poi consente di eseguire ricerche in tempo costante). Poi si può enumerare il sottoinsieme e controllare se ogni elemento presente nella superset. L'intera operazione dovrebbe prendere O (n) di memoria in più e O (n).