11

次のタイプを想像してください。

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

IList<Account>C# 2.0 で2 つを同期するための最適なアルゴリズムは何ですか? (リンクなし) ?

最初のリスト (L1) は参照リストで、2 番目 (L2) は最初のリストに従って同期するリストです。

  • L1 に存在しなくなった L2 のすべてのアカウントは、L2 から削除する必要があります。
  • L1 にまだ存在する L2 のすべてのアカウントを更新する必要があります (金額属性)
  • L1 にあり、まだ L2 にないすべてのアカウントを L2 に追加する必要があります

Id はアカウントを識別します。単純で機能するアルゴリズムを見つけるのはそれほど難しくありませんが、読みやすさとパフォーマンスを損なうことなくこのシナリオを処理するスマートなソリューションがあるかどうかを知りたいです。

編集：

  • アカウントの種類は関係ありません。クラスである可能性があり、プロパティ、等価メンバーなどがあります。
  • L1 と L2 はソートされていません
  • L2 アイテムは L1 アイテムに置き換えることができませんでした。更新する必要があります (フィールドごと、プロパティごと)
4

7 に答える 7

5

まず、変更可能な構造体を取り除きます。可変値型は根本的に悪いことです。(パブリック フィールドと同様に、IMO.)

2 つのリストの内容を簡単に比較できるように、ディクショナリを作成することをお勧めします。存在/不在を確認する簡単な方法を取得したら、残りは簡単です。

正直なところ、基本的には L2 を L1 の完全なコピーにしたいようですね... L2 をクリアして AddRange を呼び出すだけですか? それとも、L2 を変更している間に他のアクションも実行したいという点ですか?

于 2008-10-02T08:59:56.917 に答える
2

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 は存在しますか?」と尋ねられたときに許容できるパフォーマンスを示すコレクション)、合理的なものを考え出すことができます。

于 2008-10-02T09:43:55.017 に答える
0

これが古い投稿であることは承知していますが、AutoMapper をチェックしてください。非常に柔軟で構成可能な方法で、まさにあなたが望むことを行います。

オートマッパー

于 2010-06-04T20:45:37.567 に答える
0

Jon Skeet のコメントに加えて、Account をクラスに構造化し、Equals() および GetHashCode() メソッドをオーバーライドして、優れた等価性チェックを取得します。

于 2008-10-02T09:01:15.213 に答える
0

L2 = L1.clone()?

...しかし、何か言い忘れていると思います。

于 2008-10-02T09:06:05.500 に答える