Comment trouver des articles dans un surensemble qui ne sont pas dans un sous-ensemble

Question

Je sais qu'il ya un « non » sur IEnumerable grâce à LINQ qui prend une collection à ne pas contre, mais je suis inquiet au sujet de la performance grande oh Quel est l'algorithme le plus rapide de le faire?

Answer 1

La seule façon d'enlever un sous-ensemble d'éléments à partir d'un IEnumerable<T> est de boucle à travers le surensemble et pour chaque élément dans la boucle de surensemble par l'intermédiaire du sous-ensemble, en supprimant cet élément du surensemble si elle se trouve dans le sous-ensemble.

Cela vous donnera O (n²) en moyenne.

Maintenant, s'il y a des informations supplémentaires sur ces collections (peut-être un ou deux est une liste ou peut-être un ou sont triés les deux séquences) qui pourraient vous aider à créer une solution plus performante.

Si vous êtes intéressé, voici une méthode d'extension qui va faire ce que je viens de décrire:

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 utiliser le Enumerable.Except procédé d'extension:

  

Produit la différence entre deux séquences.

Answer 2

Si vous pouvez itérer sur les jeux dans l'ordre, vous pouvez garantir O comportement (n) (plutôt que le « typiquement O (n) mais peut-être O (n²) dans le pire des cas » que HashSet a) par itérer les deux au même rythme.

Par exemple:

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

Vous devrez ajouter une vérification et d'autres limites boilerplate vous.

Answer 3

Vous pouvez obtenir de meilleures performances en convertissant le surensemble en une table de hachage (O (n) en général, mais vous permet d'effectuer des recherches en temps constant). Ensuite, vous pouvez énumérer sur le sous-ensemble et vérifier si chaque élément existe dans le surensemble. Toute l'opération devrait prendre en O (n) de la mémoire supplémentaire et O (n).