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

Für den Anfang würde ich die veränderbare Struktur loswerden. Veränderbare Wertetypen sind eine grundsätzlich schlechte Sache. (Wie auch öffentliche Felder, IMO.)

Es lohnt sich wahrscheinlich, ein Wörterbuch zu erstellen, damit Sie den Inhalt der beiden Listen leicht vergleichen können. Sobald Sie diese einfache Möglichkeit haben, das Vorhandensein bzw. Nichtvorhandensein zu überprüfen, sollte der Rest kein Problem mehr darstellen.

Um ehrlich zu sein, klingt es aber so, als wollten Sie, dass L2 eine vollständige Kopie von L1 ist... L2 löschen und nur AddRange aufrufen? Oder geht es Ihnen darum, dass Sie auch andere Aktionen durchführen wollen, während Sie L2 ändern?

Answer 2

Wenn Ihre beiden Listen sortiert sind, können Sie sie einfach nacheinander durchgehen. Dies ist eine O(m+n)-Operation. Der folgende Code könnte dabei helfen:

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

Sie müssen jedoch vorsichtig sein, wenn Sie die Sammlungen bei der Iteration über sie ändern.

Wenn sie nicht sortiert sind, dann ist der Vergleich jedes Elements in dem einen mit jedem Element in dem anderen O(mn), was sehr schnell mühsam wird.

Wenn Sie es ertragen können, die Schlüsselwerte aus jeder Sammlung in ein Dictionary oder ähnliches zu kopieren (d. h. eine Sammlung mit akzeptabler Leistung bei der Frage "Ist X vorhanden?"), dann könnten Sie etwas Vernünftiges auf die Beine stellen.

Answer 3

Ich hatte das gleiche Problem, und meine beste Lösung war die folgende (an Ihren Fall angepasst), wobei beide Listen geladen waren:

1. Für jede Konto in L1, prüfen Sie, ob er in L2 existiert:
   • Falls gefunden, aktualisieren Sie alle Werte aus L1's Konto basierend auf L2's. Löschen Sie dann die Konto von L2.
   • Wenn nicht gefunden, markieren Sie L1's Konto als gelöscht markieren oder aus der Liste löschen, hängt davon ab, wie Ihre Datenbank strukturiert ist.
2. Für jede Konto links in L2, fügen Sie es zu L1 hinzu.

Ich empfehle die Implementierung der IEquatable<> Schnittstelle in Ihrem Konto Klasse (oder überschreiben Sie einfach die Equals() Methode), so dass sie bei Methoden, die einen Vergleich zwischen Objekten erfordern, immer IDs vergleicht:

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

Der Synchronisationsalgorithmus würde etwa so aussehen (stellen Sie sicher, dass beide Listen initialisiert sind, damit keine Fehler auftreten):

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

Answer 4

Zusätzlich zu Jon Skeets Kommentar machen Sie Ihre Account-Struktur zu einer Klasse und überschreiben Sie die Equals() und GetHashCode()-Methode, um eine schöne Gleichheitsprüfung zu erhalten.

Answer 5

L2 = L1.clone()?

... aber ich vermute, Sie haben etwas vergessen zu erwähnen.