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

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

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

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

Если ваши два списка отсортированы, вы можете просто просмотреть их в тандеме. Это операция 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?»), то вы могли бы придумать что-то разумное.

У меня была та же проблема, и моим лучшим решением было следующее (адаптированное к вашему случаю) с загрузкой обоих списков:

1. For each Account in L1, verify if it exists in L2:
   • If found, update all values from L1's Account based on L2's. Then, delete the Account from L2.
   • Если не найдено, пометьте Учетную запись L1 как удаленную или удалите ее из списка, это зависит от структуры вашей базы данных.
2. Для каждого аккаунта, оставшегося в L2, добавьте его в L1.

Я рекомендую реализовать интерфейс IEquatable<> в вашем классе Account (или просто переопределить метод Equals()), чтобы он всегда сравнивал идентификаторы в методах, требующих сравнения между объектами:

public struct Account : IEquatable<Account>
{
    public int Id;
    public double Amount;

    public bool Equals(Account other)
    {
        if (other == null) return false;
        return (this.Id.Equals(other.Id));
    }
}

Алгоритм синхронизации будет примерно таким (убедитесь, что оба списка инициализированы, чтобы не возникало ошибок):

L1.ForEach (L1Account =>
{
    var L2Account = L2.Find(a => a.Id == L1Account.id);
    // If found, update values
    if (L2Account != null)
    {
        L1Account.Amount = L2Account.Amount;
        L2.Remove(L2Account);
    }
    // If not found, remove it
    else
    {
        L1.Remove(L1Account);
    }
}
// Add any remaining L2 Account to L1
L1.AddRange(L2);

В дополнение к комментарию Джона Скита сделайте свою учетную запись структурой класса и переопределите методы Equals() и GetHashCode(), чтобы получить хорошую проверку на равенство.

L2 = L1.клон()?

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

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

AutoMapper

Вступление

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

Они возвращают CollectionModification<LeftItemType,RightItemType>s, что похоже на CollectionChangedEventArgs<T> (ссылка), которую можно использовать взамен для синхронизации коллекции.

Относительно доходности:

При использовании того или иного алгоритма, в котором ваши левые элементы (ссылочная коллекция) сравниваются с правыми элементами, вы можете применить каждый возвращаемый доход CollectionModification, как только они возвращаются, но это может привести к тому, что коллекция была изменена-исключением (для пример при использовании List<T>.GetEnumerator). Чтобы предотвратить это, в обоих алгоритмах реализована возможность использовать индексируемую коллекцию в качестве эталонной коллекции, которая должна быть изменена. Вам нужно только обернуть эталонную коллекцию с помощью YieldIteratorInfluencedReadOnlyList<ItemType> (abstract), используя методы расширения в YieldIteratorInfluencedReadOnlyListExtensions. :)

SortedCollectionModifications

Первый алгоритм работает для восходящих или нисходящих упорядоченных списков и использует IComparer<T>.

/// <summary>
/// The algorithm creates modifications that can transform one collection into another collection.
/// The collection modifications may be used to transform <paramref name="leftItems"/>.
/// Assumes <paramref name="leftItems"/> and <paramref name="rightItems"/> to be sorted by that order you specify by <paramref name="collectionOrder"/>.
/// Duplications are allowed but take into account that duplications are yielded as they are appearing.
/// </summary>
/// <typeparam name="LeftItemType">The type of left items.</typeparam>
/// <typeparam name="RightItemType">The type of right items.</typeparam>
/// <typeparam name="ComparablePartType">The type of the comparable part of left item and right item.</typeparam>
/// <param name="leftItems">The collection you want to have transformed.</param>
/// <param name="getComparablePartOfLeftItem">The part of left item that is comparable with part of right item.</param>
/// <param name="rightItems">The collection in which <paramref name="leftItems"/> could be transformed.</param>
/// <param name="getComparablePartOfRightItem">The part of right item that is comparable with part of left item.</param>
/// <param name="collectionOrder">the presumed order of items to be used to determine <see cref="IComparer{T}.Compare(T, T)"/> argument assignment.</param>
/// <param name="comparer">The comparer to be used to compare comparable parts of left and right item.</param>
/// <param name="yieldCapabilities">The yieldCapabilities that regulates how <paramref name="leftItems"/> and <paramref name="rightItems"/> are synchronized.</param>
/// <returns>The collection modifications.</returns>
/// <exception cref="ArgumentNullException">Thrown when non-nullable arguments are null.</exception>
public static IEnumerable<CollectionModification<LeftItemType, RightItemType>> YieldCollectionModifications<LeftItemType, RightItemType, ComparablePartType>(
    IEnumerable<LeftItemType> leftItems,
    Func<LeftItemType, ComparablePartType> getComparablePartOfLeftItem,
    IEnumerable<RightItemType> rightItems,
    Func<RightItemType, ComparablePartType> getComparablePartOfRightItem,
    SortedCollectionOrder collectionOrder,
    IComparer<ComparablePartType> comparer,
    CollectionModificationsYieldCapabilities yieldCapabilities)

Вдохновение для алгоритма Python взято из: Эффективная синхронизация двух экземпляров упорядоченного списка.

РавенствоTrailingCollectionModifications

Второй алгоритм работает для любого порядка и использует IEqualityComparer<T>.

