Como encontrar itens em um superconjunto que não estão em um subconjunto
Pergunta
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?
Solução
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.
Outras dicas
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.
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.