비교해 두 개의 컬렉션에 대한 평등에 관계 없이 순서는 항목에서 그들을
https://stackoverflow.com/questions/50098
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
을 비교하고 싶 두 가지 모음(C#),하지만 난 모르겠어요 최고의 방법으로 이를 구현하기 위해 효율적으로 합니다.
내가 읽고 다른 스레드에 대 열거.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
비고
두 가지 컬렉션은 해당하는 경우 같은 요소에 동일 수량하지만,어떤 순서입니다.소 같은 경우 해당 값이 동일 하지 않는 경우는 동일한 개체입니다.
사용하는 반사체,나는 수정한 뒤에 코드 AreEquivalent()를 만들 해당하는 평등을 비교자입니다.그것보다 더 완벽한 기존의 답변이 소요되기 때문에 null 을 계정으로 구현하의 문자열 및 효율성 및 사용자 확인합니다.게다가,그것은 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[회원]--.
끝에서,루프를 통해 모든 구성원이 사전에:
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(N),다고 가정하면 사용 O(1)조회.
이것은 내(에 의해 크게 영향을 D.Jennings)일반적인 구현을 비교 방법(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;
}
}
편집:저는 깨달은 곧 내가 제기하는 것이 정말 유일한 작품 세트-그것이 제대로 처리 컬렉션 중복되는 항목입니다.예를 들어{1,1,2}과{2,2,1}것이 동일한 것으로 간주됩에서 이 알고리즘의 관점입니다.는 경우에 당신의 컬렉션은 설정(또는 그들의 평등을 측정할 수 있는 방식),그러나 나는 당신을 희망을 찾을 아래에 유용합니다.
솔루션 내용:
return c1.Count == c2.Count && c1.Intersect(c2).Count() == c1.Count;
Linq 는 사전 일에서,그래서 이것은 또한 O(N).(참고로,그것은 오는 경우(1)컬렉션을지 않는 동일한 크기).
나는 정신을 사용하여 확인"SetEqual"방법을 제안 다니엘,OrderBy/SequenceEquals 방법을 제안에 이고르,그리고 내다.이 결과는 다음과 같다,보여주는 O(N*LogN)에 대한 이고르와 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
의 경우에는 반복이 없기 위해,다음과 같은 EqualityComparer 사용할 수 있습 컬렉션으로 사전에 키:
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;
}
}
기 은 ToHashSet()구현이 나는 사용됩니다.이 해쉬 알고리즘 코드 온에서 효과적인 자바(의 방법으로 존 스키트).
static bool SetsContainSameElements<T>(IEnumerable<T> set1, IEnumerable<T> set2) {
var setXOR = new HashSet<T>(set1);
setXOR.SymmetricExceptWith(set2);
return (setXOR.Count == 0);
}
솔루션이 필요합니다.NET3.5 고 System.Collections.Generic 네임스페이스가 있습니다. 마, SymmetricExceptWith 가 O(n+m) 가동, n 의 수를 나타내는 요소에서 첫 번째로 설정하고 m 의 수를 나타내는 요소에서 두 번째입니다.항상 추가할 수 있습는 평등을 비교하는 경우에는 이 기능을 필요합니다.
왜 사용하고 있습니다.를 제외하고()
// 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);
당신이 사용하는 경우 Shouldly, 사용할 수 있습니다 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
중복된 게시물의 종류,그러 인 솔루션을 비교를 위한 컬렉션.그것은 매우 간단하다:
이것을 수행평등교에 관계없이 주문하기:
var list1 = new[] { "Bill", "Bob", "Sally" };
var list2 = new[] { "Bob", "Bill", "Sally" };
bool isequal = list1.Compare(list2).IsSame;
이지 확인합니다면 항목을 추가/제거:
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
이는 항목이 표시됩 사전에서 변경:
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
원래의 게시물 기.
여기에 내장 방식의 변 ohadsc 의 대답은 경우에,그것은 누군가에게 도움이
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;
}
}
여기에는 솔루션을 통해 개선 이.
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]);
}
많은 해결책이 있습니다.지 않는 경우 관리에 대한 중복을 하지 않을 정렬 할 수 있다.첫째는지 확인들은 같은 수의 항목입니다.후에 그 종류의 하나의 컬렉션이 있습니다.다음 binsearch 각 항목에서 두 번째는 컬렉션에서 정렬된 컬렉션입니다.을 찾지 못한 경우에는 지정된 항목을 중지하고는 false 를 반환합니다.의 복잡성이:-정렬 첫 번째는 컬렉션:N로그(N) -찾 각 항목에서 두 번째로 먼저:N로그(N) 그래서 당신은 결국 2*N*로그(N)가 일치하는지와 당신은 모든 것입니다.이와 유사한 복잡성의 정렬니다.또한 이것은 당신의 혜택을 중지하는 경우 앞에서 차이가 있다.그러나 유지하는 경우 양쪽 정렬되기 전에 당신이 비교도에 의해 정렬이 같은 것을 사용하 qsort,정렬이 더 비싼 것입니다.가 있 최적화합니다.또 다른 대안은 작은 컬렉션을 알고 범위의 요소가 사용하는 비트 마스크의 인덱스입니다.이것은 당신에게 O(n)performance.또 다른 대안은 해시 찾습니다.을 위한 작은 컬렉션 그것은 일반적으로 많이 할 수있는 더 나은 정렬하거나 비트 마스크에 인덱스입니다.Hashtable 불 더 지역이 너무 마음에 보관하십시오.다시는 경우에만 걱정하지 않습니다.하려는 경우 계정에 대한 중복을 가로 정렬니다.
많은 경우에만 적당한 답을 하나의 이고르,제작,다른 답변에 따라 객체로 해시 코드입니다.하지만 생성할 때에는 해시 코드에 대한 개체에 이렇게 할 만반의 변경할 수 없는 필드와 같은 객체 Id 필드(의 경우에 데이터베이스 entity)- 왜 중요한 재정의 GetHashCode 때 같음 방법은 무?
즉,비교하면 두 가지 컬렉션한다면,그 결과는 사실의 비교 방법에도 불구의 분야 다른 항목이 비 동일합니다.깊은 컬렉션을 비교,당신은 당신을 사용할 필요가 이고르의 방법과 구현 IEqualirity.
읽어 보시기 바랍 의견의 미스터.Schnider 의 대부분의 투표 post.
스
허용에서 중복 IEnumerable<T> 면(설정하지 않은 것이 바람직\가능)그리고"무시하기 위해"당신이 할 수 있어야 사용 .GroupBy().
나는 전문가가 아니에 복잡성을 측정,하지만 내 기초적인 이해가는 이야 O(n).내가 이해 O(n^2)에서 오는 것으로 수행하는 O(n)운영 안에 다른 O(n)업 ListA.Where(a => ListB.Contains(a)).ToList().모든 항목에서 ListB 평가에 대한 평등에 대한 각각의 항목에서 ListA.
내가 말했듯이,내가 이해에는 복잡한 제한,그래서 올바른 이 경우 내가 잘못입니다.
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;
}
이 간단한 솔루션 세력 IEnumerable의 일반적인 유형을 구현하는 IComparable.기
OrderBy's definition.
원하지 않는 경우에 이러한 가정을 하지만 여전히 사용하는 이 솔루션을 사용할 수 있습니다,다음 코드:
bool equal = collection1.OrderBy(i => i?.GetHashCode())
.SequenceEqual(collection2.OrderBy(i => i?.GetHashCode()));
