0

プロジェクトがあります。

これらのプロジェクトは、APIを介してサイトAから私のサイトにダウンロードされます。

サイトAからすべてのプロジェクトをダウンロードします。

私の側には一致するJSONオブジェクトがあります。重要なのは、これを行う必要があるということです。

リストA（私のサイト）はリストB（彼らのサイト）と同期する必要があります。

APIの制限により、手動で同期する必要があります。

したがって、プロジェクトと属性があります。

リストAとリストBが与えられた場合、次のような高速アルゴリズムはどうなるでしょうか。

If A is missing object from B, add it.
If B no longer contains an element found in A, remove it from A.
If an attribute in B is != an attribute in an object from A, update the object in A.

これをたくさん行う唯一の方法はO（N ^ 2）だと思います。これのいくつかでO（N ^ 2）より良くなる方法はありますか？

ありがとう

4

2 に答える 2

0

いくつかのHashSet実装を使用して「含む」条件をチェックすると、平均複雑度がn^2未満になるはずです。

于 2013-02-14T18:46:24.670 に答える
0

A に B のオブジェクトがありません。追加してください。

listA.AddRange(listB.Except(listA)); //note O(N+M) not O(N*M)

B に A で見つかった要素が含まれていない場合は、A から削除します。

listA.RemoveAll(listA.Except(listB)); //note O(N+M) not O(N*M)

B の属性が != A のオブジェクトの属性である場合、A のオブジェクトを更新します。

 //note O(N+M) not O(N*M)
var pairs = listA.Join(listB, 
    item => item.Key, 
    item => item.Key, 
    (a, b) => new { a, b });

foreach(var pair in pairs)
{
    //compare the properties of the items and mutate `pair.a` as appropriate
}

これらすべてのアルゴリズムの漸近的な複雑度は、両方のセットのサイズの積ではなく、両方のセットのサイズの合計であることに注意してください。 Exceptそれぞれ、Join入力シーケンスの 1 つのすべてのアイテムを含むセットベースのデータ構造を作成し、O(1) セットベースの操作を使用して、もう一方を反復処理します。

于 2013-02-14T18:53:15.503 に答える