두 개의 icollection 컬렉션이 동일한 개체를 포함하는지 여부를 찾는 가장 빠른 방법

StackOverflow https://stackoverflow.com/questions/308476

문제

두 가지를 찾는 가장 빠른 방법은 무엇입니까 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만이 비어 있으면 동일합니다 ... 아마도 잘못된 접선에서 벗어날 것입니다. 여기...

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top