Comparaison de deux collections pour l'égalité quel que soit l'ordre des éléments qu'elles contiennent
https://stackoverflow.com/questions/50098
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Je voudrais comparer deux collections (en C#), mais je ne suis pas sûr de la meilleure façon de l'implémenter efficacement.
J'ai lu l'autre fil sur Enumerable.SequenceEqual, mais ce n'est pas exactement ce que je recherche.
Dans mon cas, deux collections seraient égales si elles contenaient toutes les deux les mêmes éléments (quel que soit l'ordre).
Exemple:
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1 == collection2; // true
Ce que je fais habituellement, c'est parcourir chaque élément d'une collection et voir s'il existe dans l'autre collection, puis parcourir chaque élément de l'autre collection et voir s'il existe dans la première collection.(Je commence par comparer les longueurs).
if (collection1.Count != collection2.Count)
return false; // the collections are not equal
foreach (Item item in collection1)
{
if (!collection2.Contains(item))
return false; // the collections are not equal
}
foreach (Item item in collection2)
{
if (!collection1.Contains(item))
return false; // the collections are not equal
}
return true; // the collections are equal
Cependant, ce n’est pas tout à fait correct et ce n’est probablement pas le moyen le plus efficace de comparer l’égalité de deux collections.
Un exemple auquel je peux penser et qui serait faux est :
collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}
Ce qui serait égal à ma mise en œuvre.Dois-je simplement compter le nombre de fois où chaque élément est trouvé et m'assurer que les comptes sont égaux dans les deux collections ?
Les exemples sont dans une sorte de C# (appelons-le pseudo-C#), mais donnez votre réponse dans le langage de votre choix, cela n'a pas d'importance.
Note: J'ai utilisé des nombres entiers dans les exemples pour plus de simplicité, mais je souhaite également pouvoir utiliser des objets de type référence (ils ne se comportent pas correctement comme des clés car seule la référence de l'objet est comparée, pas le contenu).
La solution
Il s'avère que Microsoft a déjà couvert cela dans son cadre de test : CollectionAssert.AreEquivalent
Remarques
Deux collections sont équivalentes si elles ont les mêmes éléments en même quantité, mais dans n'importe quel ordre.Les éléments sont égaux si leurs valeurs sont égales, pas s'ils se réfèrent au même objet.
À l'aide de Reflector, j'ai modifié le code derrière AreEquivalent() pour créer un comparateur d'égalité correspondant.Il est plus complet que les réponses existantes, car il prend en compte les valeurs nulles, implémente IEqualityComparer et propose des vérifications d'efficacité et de cas extrêmes.en plus, c'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 souhaitez simplement comparer directement deux collections :
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 le comparateur d'égalité de votre choix :
var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true
Autres conseils
Une solution simple et assez efficace consiste à trier les deux collections, puis à les comparer pour vérifier leur égalité :
bool equal = collection1.OrderBy(i => i).SequenceEqual(
collection2.OrderBy(i => i));
Cet algorithme est O(N*logN), tandis que votre solution ci-dessus est O(N^2).
Si les collections ont certaines propriétés, vous pourrez peut-être implémenter une solution plus rapide.Par exemple, si vos deux collections sont des jeux de hachage, elles ne peuvent pas contenir de doublons.De plus, vérifier si un jeu de hachage contient un élément est très rapide.Dans ce cas, un algorithme similaire au vôtre serait probablement le plus rapide.
Créez un dictionnaire "dict" puis pour chaque membre de la première collection, faites dict[member]++;
Ensuite, parcourez la deuxième collection de la même manière, mais pour chaque membre, faites dict[member]--.
À la fin, parcourez tous les membres du 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;
}
Modifier:Autant que je sache, c'est du même ordre que l'algorithme le plus efficace.Cet algorithme est O(N), en supposant que le dictionnaire utilise des recherches O(1).
Voici mon implémentation générique (fortement influencée par D.Jennings) de la méthode de comparaison (en C#) :
/// <summary>
/// Represents a service used to compare two collections for equality.
/// </summary>
/// <typeparam name="T">The type of the items in the collections.</typeparam>
public class CollectionComparer<T>
{
/// <summary>
/// Compares the content of two collections for equality.
/// </summary>
/// <param name="foo">The first collection.</param>
/// <param name="bar">The second collection.</param>
/// <returns>True if both collections have the same content, false otherwise.</returns>
public bool Execute(ICollection<T> foo, ICollection<T> bar)
{
// Declare a dictionary to count the occurence of the items in the collection
Dictionary<T, int> itemCounts = new Dictionary<T,int>();
// Increase the count for each occurence of the item in the first collection
foreach (T item in foo)
{
if (itemCounts.ContainsKey(item))
{
itemCounts[item]++;
}
else
{
itemCounts[item] = 1;
}
}
// Wrap the keys in a searchable list
List<T> keys = new List<T>(itemCounts.Keys);
// Decrease the count for each occurence of the item in the second collection
foreach (T item in bar)
{
// Try to find a key for the item
// The keys of a dictionary are compared by reference, so we have to
// find the original key that is equivalent to the "item"
// You may want to override ".Equals" to define what it means for
// two "T" objects to be equal
T key = keys.Find(
delegate(T listKey)
{
return listKey.Equals(item);
});
// Check if a key was found
if(key != null)
{
itemCounts[key]--;
}
else
{
// There was no occurence of this item in the first collection, thus the collections are not equal
return false;
}
}
// The count of each item should be 0 if the contents of the collections are equal
foreach (int value in itemCounts.Values)
{
if (value != 0)
{
return false;
}
}
// The collections are equal
return true;
}
}
Vous pourriez utiliser un Ensemble de hachage.Regarde le SetEquals méthode.
MODIFIER:J'ai réalisé dès que j'ai posé que cela ne fonctionnait vraiment que pour les ensembles - cela ne traiterait pas correctement les collections contenant des éléments en double.Par exemple, { 1, 1, 2 } et { 2, 2, 1 } seront considérés comme égaux du point de vue de cet algorithme.Si vos collections sont des ensembles (ou si leur égalité peut être mesurée de cette façon), j'espère que vous trouverez ce qui suit utile.
La solution que j'utilise est la suivante :
return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;
Linq fait le dictionnaire sous les couvertures, donc c'est aussi O(N).(Remarque, c'est O(1) si les collections ne sont pas de la même taille).
J'ai effectué une vérification d'intégrité en utilisant la méthode "SetEqual" suggérée par Daniel, la méthode OrderBy/SequenceEquals suggérée par Igor et ma suggestion.Les résultats sont ci-dessous, montrant O(N*LogN) pour Igor et O(N) pour le mien et celui de Daniel.
Je pense que la simplicité du code d'intersection Linq en fait la solution préférable.
__Test Latency(ms)__
N, SetEquals, OrderBy, Intersect
1024, 0, 0, 0
2048, 0, 0, 0
4096, 31.2468, 0, 0
8192, 62.4936, 0, 0
16384, 156.234, 15.6234, 0
32768, 312.468, 15.6234, 46.8702
65536, 640.5594, 46.8702, 31.2468
131072, 1312.3656, 93.7404, 203.1042
262144, 3765.2394, 187.4808, 187.4808
524288, 5718.1644, 374.9616, 406.2084
1048576, 11420.7054, 734.2998, 718.6764
2097152, 35090.1564, 1515.4698, 1484.223
En l’absence de répétitions et d’ordre, le EqualityComparer suivant peut être utilisé pour autoriser les collections en tant que 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 l'implémentation ToHashSet() que j'ai utilisée.Le algorithme de code de hachage vient de Effective Java (par l'intermédiaire de Jon Skeet).
static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
var setXOR = new HashSet<T>(set1);
setXOR.SymmetricExceptWith(set2);
return (setXOR.Count == 0);
}
La solution nécessite .NET 3.5 et le System.Collections.Generic espace de noms. Selon Microsoft, SymmetricExceptWith est un O(n+m) opération, avec n représentant le nombre d'éléments dans le premier ensemble et m représentant le nombre d'éléments dans la seconde.Vous pouvez toujours ajouter un comparateur d'égalité à cette fonction si nécessaire.
Pourquoi ne pas utiliser .Except()
// Create the IEnumerable data sources.
string[] names1 = System.IO.File.ReadAllLines(@"../../../names1.txt");
string[] names2 = System.IO.File.ReadAllLines(@"../../../names2.txt");
// Create the query. Note that method syntax must be used here.
IEnumerable<string> differenceQuery = names1.Except(names2);
// Execute the query.
Console.WriteLine("The following lines are in names1.txt but not names2.txt");
foreach (string s in differenceQuery)
Console.WriteLine(s);
Si tu utilises Il faudrait, vous pouvez utiliser ShouldAllBe avec Contains.
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 Devrait être méthode.
collection1.ShouldBe(collection2, ignoreOrder: true); // true
Une sorte de message en double, mais découvrez ma solution pour comparer les collections.C'est assez simple :
Cela effectuera 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;
Cela vérifiera si des éléments 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 éléments du dictionnaire ont 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
Message d'origine ici.
Érickson c'est presque vrai :puisque vous souhaitez faire correspondre le nombre de doublons, vous voulez un Sac.En Java, cela ressemble à ceci :
(new HashBag(collection1)).equals(new HashBag(collection2))
Je suis sûr que C# a une implémentation Set intégrée.Je l'utiliserais en premier ;si les performances posent problème, vous pouvez toujours utiliser une implémentation Set différente, mais utiliser la même interface Set.
Voici ma variante de méthode d'extension de la réponse d'ohadsc, au cas où cela serait 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;
}
}
Voici une solution qui est une amélioration par rapport à celui-ci.
public static bool HasSameElementsAs<T>(
this IEnumerable<T> first,
IEnumerable<T> second,
IEqualityComparer<T> comparer = null)
{
var firstMap = first
.GroupBy(x => x, comparer)
.ToDictionary(x => x.Key, x => x.Count(), comparer);
var secondMap = second
.GroupBy(x => x, comparer)
.ToDictionary(x => x.Key, x => x.Count(), comparer);
if (firstMap.Keys.Count != secondMap.Keys.Count)
return false;
if (firstMap.Keys.Any(k1 => !secondMap.ContainsKey(k1)))
return false;
return firstMap.Keys.All(x => firstMap[x] == secondMap[x]);
}
Il existe de nombreuses solutions à ce problème.Si vous ne vous souciez pas des doublons, vous n'êtes pas obligé de trier les deux.Assurez-vous d’abord qu’ils contiennent le même nombre d’éléments.Après cela, triez l'une des collections.Ensuite, recherchez chaque élément de la deuxième collection dans la collection triée.Si vous ne trouvez pas un élément donné, arrêtez et retournez false.La complexité de ceci :- trier la première collection :NLog (n) - Recherche de chaque élément du deuxième dans le premier:NLog (n) Vous vous retrouvez donc avec 2 * n * journal (n) en supposant qu'ils correspondent et que vous recherchez tout.Ceci est similaire à la complexité du tri des deux.Cela vous donne également l'avantage de vous arrêter plus tôt s'il y a une différence.Cependant, gardez à l’esprit que si les deux sont triés avant de vous lancer dans cette comparaison et que vous essayez de trier en utilisant quelque chose comme un qsort, le tri sera plus coûteux.Il existe des optimisations pour cela.Une autre alternative, idéale pour les petites collections où vous connaissez la gamme des éléments, consiste à utiliser un index de masque de bits.Cela vous donnera une performance O(n).Une autre alternative consiste à utiliser un hachage et à le rechercher.Pour les petites collections, il est généralement préférable d'effectuer le tri ou l'index du masque de bits.Hashtable a l'inconvénient d'une localité pire, alors gardez cela à l'esprit.Encore une fois, c'est seulement si vous ne vous souciez pas des doublons.Si vous souhaitez prendre en compte les doublons, triez les deux.
Dans de nombreux cas, la seule réponse appropriée est celle d'Igor Ostrovsky, d'autres réponses sont basées sur le hash code des objets.Mais lorsque vous générez un code de hachage pour un objet, vous le faites uniquement en fonction de ses champs IMMUTABLES - tels que le champ ID d'objet (dans le cas d'une entité de base de données) -Pourquoi est-il important de remplacer GetHashCode lorsque la méthode Equals est remplacée ?
Cela signifie que si vous comparez deux collections, le résultat peut être vrai pour la méthode de comparaison même si les champs des différents éléments ne sont pas égaux.Pour comparer en profondeur les collections , vous devez utiliser la méthode d'Igor et implémenter IEqualirity .
Veuillez lire les commentaires de moi et de M. Schnider sur son message le plus voté.
James
Autoriser les doublons dans le IEnumerable<T> (si les ensembles ne sont pas souhaitables\possibles) et "en ignorant l'ordre", vous devriez pouvoir utiliser un .GroupBy().
Je ne suis pas un expert en mesures de complexité, mais ma compréhension rudimentaire est que cela devrait être O(n).Je comprends O(n^2) comme venant de l'exécution d'une opération O(n) dans une autre opération O(n) comme ListA.Where(a => ListB.Contains(a)).ToList().Chaque élément de ListB est évalué pour son égalité par rapport à chaque élément de ListA.
Comme je l'ai dit, ma compréhension de la complexité est limitée, alors 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;
}
Cette solution simple force le IEnumerableLe type générique de à implémenter IComparable.À cause deOrderByLa définition de.
Si vous ne souhaitez pas faire une telle hypothèse mais souhaitez tout de même utiliser cette solution, vous pouvez utiliser le morceau de code suivant :
bool equal = collection1.OrderBy(i => i?.GetHashCode())
.SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));
