La comparaison de deux collections pour l'égalité indépendamment de l'ordre des éléments dans leur

Il s'avère que Microsoft a déjà couverte, dans son cadre d'essais: CollectionAssert.AreEquivalent

Remarques

Deux collections sont équivalentes si elles
les mêmes éléments dans les mêmes
la quantité, mais dans n'importe quel ordre. Éléments
sont égales si leurs valeurs sont égales,
pas si ils font référence au même objet.

L'aide d'un réflecteur, j'ai modifié le code derrière AreEquivalent() pour créer un correspondant comparateur d'égalité. Il est plus complet que les réponses existantes, car elle prend les valeurs null en compte, met en œuvre IEqualityComparer et a une certaine efficacité et le bord en cas vérifie. de plus, il est Microsoft 🙂

public class MultiSetComparer<T> : IEqualityComparer<IEnumerable<T>>
{
private readonly IEqualityComparer<T> m_comparer;
public MultiSetComparer(IEqualityComparer<T> comparer = null)
{
m_comparer = comparer ?? EqualityComparer<T>.Default;
}
public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
{
if (first == null)
return second == null;
if (second == null)
return false;
if (ReferenceEquals(first, second))
return true;
if (first is ICollection<T> firstCollection && second is ICollection<T> secondCollection)
{
if (firstCollection.Count != secondCollection.Count)
return false;
if (firstCollection.Count == 0)
return true;
}
return !HaveMismatchedElement(first, second);
}
private bool HaveMismatchedElement(IEnumerable<T> first, IEnumerable<T> second)
{
int firstNullCount;
int secondNullCount;
var firstElementCounts = GetElementCounts(first, out firstNullCount);
var secondElementCounts = GetElementCounts(second, out secondNullCount);
if (firstNullCount != secondNullCount || firstElementCounts.Count != secondElementCounts.Count)
return true;
foreach (var kvp in firstElementCounts)
{
var firstElementCount = kvp.Value;
int secondElementCount;
secondElementCounts.TryGetValue(kvp.Key, out secondElementCount);
if (firstElementCount != secondElementCount)
return true;
}
return false;
}
private Dictionary<T, int> GetElementCounts(IEnumerable<T> enumerable, out int nullCount)
{
var dictionary = new Dictionary<T, int>(m_comparer);
nullCount = 0;
foreach (T element in enumerable)
{
if (element == null)
{
nullCount++;
}
else
{
int num;
dictionary.TryGetValue(element, out num);
num++;
dictionary[element] = num;
}
}
return dictionary;
}
public int GetHashCode(IEnumerable<T> enumerable)
{
if (enumerable == null) throw new ArgumentNullException(nameof(enumerable));
int hash = 17;
foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + (val?.GetHashCode() ?? 42);
return hash;
}
}

Exemple d'utilisation:

var set = new HashSet<IEnumerable<int>>(new[] {new[]{1,2,3}}, new MultiSetComparer<int>());
Console.WriteLine(set.Contains(new [] {3,2,1})); //true
Console.WriteLine(set.Contains(new [] {1, 2, 3, 3})); //false

Ou si vous voulez juste pour comparer deux collections directement:

var comp = new MultiSetComparer<string>();
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","c","b"})); //true
Console.WriteLine(comp.Equals(new[] {"a","b","c"}, new[] {"a","b"})); //false

Enfin, vous pouvez utiliser un comparateur d'égalité de votre choix:

var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true

Créer un Dictionnaire "dict" et ensuite, pour chaque membre de la première collection, ne dict[membre]++;

Puis, en boucle au cours de la deuxième collection de la même manière, mais pour chaque membre de la dict[membre]--.

À la fin, en boucle sur tous les membres dans le dictionnaire:

    private bool SetEqual (List<int> left, List<int> right) {
if (left.Count != right.Count)
return false;
Dictionary<int, int> dict = new Dictionary<int, int>();
foreach (int member in left) {
if (dict.ContainsKey(member) == false)
dict[member] = 1;
else
dict[member]++;
}
foreach (int member in right) {
if (dict.ContainsKey(member) == false)
return false;
else
dict[member]--;
}
foreach (KeyValuePair<int, int> kvp in dict) {
if (kvp.Value != 0)
return false;
}
return true;
}

