Como encontrar itens em um superconjunto que não estão em um subconjunto

Question

Eu sei que há um "não" em Ienumerable, graças ao Linq, que leva uma coleção a não, mas estou preocupado com o Big Oh Performance Qual é o algoritmo mais rápido para fazer isso?

Answer 1

A única maneira de remover um subconjunto de itens de um IEnumerable<T> é para percorrer o Superset e para cada item no loop de superset através do subconjunto, removendo esse item do Superset, se for encontrado no subconjunto.

Isso vai te dar O (N²) na média.

Agora, se houver informações adicionais sobre essas coleções (talvez uma ou ambas seja uma lista ou talvez uma ou ambas as seqüências sejam classificadas) que possam ajudá -lo a criar uma solução mais com desempenho.

Se você estiver interessado, aqui está um método de extensão que fará o que acabei de descrever:

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;
}

---

Esqueça, use o Enumerable.Except Método de extensão:

Produz a diferença definida de duas seqüências.

Answer 2

Se você pode iterar sobre os conjuntos em ordem, poderá garantir o comportamento de O (n) (em vez do "tipicamente O (n), mas possivelmente O (n²) no pior caso" que um hashset tem), iterando através de ambos em ambos em Lockstep.

Por exemplo:

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

Você precisará adicionar a verificação de limites e outras placas de caldeira.

Answer 3

Você pode obter um melhor desempenho convertendo o superconjunto em um hashtable (O (n) normalmente, mas permite que você execute pesquisas em tempo constante). Em seguida, você pode enumerar sobre o subconjunto e verificar se existe cada item no Superset. Toda a operação deve levar a (n) memória extra e o (n) tempo.