C #에서 두 컬렉션을 비교하고 싶지만 이것을 효율적으로 구현하는 가장 좋은 방법은 확실하지 않습니다.
Enumerable.SequenceEqual 에 대한 다른 스레드를 읽었 지만 정확히 내가 원하는 것은 아닙니다.
필자의 경우 두 컬렉션 모두 (주문에 관계없이) 동일한 항목을 포함하면 동일합니다.
예:
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1 == collection2; // true내가 일반적으로하는 일은 한 컬렉션의 각 항목을 반복하여 다른 컬렉션에 있는지 확인한 다음 다른 컬렉션의 각 항목을 반복하여 첫 번째 컬렉션에 있는지 확인하는 것입니다. (길이를 비교하여 시작합니다).
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그러나 이것은 완전히 올바른 것은 아니며 두 컬렉션을 동등하게 비교하는 가장 효율적인 방법은 아닐 것입니다.
내가 잘못 생각할 수있는 예는 다음과 같습니다.
collection1 = {1, 2, 3, 3, 4}
collection2 = {1, 2, 2, 3, 4}내 구현과 동일합니다. 각 항목을 찾은 횟수를 세고 두 컬렉션의 개수가 같은지 확인해야합니까?
예제는 일종의 C # (의사 C #이라고 함)에 있지만 원하는 언어로 대답하면 중요하지 않습니다.
참고 : 예제에서 정수를 단순화하기 위해 사용했지만 참조 유형 객체도 사용할 수 있기를 원합니다 (내용이 아닌 객체의 참조 만 비교되기 때문에 키로 올바르게 작동하지 않습니다).
답변
Microsoft는 이미 테스트 프레임 워크에서 CollectionAssert를 다룬 것으로 나타났습니다.
비고
두 컬렉션은 같은 수량에 동일한 순서로 요소가 있으면 동일합니다. 동일한 객체를 참조하는 경우가 아니라 값이 동일한 경우 요소가 동일합니다.
리플렉터를 사용하여 AreEquivalent () 뒤의 코드를 수정하여 해당하는 동등 비교기를 만듭니다. null을 고려하고 IEqualityComparer를 구현하며 일부 효율성과 엣지 사례 검사가 있기 때문에 기존 답변보다 더 완벽합니다. 게다가, 그것은 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;
}
}샘플 사용법 :
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또는 두 컬렉션을 직접 비교하려는 경우 :
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마지막으로 선택한 평등 비교기를 사용할 수 있습니다.
var strcomp = new MultiSetComparer<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(strcomp.Equals(new[] {"a", "b"}, new []{"B", "A"})); //true답변
간단하고 매우 효율적인 솔루션은 두 컬렉션을 정렬 한 다음 동일한 지 비교하는 것입니다.
bool equal = collection1.OrderBy(i => i).SequenceEqual(
collection2.OrderBy(i => i));이 알고리즘은 O (N * logN)이며 위의 솔루션은 O (N ^ 2)입니다.
컬렉션에 특정 속성이있는 경우 더 빠른 솔루션을 구현할 수 있습니다. 예를 들어 두 컬렉션이 모두 해시 세트 인 경우 복제본을 포함 할 수 없습니다. 또한 해시 세트에 일부 요소가 포함되어 있는지 확인하는 것이 매우 빠릅니다. 이 경우 귀하와 유사한 알고리즘이 가장 빠를 것입니다.
답변
사전 “dict”을 만든 다음 첫 번째 컬렉션의 각 멤버에 대해 dict [member] ++;
그런 다음 동일한 방식으로 두 번째 컬렉션을 반복하지만 각 멤버에 대해 dict [member]-를 수행하십시오.
마지막으로 사전의 모든 멤버를 반복하십시오.
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;
}편집 : 내가 알 수있는 한 가장 효율적인 알고리즘과 동일한 순서입니다. 이 알고리즘은 사전이 O (1) 조회를 사용한다고 가정 할 때 O (N)입니다.
답변
이것은 비교 방법 (C #에서)의 일반적인 구현입니다 (D.Jennings의 영향을 크게 받음).
/// <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;
}
}답변
Hashset을 사용할 수 있습니다 . 상기 봐 SetEquals의 방법.
답변
shouldly 를 사용하는 경우 ContainsAll과 함께 ShouldAllBe를 사용할 수 있습니다.
collection1 = {1, 2, 3, 4};
collection2 = {2, 4, 1, 3};
collection1.ShouldAllBe(item=>collection2.Contains(item)); // true마지막으로 확장을 작성할 수 있습니다.
public static class ShouldlyIEnumerableExtensions
{
public static void ShouldEquivalentTo<T>(this IEnumerable<T> list, IEnumerable<T> equivalent)
{
list.ShouldAllBe(l => equivalent.Contains(l));
}
}최신 정보
ShouldBe 메서드 에는 선택적 매개 변수가 있습니다 .
collection1.ShouldBe(collection2, ignoreOrder: true); // true답변
편집 : 나는 이것이 실제로 세트에서만 작동한다는 것을 알 자마자 깨달았습니다. 중복 항목이있는 컬렉션을 올바르게 처리하지 못할 것입니다. 예를 들어 {1, 1, 2} 및 {2, 2, 1}은이 알고리즘의 관점에서 동일한 것으로 간주됩니다. 그러나 컬렉션이 세트 (또는 그 평등을 그렇게 측정 할 수있는 경우) 인 경우 아래 내용이 유용하기를 바랍니다.
내가 사용하는 솔루션은 다음과 같습니다.
return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;Linq는 표지 아래 사전을 수행하므로 O (N)이기도합니다. (컬렉션이 같은 크기가 아닌 경우 O (1)입니다).
Daniel이 제안한 “SetEqual”메소드, Igor가 제안한 OrderBy / SequenceEquals 메소드 및 제안을 사용하여 상태 점검을 수행했습니다. 결과는 다음과 같습니다. Igor의 경우 O (N * LogN), 광산 및 Daniel의 경우 O (N)입니다.
Linq 교차 코드의 단순성이 선호되는 솔루션이라고 생각합니다.
__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