Il modo più veloce per scoprire se due ICollection < T > le raccolte contengono gli stessi oggetti

Question

Qual è il modo più veloce per scoprire se due raccolte ICollection < T > contengono esattamente le stesse voci? La forza bruta è chiara, mi chiedevo se esiste un metodo più elegante.

Stiamo usando C # 2.0, quindi nessun metodo di estensione, se possibile, per favore!

Modifica: la risposta sarebbe interessante sia per le collezioni ordinate che per quelle non ordinate e, si spera, sarebbe diversa per ciascuna.

Answer 1

usa C5

http://www.itu.dk/research/c5/

ContainsAll

  

" Controlla se tutti gli articoli in a   la raccolta fornita è in questa borsa
  (contando le molteplicità).
     Il   articoli da cercare.
  
  Vero se tutti gli articoli lo sono   trovato ".

[Tested]

public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T
{
  HashBag<T> res = new HashBag<T>(itemequalityComparer);

  foreach (T item in items)
    if (res.ContainsCount(item) < ContainsCount(item))
      res.Add(item);
    else
      return false;

  return true;
}

Answer 2

Prima confronta il. Conteggio delle raccolte se hanno lo stesso conteggio per fare un confronto di forza bruta su tutti gli elementi. Gli scenari peggiori sono O (n). Questo è nel caso in cui l'ordine degli elementi debba essere lo stesso.

Nel secondo caso in cui l'ordine non è lo stesso, è necessario utilizzare un dizionario per memorizzare il conteggio degli elementi trovati nelle raccolte: ecco un possibile algoritmo

• Confronta conteggio raccolte: restituisce false se sono diverse
• Iterate la prima raccolta
  • Se l'elemento non esiste nel dizionario, aggiungere e inserire con Key = Item, Value = 1 (il conteggio)
  • Se l'elemento esiste, incrementa il conteggio dell'oggetto nel dizionario;
• Iterate la seconda raccolta
  • Se l'elemento non è nel dizionario, restituisce false
  • Se l'elemento è nel conteggio del decremento del dizionario per l'elemento
    • Se count == 0 l'elemento rimuovi;
• return Dictionary.Count == 0;

Answer 3

Per le raccolte ordinate, è possibile utilizzare il metodo di estensione SequenceEqual () definito da System.Linq.Enumerable :

if (firstCollection.SequenceEqual(secondCollection))

Answer 4

Intendi le stesse voci o le stesse voci nello stesso ordine?

Ad ogni modo, supponendo che tu voglia confrontare se contengono le stesse voci nello stesso ordine, "forza bruta". è davvero l'unica opzione in C # 2.0. So cosa intendi per non elegante, ma se la comparazione atomica stessa è O (1), l'intero processo dovrebbe essere in O (N), che non è così cattivo.

Answer 5

Se le voci devono essere nello stesso ordine (oltre a essere lo stesso), allora suggerisco - come ottimizzazione - di iterare entrambe le raccolte contemporaneamente e confrontare la voce corrente in ciascuna raccolta. Altrimenti, la forza bruta è la strada da percorrere.

Oh, e un altro suggerimento: potresti scavalcare Equals per la classe collection e implementare le cose sull'uguaglianza (dipende dal tuo progetto, però).

Answer 6

Anche in questo caso, utilizzando la libreria C5, con due set, è possibile utilizzare:

C5.ICollection<T> set1 = C5.ICollection<T> ();
C5.ICollection<T> set2 = C5.ICollecton<T> ();
if (set1.UnsequencedEquals (set2)) {
  // Do something
}

La libreria C5 include un'euristica che verifica prima i codici hash non sequenziali dei due set (vedi C5.ICollection < T > .GetUnsequencedHashCode () ) in modo che se i codici hash dei due gli insiemi sono disuguali, non è necessario scorrere su ogni elemento per verificare l'uguaglianza.

Un altro aspetto degno di nota è che C5.ICollection < T > eredita da System.Collections.Generic.ICollection < T > , quindi puoi utilizzare le implementazioni C5 mentre usi ancora le interfacce .NET (sebbene tu abbia accesso a meno funzionalità attraverso le interfacce avari di .NET).

Answer 7

La forza bruta prende O (n) - confrontando tutti gli elementi (supponendo che siano ordinati), che riterrei sia il migliore che potresti fare - a meno che non ci siano alcune proprietà dei dati che lo rendono più facile.

Immagino per il caso di non ordinato, la sua O (n * n).

Nel qual caso, penso che una soluzione basata su un unisci ordinamento probabilmente aiuterebbe .

Ad esempio, potresti rimodellarlo in modo che esistesse una sola raccolta? Oppure 3 raccolte, una per quelle della sola raccolta A, una solo per la B e per entrambe - quindi se solo la A e la B sono vuote - allora sono uguali ... Probabilmente sto andando su una tangente totalmente sbagliata qui ...