두 개의 ICollection<T> 컬렉션에 정확히 같은 항목이 들어 있는지 여부를 확인하는 가장 빠른 방법은 무엇입니까? 무력은 분명합니다. 더 우아한 방법이 있는지 궁금합니다.두 ICollection <T> 컬렉션에 동일한 개체가 들어 있는지 여부를 확인하는 가장 빠른 방법
우리는 C# 2.0을 사용하므로 가능하면 확장 방법을 알려주세요!
편집 : 대답은 정렬 된 컬렉션과 정렬되지 않은 컬렉션 모두에서 흥미로울 것이며 서로 다를 수 있습니다.
사용 C5
http://www.itu.dk/research/c5/
"는 공급 컬렉션의 모든 항목이 가방에있는 경우
(계산 다중도)를 확인합니다.
항목 찾고 있습니다.
모든 항목이 이면 true입니다. "
[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;
}
Ok- ContainsCount가 조회를 위해 해시를 사용하므로 조회가 O (1) - 전체적으로 O (n)입니다 - "this"에 항목의 수퍼 세트가 포함되어 있으면 true를 반환하지만 ... –
브 루트 포스 (Brute force)는 모든 요소를 (내가 소트했다고 가정하고) 비교합니다. 당신이 할 수있는 최선이라고 생각합니다.
정렬되지 않은 경우 해당 O (n * n)을 추측합니다.
이 경우에는 merge sort을 기반으로하는 솔루션이 도움이 될 것이라고 생각합니다.
예를 들어 컬렉션을 하나만 만들도록 모델을 다시 만들 수 있습니까? 또는 컬렉션 3에 포함 된 컬렉션 3 개, 컬렉션 A에만있는 컬렉션 1 개, B 전용 컬렉션 1 개, 그리고 둘 다 포함 된 컬렉션 1 개 - 따라서 A와 B 만 비어 있다면 - 그들은 동일합니다 ... 나는 완전히 잘못된 탄젠트 여기 ...
같은 순서로 동일한 항목이나 동일한 항목을 의미합니까?
어쨌든 동일한 항목이 같은 순서로 포함되어 있는지 비교하려는 경우 C# 2.0에서는 "무차별 대항"이 유일한 옵션입니다. 나는 당신이 우아하지 않다는 것을 안다. 그러나 만약 원자 비교 자체가 O (1)라면, 전체 과정은 O (N)이되어야한다. 은이 아니다.
항목이 동일한 순서 이외의 다른 순서로 있어야하는 경우 최적화로 - 두 컬렉션을 동시에 반복하고 각 컬렉션의 현재 항목을 비교하는 것이 좋습니다. 그렇지 않으면 무차별 한 힘이 갈 길입니다.
아, 또 다른 제안 - 컬렉션 클래스에 대해 Equals를 재정의하고 동등한 항목을 구현할 수 있습니다 (프로젝트에 따라 다름).
먼저 비교해보십시오. 숫자가 같은 경우 컬렉션의이됩니다. 모든 요소에서 무차별 비교가 수행됩니다. 최악의 시나리오는 O (n)입니다. 이 경우 요소의 순서가 같아야합니다.
순서가 동일하지 않습니다 두 번째 경우, 당신은 컬렉션에있는 요소의 수를 저장하기 위해 사전을 사용할 필요가 : 여기에 가능한 알고리즘이다
주문 컬렉션 들어, System.Linq.Enumerable에 의해 정의 된 SequenceEqual() 확장 방법을 사용할 수 있습니다 : 두 세트를 가지고는 C5 라이브러리를 사용하여, 다시
if (firstCollection.SequenceEqual(secondCollection))
을, 당신은 사용할 수 있습니다
C5.ICollection<T> set1 = C5.ICollection<T>();
C5.ICollection<T> set2 = C5.ICollecton<T>();
if (set1.UnsequencedEquals (set2)) {
// Do something
}
C5 라이브러리에는 처음에 두 세트의 순서없는 해시 코드를 실제로 테스트하는 경험적 방법이 포함되어 있습니다 ee C5.ICollection<T>.GetUnsequencedHashCode()) 두 세트의 해시 코드가 동일하지 않은 경우 동등성을 테스트하기 위해 모든 항목을 반복 할 필요가 없도록합니다.
또한 C5.ICollection<T>은 System.Collections.Generic.ICollection<T>에서 상속되므로 .NET 인터페이스를 사용하면서 C5 구현을 사용할 수 있습니다 (.NET의 인색 인터페이스를 통해 기능을 거의 사용할 수는 없지만).
이렇게 빨리 또는 우아한가? 그들은 둘 다 서로 잘 어울리지 않습니다. – nawfal