두 개의 icollection 컬렉션이 동일한 개체를 포함하는지 여부를 찾는 가장 빠른 방법
-
08-07-2019 - |
문제
두 가지를 찾는 가장 빠른 방법은 무엇입니까 ICollection<T>
컬렉션에는 정확히 동일한 항목이 포함되어 있습니까? 무자비한 힘이 분명합니다. 더 우아한 방법이 있는지 궁금합니다.
우리는 c# 2.0을 사용하고 있으므로 가능한 경우 확장 방법이 없습니다.
편집 : 대답은 질서와 정렬되지 않은 컬렉션 모두에 흥미로울 것이며, 각각에 따라 다를 것입니다.
해결책
C5를 사용하십시오
http://www.itu.dk/research/c5/
"제공된 컬렉션의 모든 품목 이이 가방에 있는지 확인하십시오.
(다중성 계산).
찾을 항목.
모든 항목이 발견되면 사실입니다. "
[Tested]
public virtual bool ContainsAll<U>(SCG.IEnumerable<U> items) where U : T
{
HashBag<T> res = new HashBag<T>(itemequalityComparer);
foreach (T item in items)
if (res.ContainsCount(item) < ContainsCount(item))
res.Add(item);
else
return false;
return true;
}
다른 팁
먼저 비교하십시오.세다 컬렉션이 동일한 수를 가진 경우 모든 요소에서 무차별 인력 비교를합니다. 최악의 시나리오는 O (n)입니다. 이것은 요소 순서가 동일 해야하는 경우입니다.
순서가 동일하지 않은 두 번째 사례는 사전을 사용하여 컬렉션에있는 요소 수를 저장해야합니다. 다음은 가능한 알고리즘이 있습니다.
- 수집 수를 비교 : 다른 경우 False를 반환합니다.
- 첫 번째 컬렉션을 반복하십시오
- 사전에 항목이 존재하지 않으면 key = item, value = 1 (count)을 추가하고 입력합니다.
- 항목이 존재하는 경우 사전 int int int int int int int int int int int.
- 두 번째 컬렉션을 반복하십시오
- 항목이 사전에 있지 않으면 False를 반환합니다.
- 항목이 사전 감소 카운트에있는 경우 항목의 경우
- count == 0 인 경우 항목을 제거합니다.
- return dictionary.count == 0;
주문한 컬렉션의 경우 사용할 수 있습니다 SequenceEqual()
확장 방법에 의해 정의되었습니다 System.Linq.Enumerable
:
if (firstCollection.SequenceEqual(secondCollection))
같은 순서로 동일한 항목 또는 동일한 항목을 의미합니까?
어쨌든, 동일한 순서로 동일한 항목을 포함하고 있는지 비교하고 싶다고 가정하면 "Brute Force"는 C# 2.0에서 유일한 옵션입니다. 나는 당신이 비 우아함이 무엇을 의미하는지 알고 있지만 원자 비교 자체가 O (1)이라면 전체 프로세스는 O (n)이어야합니다. 저것 나쁜.
항목이 동일한 순서 (동일 한 것 외에도)이어야하는 경우 최적화로 두 컬렉션을 동시에 동시에 반복하고 각 컬렉션의 현재 항목을 비교할 것을 제안합니다. 그렇지 않으면, 무차별의 힘은 갈 길입니다.
아, 그리고 또 다른 제안 - 당신은 컬렉션 클래스의 평등을 무시하고 그곳에있는 평등을 구현할 수 있습니다 (그러나 프로젝트에 따라 다릅니다).
다시, 두 세트가있는 C5 라이브러리를 사용하면 다음을 사용할 수 있습니다.
C5.ICollection<T> set1 = C5.ICollection<T> (); C5.ICollection<T> set2 = C5.ICollecton<T> (); if (set1.UnsequencedEquals (set2)) { // Do something }
C5 라이브러리에는 실제로 두 세트의 시합되지 않은 해시 코드를 실제로 테스트하는 휴리스틱이 포함되어 있습니다 (참조 C5.ICollection<T>.GetUnsequencedHashCode()
) 따라서 두 세트의 해시 코드가 불평등 한 경우 평등을 테스트하기 위해 모든 항목을 반복 할 필요는 없습니다.
또한 당신에게 주목할만한 것이 있습니다 C5.ICollection<T>
상속 System.Collections.Generic.ICollection<T>
, .NET 인터페이스를 사용하는 동안 C5 구현을 사용할 수 있습니다 (.NET의 인색 인터페이스를 통해 기능이 적은 기능에 액세스 할 수 있지만).
Brute Force는 O (n)을 차지합니다 - 모든 요소가 정렬되었다고 가정합니다 (정렬되었다고 가정)을 비교합니다. 데이터의 속성이 더 쉬워지면 내가 할 수있는 최선이라고 생각합니다.
나는 분류되지 않은 경우, 그 O (n*n).
어떤 경우에, 나는 정렬을 병합하십시오 아마도 도움이 될 것입니다.
예를 들어, 컬렉션이 하나만 있도록 다시 모델링 할 수 있습니까? 또는 3 개의 컬렉션, 하나는 컬렉션 A 만, B에만 적용되고 둘 다에만 적용됩니다. 따라서 A와 B만이 비어 있으면 동일합니다 ... 아마도 잘못된 접선에서 벗어날 것입니다. 여기...