Lặp lại qua 2 Danh sách

Question

Tôi có một mặt hàng List<T1> và List<T2> mặt hàng thứ hai. Cả hai danh sách được sắp xếp theo thứ tự bảng chữ cái của thuộc tính A. Tôi biết rằng danh sách các mục trong List<T2> là một tập con của List<T1> và không có mục nào trong số List<T2> tồn tại không tồn tại trong List<T1>.

Tôi cần lặp lại thông qua List<T1> và thay đổi biến mỗi lần khớp với biến trong List<T2>. Cách nhanh nhất và tốt nhất để làm điều này là gì? Tôi giả sử tôi cần phải lặp qua cả hai danh sách nhưng tôi biết làm một foreach lồng nhau sẽ không có ý nghĩa.

Answer 1

Đối với loại điều này, tôi thích đi bộ đôi cho vòng lặp. Xem ví dụ bên dưới.

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++; 
    } 
} 

Trường hợp Act(...) thực hiện bất kỳ hành động nào bạn muốn làm.

Vòng lặp tăng danh sách siêu mỗi lần, nhưng chỉ tăng danh sách phụ khi bạn tìm thấy kết quả phù hợp.

Lưu ý rằng điều này chỉ hoạt động vì hai giả định của bạn. 1) Các danh sách được sắp xếp và 2) Danh sách thứ hai là một tập hợp con của danh sách đầu tiên.

Answer 2

Nếu danh sách không phải là quá lớn, cách này đơn giản nhất để làm điều này là để gọi Contains:

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

Bạn có thể làm cho nó nhanh hơn bằng cách gọi BinarySearch sử dụng một tùy chỉnh IComparer<T>, như thế này:

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 
    } 
} 

Trong Net 3.5, bạn có thể làm cho nó nhanh hơn bằng cách sử dụng một HashSet<T>:

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

Nếu danh sách của bạn rất lớn, bạn nên đo lường hiệu suất của từng tùy chọn và chọn phù hợp.
Nếu không, hãy chọn một trong các tùy chọn đầu tiên, đơn giản nhất.

Answer 3

Nếu cả hai được sắp xếp trên một thuộc tính duy nhất, bạn có thể sử dụng tính năng này trong khi lặp lại. Ý tưởng là để lặp qua superset, và sau đó tạm ứng các iterator bộ phụ dựa trên đó được sắp xếp tài sản duy nhất cho đến khi nó hoặc là phù hợp hoặc là lớn hơn/nhỏ hơn (tùy thuộc vào thứ tự sắp xếp) so với superset một.

Đối với tài sản được sắp xếp theo thứ tự tăng dần:

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. 
      } 
     } 
    } 
} 

Lưu ý rằng điều này không thực sự dựa vào supersetList là một superset của subsetList. EndangeredMassa của giải pháp là sạch hơn với giả định đó là đúng sự thật.

Answer 4

Câu hỏi của bạn ngụ ý rằng bạn muốn tránh phải lặp lại tất cả các mục trong danh sách thứ hai mỗi lần, đó là điều sẽ xảy ra trong giải pháp ngây thơ tệ nhất bằng cách sử dụng Contains(). Vì cả hai danh sách đều được sắp xếp và list2 là một tập con của list1, bạn biết rằng không có mục nhập nào trong list1 sẽ có chỉ mục nhỏ hơn mục nhập tương ứng trong list2.Với ý nghĩ đó, bạn có thể tạo một giải pháp O (n) hiệu quả với hai điều tra viê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();