/// <summary>
/// The algorithm creates modifications that can transform one collection into another collection.
/// The collection modifications may be used to transform <paramref name="leftItems"/>.
/// The more the collection is synchronized in an orderly way, the more efficient the algorithm is.
/// Duplications are allowed but take into account that duplications are yielded as they are appearing.
/// </summary>
/// <typeparam name="LeftItemType">The type of left items.</typeparam>
/// <typeparam name="RightItemType">The type of right items.</typeparam>
/// <typeparam name="ComparablePartType">The type of the comparable part of left item and right item.</typeparam>
/// <param name="leftItems">The collection you want to have transformed.</param>
/// <param name="getComparablePartOfLeftItem">The part of left item that is comparable with part of right item.</param>
/// <param name="rightItems">The collection in which <paramref name="leftItems"/> could be transformed.</param>
/// <param name="getComparablePartOfRightItem">The part of right item that is comparable with part of left item.</param>
/// <param name="equalityComparer">The equality comparer to be used to compare comparable parts.</param>
/// <param name="yieldCapabilities">The yield capabilities, e.g. only insert or only remove.</param>
/// <returns>The collection modifications.</returns>
/// <exception cref="ArgumentNullException">Thrown when non-nullable arguments are null.</exception>
public static IEnumerable<CollectionModification<LeftItemType, RightItemType>> YieldCollectionModifications<LeftItemType, RightItemType, ComparablePartType>(
    IEnumerable<LeftItemType> leftItems,
    Func<LeftItemType, ComparablePartType> getComparablePartOfLeftItem,
    IEnumerable<RightItemType> rightItems,
    Func<RightItemType, ComparablePartType> getComparablePartOfRightItem,
    IEqualityComparer<ComparablePartType>? equalityComparer,
    CollectionModificationsYieldCapabilities yieldCapabilities)
    where ComparablePartType : notnull

Требования

Требуется одна из следующих платформ

• .NET-Стандарт 2.0
• .NET Core 3.1
• .NET 5.0

Оба алгоритма созданы с пользовательскими реализованными типами (IndexDirectory, NullableKeyDictionary, LinkedBucketList, чтобы назвать несколько), поэтому я не могу просто скопировать и вставить сюда код, поэтому я хотел бы сослаться на мои следующие пакеты:

• Teronis.NetStandard.Core: переходное использование по пакетам ниже
• Teronis.NetStandard.Collections: содержит несколько пользовательских типов коллекций. Транзитивно используется пакетами ниже
• Teronis.NetStandard.Collections.Algorithms: содержит алгоритмы
• Teronis.NetStandard.Collections.Synchronization: Содержит классы синхронизации коллекций.

Реализация

Ожидаемые занятия

Аккаунт:

public class Account
{
    public Account(int id) =>
        Id = id;

    public int Id { get; }
    public double Amount { get; }
}

И следующий класс сравнения равенства элементов коллекции:

Comparer AccountEquality:

public class AccountEqualityComparer : EqualityComparer<Account>
{
    public new static AccountEqualityComparer Default = new AccountEqualityComparer();

    public override bool Equals([AllowNull] Account x, [AllowNull] Account y) =>
        ReferenceEquals(x, y) || (!(x is null && y is null) && x.Id.Equals(y.Id));

    public override int GetHashCode([DisallowNull] Account obj) =>
        obj.Id;
}

Мои занятия

AccountCollectionViewModel:

using Teronis.Collections.Algorithms.Modifications;
using Teronis.Collections.Synchronization;
using Teronis.Collections.Synchronization.Extensions;
using Teronis.Reflection;

public class AccountCollectionViewModel : SyncingCollectionViewModel<Account, Account>
{
    public AccountCollectionViewModel()
        : base(CollectionSynchronizationMethod.Sequential(AccountEqualityComparer.Default))
    {
        // In case of SyncingCollectionViewModel, we have to pass a synchronization method.
        //
        //   Sequential means any order
        //
    }

    protected override Account CreateSubItem(Account superItem) =>
        superItem;

    protected override void ApplyCollectionItemReplace(in ApplyingCollectionModificationBundle modificationBundle)
    {
        foreach (var (oldItem, newItem) in modificationBundle.OldSuperItemsNewSuperItemsModification.YieldTuplesForOldItemNewItemReplace())
        {
            // Implementation detail: update left public property values by right public property values.
            TeronisReflectionUtils.UpdateEntityVariables(oldItem, newItem);
        }
    }
}

Программа:

using System.Diagnostics;
using System.Linq;

class Program
{
    static void Main()
    {
        // Arrange
        var collection = new AccountCollectionViewModel();

        var initialData = new Account[] {
            new Account(5) { Amount = 0 },
            new Account(7) { Amount = 0 },
            new Account(3) { Amount = 0 }
        };

        var newData = new Account[] {
            new Account(5) { Amount = 10 }, 
            /* Account by ID 7 got removed .. */ 
            /* but account by ID 8 is new. */ 
            new Account(8) { Amount = 10 },
            new Account(3) { Amount = 10 }
        };

        // Act
        collection.SynchronizeCollection(initialData);

        // Assert
        Debug.Assert(collection.SubItems.ElementAt(1).Id == 7, "The account at index 1 has not the ID 7.");
        Debug.Assert(collection.SubItems.All(x => x.Amount == 0), "Not all accounts have an amount of 0.");

        // Act
        collection.SynchronizeCollection(newData);

        // Assert
        Debug.Assert(collection.SubItems.ElementAt(1).Id == 8, "The account at index 1 has not the ID 8.");
        Debug.Assert(collection.SubItems.All(x => x.Amount == 10), "Not all accounts have an amount of 10.");

        ;
    }
}

Вы можете видеть, что я использую SyncingCollectionViewModel, очень тяжелый тип. Это потому, что я не закончил легкий SynchronizableCollection еще не реализован (отсутствуют виртуальные методы для добавления, удаления, замены и т.д.).