Confronto di due raccolte per l'uguaglianza indipendentemente dall'ordine degli elementi in esse contenuti
https://stackoverflow.com/questions/50098
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Vorrei confrontare due raccolte (in C#), ma non sono sicuro del modo migliore per implementarlo in modo efficiente.
Ho letto l'altro thread su Enumerable.SequenceEqual, ma non è esattamente quello che cerco.
Nel mio caso, due raccolte sarebbero uguali se entrambe contenessero gli stessi elementi (indipendentemente dall'ordine).
Esempio:
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1 == collection2; // true
Quello che faccio di solito è scorrere ogni elemento di una raccolta e vedere se esiste nell'altra raccolta, quindi scorrere ogni elemento dell'altra raccolta e vedere se esiste nella prima raccolta.(Inizio confrontando le lunghezze).
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
Tuttavia, questo non è del tutto corretto e probabilmente non è il modo più efficiente per confrontare due raccolte per verificarne l'uguaglianza.
Un esempio che mi viene in mente sarebbe sbagliato è:
collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}
Il che sarebbe uguale alla mia implementazione.Dovrei semplicemente contare il numero di volte in cui viene trovato ogni elemento e assicurarmi che i conteggi siano uguali in entrambe le raccolte?
Gli esempi sono in una sorta di C# (chiamiamolo pseudo-C#), ma fornisci la tua risposta nella lingua che desideri, non importa.
Nota: Ho usato numeri interi negli esempi per semplicità, ma voglio poter usare anche oggetti di tipo riferimento (non si comportano correttamente come chiavi perché viene confrontato solo il riferimento dell'oggetto, non il contenuto).
Soluzione
Si scopre che Microsoft ha già questo coperto nel suo framework di test: CollectionAssert.AreEquivalent
Osservazioni
Due collezioni sono equivalenti se hanno gli stessi elementi nella stessa quantità, ma in qualsiasi ordine.Gli elementi sono uguali se i loro valori sono uguali, non se si riferiscono allo stesso oggetto.
Utilizzando reflector, ho modificato il codice dietro AreEquivalent() per creare un corrispondente comparatore di uguaglianza.È più completo delle risposte esistenti, poiché tiene conto dei valori nulli, implementa IEqualityComparer e presenta alcuni controlli di efficienza e casi limite.inoltre, lo è 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;
}
}
Utilizzo del campione:
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
Oppure se vuoi semplicemente confrontare direttamente due collezioni:
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
Infine, puoi utilizzare un comparatore di uguaglianza di tua scelta:
var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true
Altri suggerimenti
Una soluzione semplice e abbastanza efficiente è ordinare entrambe le raccolte e quindi confrontarle per verificarne l'uguaglianza:
bool equal = collection1.OrderBy(i => i).SequenceEqual(
collection2.OrderBy(i => i));
Questo algoritmo è O(N*logN), mentre la soluzione sopra è O(N^2).
Se le raccolte hanno determinate proprietà, potresti essere in grado di implementare una soluzione più rapida.Ad esempio, se entrambe le raccolte sono set di hash, non possono contenere duplicati.Inoltre, verificare se un set di hash contiene qualche elemento è molto veloce.In tal caso un algoritmo simile al tuo sarebbe probabilmente più veloce.
Crea un dizionario "dict" e poi per ogni membro nella prima raccolta, esegui dict[member]++;
Quindi, esegui il loop sulla seconda raccolta allo stesso modo, ma per ciascun membro esegui dict[member]--.
Alla fine, esegui il loop su tutti i membri nel dizionario:
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;
}
Modificare:Per quanto ne so, questo è nello stesso ordine dell'algoritmo più efficiente.Questo algoritmo è O(N), presupponendo che il Dizionario utilizzi le ricerche O(1).
Questa è la mia implementazione generica (fortemente influenzata da D.Jennings) del metodo di confronto (in 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;
}
}
Potresti usare a Hashset.Guarda al ImpostaEquali metodo.
MODIFICARE:Mi sono reso conto non appena l'ho proposto che funziona davvero solo per i set: non gestirà correttamente le raccolte che contengono elementi duplicati.Ad esempio, { 1, 1, 2 } e { 2, 2, 1 } saranno considerati uguali dal punto di vista di questo algoritmo.Se le tue raccolte sono insiemi (o la loro uguaglianza può essere misurata in questo modo), tuttavia, spero che troverai utile quanto segue.
La soluzione che utilizzo è:
return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;
Linq fa il dizionario sotto le coperte, quindi anche questo è O(N).(Nota, è O(1) se le raccolte non hanno la stessa dimensione).
Ho eseguito un controllo di integrità utilizzando il metodo "SetEqual" suggerito da Daniel, il metodo OrderBy/SequenceEquals suggerito da Igor e il mio suggerimento.I risultati sono riportati di seguito e mostrano O(N*LogN) per Igor e O(N) per me e Daniel.
Penso che la semplicità del codice Linq intersect lo renda la soluzione preferibile.
__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
Nel caso di nessuna ripetizione e nessun ordine, è possibile utilizzare il seguente EqualityComparer per consentire raccolte come chiavi del dizionario:
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;
}
}
Qui è l'implementazione ToHashSet() che ho usato.IL algoritmo del codice hash viene da Effective Java (tramite 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 soluzione richiede .NET 3.5 e System.Collections.Generic spazio dei nomi. Secondo Microsoft, SymmetricExceptWith è un O(n+m) operazione, con N che rappresenta il numero di elementi nel primo insieme e M che rappresenta il numero di elementi nel secondo.Se necessario, puoi sempre aggiungere un comparatore di uguaglianza a questa funzione.
Perché non utilizzare .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);
Se usi Dovrebbe, puoi utilizzare ShouldAllBe con contiene.
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1.ShouldAllBe(item=>collection2.Contains(item)); // true
E infine, puoi scrivere un'estensione.
public static class ShouldlyIEnumerableExtensions
{
public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
{
list.ShouldAllBe(l => equivalent.Contains(l));
}
}
AGGIORNAMENTO
Esiste un parametro facoltativo su Dovrebbe essere metodo.
collection1.ShouldBe(collection2, ignoreOrder: true); // true
Una sorta di post duplicato, ma dai un'occhiata alla mia soluzione per confrontare le raccolte.È piuttosto semplice:
Ciò eseguirà un confronto di uguaglianza indipendentemente dall'ordine:
var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;
Questo controllerà se gli elementi sono stati aggiunti/rimossi:
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
Questo vedrà quali elementi nel dizionario sono cambiati:
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
Posta originale Qui.
erickson ha quasi ragione:poiché vuoi abbinare i conteggi dei duplicati, vuoi a Borsa.In Java, questo assomiglia a:
(new HashBag(collection1)).equals(new HashBag(collection2))
Sono sicuro che C# abbia un'implementazione Set incorporata.Lo userei per primo;se le prestazioni sono un problema, puoi sempre utilizzare un'implementazione Set diversa, ma utilizzare la stessa interfaccia Set.
Ecco la variante del mio metodo di estensione della risposta di ohadsc, nel caso sia utile a qualcuno
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;
}
}
Ecco una soluzione che rappresenta un miglioramento Questo.
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]);
}
Esistono molte soluzioni a questo problema.Se non ti interessano i duplicati, non devi ordinarli entrambi.Per prima cosa assicurati che abbiano lo stesso numero di articoli.Dopodiché ordina una delle collezioni.Quindi cerca in bin ogni elemento della seconda raccolta nella raccolta ordinata.Se non trovi un determinato elemento fermati e restituisci false.La complessità di questo:- smistamento della prima raccolta:NLog (N) - Ricerca di ogni elemento dal secondo al primo:NLog (N) in modo da finire con 2*n*log (n) supponendo che corrispondano e cerchi tutto.Questo è simile alla complessità dell'ordinamento di entrambi.Inoltre questo ti dà il vantaggio di fermarti prima se c'è una differenza.Tuttavia, tieni presente che se entrambi vengono ordinati prima di iniziare questo confronto e provi a ordinare utilizzando qualcosa come qsort, l'ordinamento sarà più costoso.Ci sono ottimizzazioni per questo.Un'altra alternativa, ottima per piccole raccolte in cui si conosce la gamma degli elementi, è utilizzare un indice maschera di bit.Questo ti darà una prestazione O(n).Un'altra alternativa è utilizzare un hash e cercarlo.Per raccolte di piccole dimensioni di solito è molto meglio eseguire l'ordinamento o l'indice della maschera di bit.Hashtable ha lo svantaggio di una località peggiore, quindi tienilo a mente.Ancora una volta, è solo se non ti interessano i duplicati.Se vuoi tenere conto dei duplicati, procedi con l'ordinamento di entrambi.
In molti casi l'unica risposta adatta è quella di Igor Ostrovsky, altre risposte si basano sul codice hash degli oggetti.Ma quando generi un codice hash per un oggetto, lo fai solo in base ai suoi campi IMMUTABLE - come il campo ID oggetto (in caso di un'entità di database) -Perché è importante sovrascrivere GetHashCode quando il metodo Equals viene sovrascritto?
Ciò significa che se si confrontano due raccolte, il risultato del metodo di confronto potrebbe essere vero anche se i campi dei diversi elementi non sono uguali.Per confrontare in modo approfondito le raccolte, è necessario utilizzare il metodo di Igor e implementare IEqualirity.
Per favore leggi i commenti miei e di Mr.Schnider sul suo post più votato.
Giacomo
Consentire duplicati nel file IEnumerable<T> (se i set non sono desiderabili\possibili) e "ignorando l'ordine" dovresti essere in grado di utilizzare a .GroupBy().
Non sono un esperto nelle misurazioni della complessità, ma la mia comprensione rudimentale è che dovrebbe essere O(n).Capisco che O(n^2) provenga dall'esecuzione di un'operazione O(n) all'interno di un'altra operazione O(n) simile ListA.Where(a => ListB.Contains(a)).ToList().Ogni elemento dell'Elenco B viene valutato in termini di uguaglianza rispetto a ciascun elemento dell'Elenco A.
Come ho detto, la mia comprensione della complessità è limitata, quindi correggimi se sbaglio.
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;
}
Questa semplice soluzione costringe il IEnumerableil tipo generico da implementare IComparable.Per colpa diOrderByla definizione.
Se non vuoi fare un presupposto del genere ma vuoi comunque utilizzare questa soluzione, puoi utilizzare il seguente pezzo di codice:
bool equal = collection1.OrderBy(i => i?.GetHashCode())
.SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));
