Vergleich der beiden Sammlungen für die Gleichstellung unabhängig von der Reihenfolge der Elemente in Ihnen
https://stackoverflow.com/questions/50098
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich möchte vergleichen Sie zwei Sammlungen (in C#), aber ich bin nicht sicher, der beste Weg, um dies zu implementieren, effizient.
Ich habe gelesen, die anderen thread über Enumerable.SequenceEqual, aber es ist nicht genau das, was ich Suche.
In meinem Fall, zwei Sammlungen wäre gleich, wenn Sie beide enthalten die gleichen Artikel (unabhängig von der Reihenfolge).
Beispiel:
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1 == collection2; // true
Was ich normalerweise tun ist, um eine Schleife durch jedes Element einer Sammlung und sehen, ob er vorhanden, in der anderen Sammlung, dann eine Schleife durch jedes Element der anderen Sammlung zu sehen, wenn es vorhanden ist, in der ersten Sammlung.(Ich fange an durch den Vergleich der Längen).
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
Dies ist jedoch nicht ganz richtig, und es ist wahrscheinlich nicht der effizienteste Weg, um zu tun, vergleichen Sie zwei Kollektionen für die Gleichstellung.
Ein Beispiel, das ich denken kann, wäre das auch falsch ist:
collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}
Das wäre gleich meine Umsetzung.Sollte ich einfach zählen, wie oft jedes Einzelteil ist gefunden und stellen Sie sicher, dass die zählt, sind gleich in beiden Sammlungen?
Die Beispiele sind in irgendeiner Art von C# (wir nennen es pseudo-C#), aber geben Sie Ihre Antwort in welcher Sprache auch immer Sie möchten, es nicht egal.
Hinweis: Ich verwendet, ganzen zahlen in den Beispielen für die Einfachheit, aber ich möchte in der Lage sein, um Referenz benutzen-geben Objekte zu (Sie Verhalten sich nicht korrekt als Schlüssel, da nur die Referenz des Objekts verglichen, nicht der Inhalt).
Lösung
Es stellt sich heraus, hat Microsoft bereits dadurch abgedeckt, in seiner testing framework: CollectionAssert.AreEquivalent
Bemerkungen
Zwei Sammlungen sind gleichwertig, wenn Sie die gleichen Elemente in der gleichen Quantität, aber in beliebiger Reihenfolge.Elemente sind gleich, wenn Ihre Werte gleich sind, nicht, wenn Sie auf das gleiche Objekt beziehen.
Mit dem Reflektor, modifizierte ich den code hinter AreEquivalent() zum erstellen eines entsprechenden equality comparer.Es ist mehr komplette als die bisherigen Antworten, da dauert es null-Werte zu berücksichtigen, IEqualityComparer implementiert und hat einige Effizienz-und edge-Fall prüft.plus, es ist 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;
}
}
Ein Beispiel für die Verwendung:
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
Oder wenn Sie nur wollen, um zu vergleichen, zwei Sammlungen direkt:
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
Schließlich können Sie Ihren an equality comparer Ihrer Wahl:
var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true
Andere Tipps
Eine einfache und relativ effiziente Lösung zu Sortieren beide Sammlungen und dann vergleichen Sie Sie für die Gleichstellung:
bool equal = collection1.OrderBy(i => i).SequenceEqual(
collection2.OrderBy(i => i));
Dieser Algorithmus ist O(N*logN), während Ihre Lösung oben ist O(N^2).
Wenn die Sammlungen haben bestimmte Eigenschaften, die Sie möglicherweise in der Lage sein zu implementieren, die eine schnellere Lösung.Für Beispiel, wenn die beiden Ihre Kollektionen sind hash-sets, können Sie keine Duplikate enthalten.Auch die Prüfung, ob ein hash-set enthält ein element ist sehr schnell.In diesem Fall kann ein Algorithmus ähnlich würde dir wahrscheinlich am schnellsten.
Erstellen Sie ein Wörterbuch "dict" - und dann für jedes Element in der ersten Sammlung, tun dict[Mitglied]++;
Dann Schleife über die zweite Sammlung, die in der gleichen Weise, aber für jedes Mitglied tun dict[Mitglied]--.
Am Ende Schleife über alle Mitglieder in der Wörterbuch:
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:Soweit ich sagen kann, dies ist in der gleichen Reihenfolge wie die meisten effizienten Algorithmus.Dieser Algorithmus ist O(N), unter der Annahme, dass das Wörterbuch verwendet O(1) lookups.
Dies ist mein (stark beeinflusst von D. Jennings) generische Implementierung der Vergleich Methode (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;
}
}
EDIT:Ich erkannte, sobald ich schlug vor, dass dies wirklich nur funktioniert für Gruppen-es wird nicht richtig umzugehen mit Sammlungen, die doppelte Elemente.Zum Beispiel ist { 1, 1, 2 } und { 2, 2, 1 } wird als gleich aus diesen Algorithmus Perspektive.Wenn Sie Ihre Sammlungen sind Sätze (oder Ihre Gleichheit gemessen werden kann, die Art und Weise), jedoch, ich hoffe, Sie finden die unten nützlich.
Die Lösung, die ich benutze, ist:
return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;
Linq funktioniert das Wörterbuch Sache unter der Decke, das ist also auch O(N).(Beachten Sie, es ist O(1) wenn Sie die Sammlungen sind nicht die gleiche Größe).
Ich habe eine überprüfung mit dem "SetEqual" - Methode vorgeschlagen, die von Daniel, die OrderBy - /SequenceEquals Methode vorgeschlagen, die von Igor, und mein Vorschlag.Die Ergebnisse unten zeigen, O(N*LogN) für Igor und O(N) bei mir und Daniel.
Ich denke, die Einfachheit der Linq-schneiden-code macht es die bevorzugte Lösung.
__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
In die Fall von keine Wiederholungen und keine Ordnung, die folgenden EqualityComparer können verwendet werden Sammlungen als dictionary-Schlüssel:
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;
}
}
Hier ist die ToHashSet() Implementierung, die ich verwendet.Die hash-code-Algorithmus kommt aus Effektive Java (durch Weg von 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);
}
Lösung erfordert .NET 3.5 und der System.Collections.Generic namespace. Laut Microsoft, SymmetricExceptWith ist ein O(n + m) Betrieb mit n für die Anzahl der Elemente in der ersten gesetzt und m für die Anzahl der Elemente in der zweiten.Sie könnte immer fügen Sie ein equality comparer auf diese Funktion, wenn notwendig.
Warum nicht .Außer der()
// 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);
Wenn Sie Shouldly, Sie können ShouldAllBe mit Enthält.
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1.ShouldAllBe(item=>collection2.Contains(item)); // true
Und schließlich können Sie schreiben für eine Verlängerung.
public static class ShouldlyIEnumerableExtensions
{
public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
{
list.ShouldAllBe(l => equivalent.Contains(l));
}
}
UPDATE
Ein optionaler parameter vorhanden ist ShouldBe Methode.
collection1.ShouldBe(collection2, ignoreOrder: true); // true
Eine doppelte Art posten, aber schauen Sie sich meine Lösung für den Vergleich von Sammlungen.Es ist ziemlich einfach:
Diese führen eine Geschlechter-Vergleich unabhängig von der Reihenfolge:
var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;
Dieser wird überprüfen, um zu sehen, ob Elemente wurden Hinzugefügt / entfernt:
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
Diese werden sehen, welche Elemente im Wörterbuch geändert:
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
Original post hier.
erickson ist fast richtig:da willst du match zählt der Duplikate, die Sie wollen, ein Tasche.In Java, das ungefähr so aussieht:
(new HashBag(collection1)).equals(new HashBag(collection2))
Ich bin sicher, C# hat eine gebaut-in Set-Implementierung.Ich würde das erste;wenn die Leistung ein problem, Sie könnte immer verwenden Sie ein anderes Set-Implementierung, aber die gleichen Schnittstelle.
Hier ist meine Erweiterungsmethode Variante des ohadsc Antwort, in Fall, es ist nützlich für jemanden
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;
}
}
Hier ist eine Lösung, die eine Verbesserung gegenüber diese ein.
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]);
}
Es gibt viele Lösungen zu diesem problem.Wenn Sie kümmern sich nicht um Duplikate, die Sie nicht haben, um zu Sortieren die beiden.Stellen Sie zunächst sicher, dass Sie die gleiche Anzahl von Elementen.Nach, dass die Art eine der Sammlungen.Dann binsearch jedes Element aus der zweiten Sammlung in der Sammlung sortiert.Wenn Sie nicht finden, ein bestimmtes Element zu stoppen und geben Sie false zurück.Die Komplexität:- Sortierung der ersten Sammlung:NLog(N) - suchen Sie jedes Element aus der zweiten in die erste:NLOG(N) so dass man am Ende mit 2*N*LOG(N) unter der Annahme, dass Sie übereinstimmen, und Sie sehen alles.Dies ist ähnlich wie die Komplexität der Sortierung beide.Auch dies gibt Ihnen den Vorteil, zu stoppen früher, wenn es einen Unterschied.Beachten Sie jedoch, dass, wenn die beiden werden sortiert, bevor Sie Schritt in diesem Vergleich und Sie versuchen, Sie zu Sortieren, indem Sie etwas wie eine qsort, die Sortierung wird teurer.Es gibt Optimierungen für diese.Eine weitere alternative, die ist ideal für kleine Sammlungen, wo man weiß, die Auswahl der Elemente ist zu verwenden eine bit-index.Dadurch erhalten Sie eine O(n) Leistung.Eine weitere alternative ist die Verwendung einer hash und nachschlagen.Für kleine Sammlungen in der Regel ist es viel besser, die zum Sortieren oder die Bitmaske index.Hashtable haben den Nachteil schlechter Ort also, keep that in mind.Wieder, das ist nur, wenn Sie kümmern sich nicht um Duplikate.Wenn Sie möchten, zur Konto für Duplikate gehen Sie mit der Sortierung beide.
In vielen Fällen die einzig angemessene Antwort ist der, der von Igor Ostrovsky , andere Antworten basieren auf Objekte hash-code.Aber wenn Sie generiert einen hash-code für ein Objekt, so tun Sie dies nur auf der Grundlage seiner UNVERÄNDERLICHE Felder - wie Objekt-Id-Feld (im Falle eines Datenbank-Entität) - Warum ist es wichtig, GetHashCode überschreiben, wenn die Equals-Methode überschrieben wird?
Dies bedeutet , dass, wenn Sie vergleichen zwei Sammlungen , ist das Ergebnis wahr sein könnte, der compare-Methode, obwohl die Felder der verschiedenen Elemente sind nicht gleich .Deep vergleichen Sie Sammlungen , die Sie benötigen, zu verwenden, Igor Methode und implementieren IEqualirity .
Bitte Lesen Sie sich die Kommentare von mir und Herr.Schnider auf seinen meisten stimmten post.
James
Ermöglicht, die Duplikate in der IEnumerable<T> (wenn die Sätze sind nicht wünschenswert\möglich) und "ignorieren, um" Sie sollten in der Lage sein zu verwenden .GroupBy().
Ich bin kein Experte auf die Komplexität Messungen, aber mein rudimentäres Verständnis ist, dass dies O(n).Ich verstehe, O(n^2), als käme Sie von der Durchführung eine O(n) - operation in einer anderen O(n) operation, wie ListA.Where(a => ListB.Contains(a)).ToList().Jedes Element in ListB ist bewertet für Gleichheit gegen jedes Element in ListA.
Wie gesagt, mein Verständnis auf Komplexität ist begrenzt, so korrigieren Sie mich, wenn ich falsch bin.
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;
}
Diese einfache Lösung Kräfte der IEnumerable's generischen Typ zu implementieren IComparable.Wegen
OrderBy's definition.
Wenn Sie nicht wollen, um eine solche Annahme aber immer noch wollen, verwenden Sie diese Lösung verwenden, können Sie das folgende Stück code :
bool equal = collection1.OrderBy(i => i?.GetHashCode())
.SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));
