Лучший алгоритм для синхронизации двух IList в С# 2.0

Представьте себе следующий тип:

public struct Account
{
    public int Id;
    public double Amount;
}

Каков наилучший алгоритм для синхронизации двух IList<Account> в С# 2.0? (Нет linq)?

Первый список (L1) - это список ссылок, второй (L2) - тот, который будет синхронизироваться в соответствии с первым:

  • Все учетные записи в L2, которые больше не присутствуют в L1, должны быть удалены из L2
  • Все учетные записи в L2, которые все еще существуют в L1, должны быть обновлены (атрибут суммы)
  • Все учетные записи, которые находятся в L1, но еще не включены в L2, должны быть добавлены к L2

Идентификатор идентифицирует учетные записи. Нелегко найти наивный и рабочий алгоритм, но я хотел бы знать, есть ли интеллектуальное решение для обработки этого сценария, не нарушая читаемости и perfs.

ИЗМЕНИТЬ:

  • Тип учетной записи не имеет значения, может быть класс, имеет свойства, члены равенства и т.д.
  • L1 и L2 не сортируются
  • Элементы L2 не могут быть заменены элементами L1, они должны быть обновлены (поле за полем, свойство по свойству)

Ответы

Ответ 1

Для начала я бы избавился от изменяемой структуры. Типы взаимозаменяемых значений - это в корне плохая вещь. (Как и общедоступные поля, ИМО.)

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

Честно говоря, похоже, что вы в основном хотите, чтобы L2 был полной копией L1... очистить L2 и просто вызвать AddRange? Или в том, что вы также хотите выполнять другие действия, пока вы меняете L2?

Ответ 2

Если ваши два списка отсортированы, вы можете просто пройти через них в тандеме. Это операция O (m + n). Следующий код может помочь:

class Program
{
    static void Main()
    {
        List<string> left = new List<string> { "Alice", "Charles", "Derek" };
        List<string> right = new List<string> { "Bob", "Charles", "Ernie" };

        EnumerableExtensions.CompareSortedCollections(left, right, StringComparer.CurrentCultureIgnoreCase,
            s => Console.WriteLine("Left: " + s), s => Console.WriteLine("Right: " + s), (x,y) => Console.WriteLine("Both: " + x + y));
    }
}

static class EnumerableExtensions
{
    public static void CompareSortedCollections<T>(IEnumerable<T> source, IEnumerable<T> destination, IComparer<T> comparer, Action<T> onLeftOnly, Action<T> onRightOnly, Action<T, T> onBoth)
    {
        EnumerableIterator<T> sourceIterator = new EnumerableIterator<T>(source);
        EnumerableIterator<T> destinationIterator = new EnumerableIterator<T>(destination);

        while (sourceIterator.HasCurrent && destinationIterator.HasCurrent)
        {
            // While LHS < RHS, the items in LHS aren't in RHS
            while (sourceIterator.HasCurrent && (comparer.Compare(sourceIterator.Current, destinationIterator.Current) < 0))
            {
                onLeftOnly(sourceIterator.Current);
                sourceIterator.MoveNext();
            }

            // While RHS < LHS, the items in RHS aren't in LHS
            while (sourceIterator.HasCurrent && destinationIterator.HasCurrent && (comparer.Compare(sourceIterator.Current, destinationIterator.Current) > 0))
            {
                onRightOnly(destinationIterator.Current);
                destinationIterator.MoveNext();
            }

            // While LHS==RHS, the items are in both
            while (sourceIterator.HasCurrent && destinationIterator.HasCurrent && (comparer.Compare(sourceIterator.Current, destinationIterator.Current) == 0))
            {
                onBoth(sourceIterator.Current, destinationIterator.Current);
                sourceIterator.MoveNext();
                destinationIterator.MoveNext();
            }
        }

        // Mop up.
        while (sourceIterator.HasCurrent)
        {
            onLeftOnly(sourceIterator.Current);
            sourceIterator.MoveNext();
        }

        while (destinationIterator.HasCurrent)
        {
            onRightOnly(destinationIterator.Current);
            destinationIterator.MoveNext();
        }
    }
}

internal class EnumerableIterator<T>
{
    private readonly IEnumerator<T> _enumerator;

    public EnumerableIterator(IEnumerable<T> enumerable)
    {
        _enumerator = enumerable.GetEnumerator();
        MoveNext();
    }

    public bool HasCurrent { get; private set; }

    public T Current
    {
        get { return _enumerator.Current; }
    }

    public void MoveNext()
    {
        HasCurrent = _enumerator.MoveNext();
    }
}

Однако вы должны быть осторожны при изменении коллекций, итерации по ним.

Если они не отсортированы, то сравнение каждого элемента в одном с каждым элементом в другом - это O (mn), который становится очень тяжелым.

Если вы можете скопировать значения ключей из каждой коллекции в словарь или аналогичный (т.е. коллекция с приемлемой производительностью при запросе "присутствует ли X?" ), тогда вы можете придумать что-то разумное.

Ответ 3

В дополнение к комментарию Jon Skeet создайте свою учетную запись struct a class и переопределите метод Equals() и GetHashCode(), чтобы получить хорошую проверку равенства.

Ответ 4

L2 = L1.clone()?

... но я бы предположил, что вы забыли что-то упомянуть.

Ответ 5

Я знаю, что это старый пост, но вы должны проверить AutoMapper. Он будет делать именно то, что вы хотите, очень гибким и настраиваемым способом.

AutoMapper