Le moyen le plus rapide de savoir si deux ICollection < > les collections contiennent les mêmes objets

StackOverflow https://stackoverflow.com/questions/308476

Question

Quel est le moyen le plus rapide de savoir si deux collections ICollection < T > contiennent exactement les mêmes entrées? La force brute est claire, je me demandais s’il existait une méthode plus élégante.

Nous utilisons C # 2.0, donc pas de méthodes d'extension si possible, s'il vous plaît!

Modifier: la réponse serait intéressante à la fois pour les collections ordonnées et non ordonnées et, espérons-le, différente pour chaque collection.

Était-ce utile?

La solution

utilisez C5

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

ContainsAll

  

" Vérifiez si tous les éléments d'un   la collection fournie est dans ce sac
  (en comptant les multiplicités).
     le   éléments à rechercher.
  
  Vrai si tous les objets sont   trouvé. "

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

Autres conseils

Commencez par comparer le nombre des collections, si elles ont le même nombre, comparez la force brute à tous les éléments. Le pire scénario est O (n). C'est dans le cas où l'ordre des éléments doit être le même.

Dans le deuxième cas où l'ordre n'est pas identique, vous devez utiliser un dictionnaire pour stocker le nombre d'éléments trouvés dans les collections: voici un algorithme possible

  • Comparez le nombre de collections: renvoyez false si elles sont différentes
  • Itérer la première collection
    • Si l'élément n'existe pas dans le dictionnaire, ajoutez-le et saisissez-le avec Key = Item, Value = 1 (le nombre)
    • S'il existe un élément, incrémentez le nombre d'éléments dans le dictionnaire;
  • Itérer la deuxième collection
    • Si l'élément ne figure pas dans le dictionnaire, retournez false
    • Si l'élément est dans le dictionnaire, le nombre de décrémentations de l'élément
      • Si compte == 0 l'élément supprimé;
  • retourner Dictionary.Count == 0;

Pour les collections ordonnées, vous pouvez utiliser la méthode d'extension SequenceEqual () définie par System.Linq.Enumerable : 

if (firstCollection.SequenceEqual(secondCollection))

Vous voulez dire les mêmes entrées ou les mêmes entrées dans le même ordre?

Quoi qu'il en soit, si vous souhaitez comparer si elles contiennent les mêmes entrées dans le même ordre, "force brute". est vraiment votre seule option en C # 2.0. Je sais ce que vous entendez par non élégant, mais si la comparaison atomique elle-même est O (1), tout le processus devrait être en O (N), ce qui n’est <<>> pas mauvais.

Si les entrées doivent être dans le même ordre (en plus d'être identiques), alors je vous suggère, en guise d'optimisation, de répéter les deux collections en même temps et de comparer l'entrée actuelle dans chaque collection. Sinon, la force brutale est la voie à suivre.

Oh, et une autre suggestion - vous pouvez remplacer Equals pour la classe de collection et implémenter les éléments d’égalité qui y sont définis (cela dépend de votre projet, cependant).

Encore une fois, en utilisant la bibliothèque C5 et en ayant deux jeux, vous pouvez utiliser: 

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

La bibliothèque C5 inclut une heuristique qui teste d’abord les codes de hachage non séquencés des deux ensembles (voir C5.ICollection < T > .GetUnquencedHashCode () ), de sorte que les codes de hachage des deux les ensembles sont inégaux, il n’est pas nécessaire de parcourir chaque élément pour vérifier l’égalité.

Vous devez également noter que C5.ICollection < T > hérite de System.Collections.Generic.ICollection < T > , de sorte que vous pouvez utiliser les implémentations C5. tout en utilisant les interfaces .NET (bien que vous ayez accès à moins de fonctionnalités via les interfaces stingy de .NET).

La force brute prend O (n) - en comparant tous les éléments (en supposant qu’ils soient triés), ce qui, à mon avis, est ce que vous pouvez faire de mieux - à moins que certaines données ne facilitent les choses.

Je suppose que pour le cas de non trié, c’est O (n * n).

Dans ce cas, je pense qu'une solution basée sur un tri par fusion serait probablement utile. .

Par exemple, pourriez-vous le modéliser de sorte qu’il n’y ait qu’une collection? Ou 3 collections, une pour ceux de la collection A seulement, une pour B seulement et pour les deux. Donc, si A seul et B seulement sont vides, ils sont identiques, je suis probablement sur la mauvaise tangente. ici ...

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top