Edit: aussi loin Que je peux dire c'est du même ordre que le plus efficace algorithme. Cet algorithme est O(N), en supposant que le Dictionnaire utilise O(1) les recherches.

Vous pouvez utiliser un Hashset. Regardez les SetEquals méthode.

Dans le cas d'absence de répétitions et aucun ordre, les suivantes EqualityComparer peut être utilisé pour permettre à des collections comme les clés de dictionnaire:

public class SetComparer<T> : IEqualityComparer<IEnumerable<T>> 
where T:IComparable<T>
{
public bool Equals(IEnumerable<T> first, IEnumerable<T> second)
{
if (first == second)
return true;
if ((first == null) || (second == null))
return false;
return first.ToHashSet().SetEquals(second);
}
public int GetHashCode(IEnumerable<T> enumerable)
{
int hash = 17;
foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + val.GetHashCode();
return hash;
}
}

Ici est le ToHashSet() de la mise en œuvre que j'ai utilisé. Le algorithme de code de hachage vient d'être Efficace Java (par voie de Jon Skeet).

Si vous utilisez Shouldly, vous pouvez utiliser ShouldAllBe avec Contient.

collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1.ShouldAllBe(item=>collection2.Contains(item)); //true

Et enfin, vous pouvez écrire une extension.

public static class ShouldlyIEnumerableExtensions
{
public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
{
list.ShouldAllBe(l => equivalent.Contains(l));
}
}

Mise à JOUR

Un paramètre facultatif existe sur ShouldBe méthode.

collection1.ShouldBe(collection2, ignoreOrder: true); //true

Un double poste de sortes, mais découvrez ma solution pour comparer des collections. C'est assez simple:

Cela permettra d'effectuer une comparaison d'égalité quel que soit l'ordre:

var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;

Il s'agira de vérifier pour voir si les articles ont été ajoutés /supprimés:

var list1 = new[] { "Billy", "Bob" };
var list2 = new[] { "Bob", "Sally" };
var diff = list1.Compare(list2);
var onlyinlist1 = diff.Removed; //Billy
var onlyinlist2 = diff.Added;   //Sally
var inbothlists = diff.Equal;   //Bob

Cela permettra de voir quels sont les articles dans le dictionnaire changé:

var original = new Dictionary<int, string>() { { 1, "a" }, { 2, "b" } };
var changed = new Dictionary<int, string>() { { 1, "aaa" }, { 2, "b" } };
var diff = original.Compare(changed, (x, y) => x.Value == y.Value, (x, y) => x.Value == y.Value);
foreach (var item in diff.Different)
Console.Write("{0} changed to {1}", item.Key.Value, item.Value.Value);
//Will output: a changed to aaa

Post Original ici.

Voici ma méthode d'extension variante de ohadsc réponse, dans le cas où c'est utile à quelqu'un

static public class EnumerableExtensions 
{
static public bool IsEquivalentTo<T>(this IEnumerable<T> first, IEnumerable<T> second)
{
if ((first == null) != (second == null))
return false;
if (!object.ReferenceEquals(first, second) && (first != null))
{
if (first.Count() != second.Count())
return false;
if ((first.Count() != 0) && HaveMismatchedElement<T>(first, second))
return false;
}
return true;
}
private static bool HaveMismatchedElement<T>(IEnumerable<T> first, IEnumerable<T> second)
{
int firstCount;
int secondCount;
var firstElementCounts = GetElementCounts<T>(first, out firstCount);
var secondElementCounts = GetElementCounts<T>(second, out secondCount);
if (firstCount != secondCount)
return true;
foreach (var kvp in firstElementCounts)
{
firstCount = kvp.Value;
secondElementCounts.TryGetValue(kvp.Key, out secondCount);
if (firstCount != secondCount)
return true;
}
return false;
}
private static Dictionary<T, int> GetElementCounts<T>(IEnumerable<T> enumerable, out int nullCount)
{
var dictionary = new Dictionary<T, int>();
nullCount = 0;
foreach (T element in enumerable)
{
if (element == null)
{
nullCount++;
}
else
{
int num;
dictionary.TryGetValue(element, out num);
num++;
dictionary[element] = num;
}
}
return dictionary;
}
static private int GetHashCode<T>(IEnumerable<T> enumerable)
{
int hash = 17;
foreach (T val in enumerable.OrderBy(x => x))
hash = hash * 23 + val.GetHashCode();
return hash;
}
}

