Итерация по 2 спискам - PullRequest
Новая
       30

Итерация по 2 спискам

5 голосов
/ 20 июля 2010

У меня есть List<T1> предметов и второй List<T2> предметов.Оба списка отсортированы в алфавитном порядке по свойству А. Я знаю, что список элементов в List<T2> является подмножеством List<T1>, и в List<T2> не существует элементов, которые не существуют в List<T1>.

Мне нужно перебрать List<T1> и изменять переменную каждый раз, когда она соответствует переменной в List<T2>.Какой самый быстрый и лучший способ сделать это?Я предполагаю, что мне нужно перебрать оба списка, но я знаю, что делать вложенный foreach не имеет смысла.

Ответы [ 4 ]

12 голосов
/ 20 июля 2010

Для такого типа вещей я предпочитаю двойную ходьбу за петлю.См. Пример ниже. 

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) Второй список является подмножеством первого.

5 голосов
/ 20 июля 2010

Если списки не слишком велики, самый простой способ сделать это - вызвать Contains: 

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

Вы можете сделать это быстрее, вызвав BinarySearch, используя пользовательский IComparer<T>, например: 

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 вы можете сделать это быстрее, используя HashSet<T>: 

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

Если ваши списки очень большие, вы должны измерить производительность каждого варианта и выбрать соответственно.
В противном случае выберите один из первых вариантов, который является самым простым.

1 голос
/ 20 июля 2010

Ваш вопрос подразумевает, что вы хотите избежать необходимости перебирать все элементы во втором списке каждый раз, что и происходит в наивном решении наихудшего случая с использованием 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();
1 голос
/ 20 июля 2010

Если они оба отсортированы по уникальному свойству, вы можете использовать это во время итерации. Идея состоит в том, чтобы перебрать надмножество, а затем продвинуть итератор подмножества на основе этого отсортированного уникального свойства, пока оно не совпадет или не станет больше / меньше (в зависимости от порядка сортировки), чем надмножество.

Для объекта, отсортированного по возрастанию: 

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

Обратите внимание, что на самом деле supersetList не является надмножеством subsetList. Решение EndangeredMassa более чистое, если принять это предположение.

...