Bester Algorithmus für die Synchronisierung von zwei IList in C# 2.0

Question

Stellen Sie sich den folgenden Typ vor:

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

Was ist der beste Algorithmus zur Synchronisierung zweier IList<Account> in C# 2.0 (kein linq) ?

Die erste Liste (L1) ist die Referenzliste, die zweite (L2) ist die Liste, die mit der ersten synchronisiert wird:

• Alle Konten in L2, die nicht mehr in L1 vorhanden sind, müssen in L2 gelöscht werden.
• Alle Konten in L2, die noch in L1 existieren, müssen aktualisiert werden (Betragsattribut)
• Alle Konten, die in L1, aber noch nicht in L2 sind, müssen zu L2 hinzugefügt werden.

Die Id identifiziert Konten. Es ist nicht allzu schwer, einen naiven und funktionierenden Algorithmus zu finden, aber ich würde gerne wissen, ob es eine intelligente Lösung gibt, um dieses Szenario zu handhaben, ohne die Lesbarkeit und Perfs zu ruinieren.

EDITAR :

• Der Kontotyp spielt keine Rolle, er kann eine Klasse sein, hat Eigenschaften, Gleichheitsmitglieder usw.
• L1 und L2 sind nicht sortiert
• L2-Elemente können nicht durch L1-Elemente ersetzt werden, sie müssen aktualisiert werden (Feld für Feld, Eigenschaft für Eigenschaft)

Answer 1

Ich weiß, dies ist ein alter Beitrag, aber Sie sollten sich AutoMapper ansehen. Es wird genau das tun, was Sie in einer sehr flexiblen und konfigurierbaren Weise wollen.

AutoMapper

Answer 2

Einführung

Ich habe zwei Algorithmen implementiert, einen für sortierte und einen für sequentielle Sammlungen. Beide unterstützen Nullwerte und Duplikate und funktionieren auf dieselbe Weise:

Sie bringen Rendite CollectionModification<LeftItemType,RightItemType> s, was ähnlich ist wie CollectionChangedEventArgs<T> ( Referenz ), die im Gegenzug verwendet werden können, um synchronisieren. eine Sammlung.

Bezüglich der Rendite:

Wenn Sie den einen oder anderen Algorithmus verwenden, bei dem die linken Elemente (die Referenzsammlung) mit den rechten Elementen verglichen werden, können Sie jeden zurückgegebenen Ertrag anwenden CollectionModification sobald sie zurückgegeben werden, aber dies kann zu einer "Sammlung wurde geändert"-Ausnahme führen (zum Beispiel bei der Verwendung von List<T>.GetEnumerator ). Um dies zu verhindern, haben beide Algorithmen die Möglichkeit implementiert, eine indizierbare Sammlung als Referenzsammlung zu verwenden, die gerade geändert wird. Sie müssen die Referenzsammlung lediglich mit YieldIteratorInfluencedReadOnlyList<ItemType> (abstrakt) durch die Verwendung der Erweiterungsmethoden in YieldIteratorInfluencedReadOnlyListExtensions . :)

SortedCollectionModifications

Der erste Algorithmus funktioniert für aufsteigende oder absteigende geordnete Listen und verwendet 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)

Der Python-Algorithmus ist inspiriert von: Effiziente Synchronisierung von zwei Instanzen einer geordneten Liste .

EqualityTrailingCollectionModifications

Der zweite Algorithmus funktioniert für jede Reihenfolge und verwendet 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

Anforderungen

Einer der folgenden Rahmen ist erforderlich

• .NET-Standard 2.0
• .NET Core 3.1
• .NET 5.0

Beide Algorithmen werden mit benutzerdefinierten implementierten Typen erstellt ( IndexDirectory , NullableKeyDictionary , LinkedBucketList um nur einige zu nennen), so dass ich den Code nicht einfach kopieren und hier einfügen kann. Daher möchte ich Sie auf meine folgenden Pakete verweisen:

• Teronis.NetStandard.Core : Wird vorübergehend von den folgenden Paketen verwendet
• Teronis.NetStandard.Sammlungen : Enthält einige benutzerdefinierte Sammlungstypen. Wird vorübergehend von den folgenden Paketen verwendet
• Teronis.NetStandard.Collections.Algorithmen : Enthält die Algorithmen
• Teronis.NetStandard.Collections.Synchronisation : Enthält die Synchronisierungsklassen der Sammlungen

Umsetzung

Anitzipierte Klassen

Konto :

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

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

Und die folgende Sammlung Element Gleichheit Komparator Klasse:

AccountEqualityComparer :

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

"Meine" Klassen

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

Programm :

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.");

        ;
    }
}

Sie können sehen, dass ich SyncingCollectionViewModel ein sehr "schwerer" Typ. Das ist, weil ich nicht das Leichtgewicht beendet haben SynchronizableCollection Implementierung noch nicht (es fehlen virtuelle Methoden für add, remove, replace usw.).