Il y a beaucoup de solutions à ce problème.
Si vous ne vous souciez pas des doublons, vous n'avez pas à trier à la fois. Assurez-vous d'abord qu'ils ont le même nombre d'éléments. Après que sorte l'une de ces collections. Puis binsearch chaque élément de la deuxième collection dans la collection triée. Si vous ne trouvez pas un élément donné d'arrêt et de renvoyer false.
La complexité de cette:
- tri de la première collection: NLog(N)
- la recherche de chaque élément de la deuxième à la première: NLOG(N)
si vous vous retrouvez avec 2*N*LOG(N) en supposant qu'elles correspondent et que vous regardez tout. Ceci est similaire à la complexité du tri à la fois. Aussi cela vous donne l'avantage à arrêter plus tôt si il y a une différence.
Cependant, gardez à l'esprit que si les deux sont triés avant d'étape dans cette comparaison et vous essayez de tri par utiliser quelque chose comme un qsort, le tri sera plus cher. Il y a des optimisations pour cela.
Une autre alternative, ce qui est idéal pour les petites collections où vous savez que la gamme des éléments est d'utiliser un masque de bits d'index. Cela vous donnera un O(n) de la performance.
Une autre alternative est d'utiliser une table de hachage et de le regarder. Pour les petites collections, il est généralement beaucoup mieux de faire le tri ou le masque de bits d'index. Table de hachage ont l'inconvénient de pire localité donc, gardez cela à l'esprit.
De nouveau, c'est que si vous ne vous souciez pas des doublons. Si vous voulez en compte les doublons aller avec tri à la fois.

Permettant de doublons dans les IEnumerable<T> (si les jeux ne sont pas souhaitables\possibles) et "ignorant la commande", vous devriez être en mesure d'utiliser un .GroupBy().

Je ne suis pas un expert sur la complexité des mesures, mais ma compréhension rudimentaire, c'est que ce doit être en O(n). Je comprends O(n^2) comme provenant de l'exécution d'une O(n) fonctionnement à l'intérieur d'un autre O(n) comme ListA.Where(a => ListB.Contains(a)).ToList(). Chaque élément de ListB est évalué pour l'égalité contre chaque élément de ListA.

Comme je l'ai dit, ma compréhension de la complexité est limitée, donc corrigez-moi si je me trompe.

public static bool IsSameAs<T, TKey>(this IEnumerable<T> source, IEnumerable<T> target, Expression<Func<T, TKey>> keySelectorExpression)
{
//check the object
if (source == null && target == null) return true;
if (source == null || target == null) return false;
var sourceList = source.ToList();
var targetList = target.ToList();
//check the list count :: { 1,1,1 } != { 1,1,1,1 }
if (sourceList.Count != targetList.Count) return false;
var keySelector = keySelectorExpression.Compile();
var groupedSourceList = sourceList.GroupBy(keySelector).ToList();
var groupedTargetList = targetList.GroupBy(keySelector).ToList();
//check that the number of grouptings match :: { 1,1,2,3,4 } != { 1,1,2,3,4,5 }
var groupCountIsSame = groupedSourceList.Count == groupedTargetList.Count;
if (!groupCountIsSame) return false;
//check that the count of each group in source has the same count in target :: for values { 1,1,2,3,4 } & { 1,1,1,2,3,4 }
//key:count
//{ 1:2, 2:1, 3:1, 4:1 } != { 1:3, 2:1, 3:1, 4:1 }
var countsMissmatch = groupedSourceList.Any(sourceGroup =>
{
var targetGroup = groupedTargetList.Single(y => y.Key.Equals(sourceGroup.Key));
return sourceGroup.Count() != targetGroup.Count();
});
return !countsMissmatch;
}