2 목록 반복

Question

나는 List<T1> 개의 항목과 두 번째 List<T2> 개의 항목을 가지고 있습니다. 두 목록 모두 속성 A에 의해 사전 순으로 정렬됩니다. List<T2>의 항목 목록은 List<T1>의 하위 집합이며 에는없는 List<T2>의 항목이 존재하지 않습니다.

List<T1>을 반복하고 List<T2>의 변수와 매치 할 때마다 변수를 변경해야합니다. 가장 빠른 방법은 무엇입니까? 두 목록을 반복해야한다고 가정하고 있지만 중첩 된 foreach를 수행하는 것이 의미가 없다는 것을 알고 있습니다.

이

foreach(var item in list1) { 
    if (list2.Contains(item) { 
     //Do something 
    } 
} 

당신은 빨리 만들 수있는 사용자 정의 IComparer<T>를 사용하여 BinarySearch를 호출하여, 다음과 같이 : 목록이 너무 큰 수없는 경우

Answer 1

이 유형의 경우 루프를 두 번 걷는 것이 더 좋습니다. 아래 예제를 참조하십시오.

var super = new List<Contact>(); 
super.Add(new Contact() {Name = "John"}); 
super.Add(new Contact() {Name = "Larry"}); 
super.Add(new Contact() {Name = "Smith"}); 
super.Add(new Contact() {Name = "Corey"}); 

var sub = new List<Contact>(); 
sub.Add(new Contact() {Name = "Larry"}); 
sub.Add(new Contact() {Name = "Smith"}); 

var subCount = 0; 
for(int i=0; i<super.Count && subCount < sub.Count; i++) 
{ 
    if (super[i].Name == sub[subCount].Name) 
    { 
     Act(super[i], sub[subCount]); 
     subCount++; 
    } 
} 

여기에서 Act(...)은 사용자가 원하는 모든 작업을 수행합니다.

루프는 매번 수퍼 목록을 증가 시키지만 일치 항목을 찾을 때만 하위 목록을 증가시킵니다.

두 가지 가정 때문에 작동하는 것에 유의하십시오. 1) 목록은 모두 정렬되어 있고 2) 두 번째 목록은 첫 번째 목록의 하위 집합입니다.

Answer 2

는이 작업을 수행하는이 간단한 방법은 Contains를 호출하는 것입니다

var hashset = new HashSet<YourClass>(list2); 
foreach(var item in list1) { 
    if (hashset.Contains(item) { 
     //Do something 
    } 
} 

:

class MyComparer : IComparer<YourClass> { 
    private MyComparer() { } 
    public static readonly MyComparer Instance = new MyComparer(); 

    public int CompareTo(YourClass a, YourClass b) { 
     //TODO: Handle nulls 
     return a.SomeProperty.CompareTo(b.SomeProperty); 
    } 
} 
foreach(var item in list1) { 
    if (list2.BinarySearch(item, MyComparer.Instance) >= 0) { 
     //Do something 
    } 
} 

닷넷 3.5에서

, 당신은 HashSet<T>를 사용하여 빠르게 만들 수 있습니다

목록이 매우 큰 경우 각 옵션의 성능을 측정하고 적절하게 선택해야합니다.
그렇지 않으면 가장 간단한 첫 번째 옵션 중 하나를 선택하십시오.

Answer 3

둘 다 고유 한 속성으로 정렬 된 경우 반복하는 동안이 속성을 사용할 수 있습니다. 아이디어는 수퍼 세트를 반복하고 그 수퍼 세트보다 더 크거나 작은 (정렬 순서에 따라) 때까지 그 정렬 된 고유 한 속성을 기반으로 서브 세트 이터레이터를 진행하는 것입니다. 오름차순으로 정렬 속성에 대한

이 실제로 subsetList의 상위 집합 인 supersetList에 의존하지 않는

if (subsetList.Count > 0) 
{ 
    using(IEnumerator<T2> subset = subsetList.GetEnumerator()) 
    { 
     subset.MoveNext(); 
     T2 subitem = subsetList.Current; 
     foreach(T1 item in supersetList) 
     { 
      while (item.A > subitem.A && 
        subset.MoveNext()) 
      { 
       subitem = subset.Current; 
      } 

      if (item.A == subitem.A) 
      { 
       // Modify item here. 
      } 
     } 
    } 
} 

참고. EndangeredMassa의 해결책은 사실이라는 전제하에 더 깨끗합니다.

Answer 4

귀하의 질문은 매번 두 번째 목록의 모든 항목을 반복하지 않아도된다는 것을 의미합니다. 이는 최악의 경우 순도가 Contains() 인 솔루션에서 발생합니다. 두 목록 모두 정렬되어 있고 list2은 list1의 하위 집합이므로 list1에있는 항목의 색인이 list2의 해당 항목보다 작을 것입니다.이를 염두에 두 명의 열거자를 통해 효율적인 O (n) 솔루션을 만들 수 있습니다.

Debug.Assert(list1.Count > 0); 
Debug.Assert(list1.Count >= list2.Count); 

var enum1 = list1.GetEnumerator(); 
var enum2 = list2.GetEnumerator(); 

enum1.MoveNext(); 
while (enum2.MoveNext()) 
{ 
    // Skip elements from list1 that aren't equal to the current entry in list2 
    while (!enum1.Current.Equals(enum2.Current)) 
     enum1.MoveNext(); 

    // Fire the OnEqual event for every entry in list1 that's equal to an entry 
    // in list2 
    do { 
     OnEqual(enum1.Current, enum2.Current); 
    } while (enum1.MoveNext() && enum1.Current.Equals(enum2.Current)); 
} 

enum1.Dispose(); 
enum2.Dispose();