2 Listeleri boyunca yineleme

Question

Öğeleri List<T1> ve ikinci List<T2> ürünüm var. Her iki liste Ben List<T2> öğelerin listesini bu List<T1> bulunmayan Varlığından List<T1> bir alt kümesi ve List<T2> hiçbir öğe olduğunu biliyoruz mülkiyet A. göre alfabetik olarak sıralanır.

List<T1> aracılığıyla yinelemeli ve List<T2> değişkenindeki bir değişkenle her değiştiğinde bir değişkeni değiştirmem gerekir. Bunu yapmanın en hızlı ve en iyi yolu nedir? Her iki listeden de yinelemeye ihtiyacım var ama katlanmış bir foreach yapmanın mantıklı olmadığını biliyorum.

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

daha hızlı yapabiliriz özel bir IComparer<T> kullanılarak BinarySearch arayarak, böyle: listelerinin çok büyük değilse

Answer 1

Bu tür bir şey için, döngü için çift yürüyüşü tercih ederim. Aşağıdaki örneğe bakınız.

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

Nereye yapmak istediğiniz her tür eylem Act(...) gerçekleştirdiği.

Döngü her seferinde süper listeyi artırır, ancak bir eşleşme bulduğunuzda yalnızca alt listeyi artırır.

Bunun yalnızca iki varsayımınız nedeniyle çalıştığını unutmayın. 1) Listeler hem sıralanır hem de 2) İkinci liste, birincinin bir alt kümesidir.

Answer 2

Bunu yapmak için bu basit yolu Contains çağırmaktır

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

.NET 3.5 olarak

, bir HashSet<T> kullanarak daha hızlı yapabilirsiniz

Listeleriniz çok büyükse, her seçeneğin performansını ölçmeli ve uygun şekilde seçmelisiniz.
Aksi takdirde, en kolay olan ilk seçeneklerden birine gidin.

Answer 3

Her ikisi de benzersiz bir özelliğe göre sıralanırsa, bunu yinelemeniz sırasında kullanabilirsiniz. Bu fikir, üst dizinin içinden geçerek alt sıra yineleyicisini, sıralanan benzersiz özelliğe dayalı olarak, üst sıradakiyle eşleşene kadar veya daha büyük/küçük (sıralama düzenine bağlı olarak) olana kadar ilerletmektir. artan düzende sıralanır bir özellik için

: bu aslında subsetList bir üst olma supersetList itimat etmediğini

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

Not. EndangeredMassa'un çözümü, bu varsayımın doğru olmasıyla daha temizdir.

Answer 4

Sorunuz, ikinci listede yer alan tüm öğelerin üzerinde yineleme yapmaktan kaçınmak istediğiniz anlamına gelir; bu, Contains() kullanarak en kötü durumdaki naif çözümde ne olacağıdır. Her iki liste de sıralandığından ve list2, list1'un bir alt kümesi olduğundan, list1'daki hiçbir girdinin list2'daki karşılık gelen girdiden daha az bir endeksi olduğunu bilmezsiniz.Bunu göz önünde bulundurarak, iki numaralayıcı ile verimli bir O (n) çözüm üretebilirsiniz:

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();