儘快確定2個列表之間變化的算法？

這些項目是從一個網站通過API下載到我的網站。

我從網站下載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）好一些嗎？

感謝

來源

2013-02-14 jmasterx

使用HashSet的和/或一些LINQ加入/聯盟/節選是相當微不足道的。前者可能導致更好的界限，但後者可以......好，更多LINQ'y。 – 2013-02-14 18:47:46

您可以在O（n log n）時間對兩個列表進行排序。你能想到一個算法來比較兩個線性時間操作的排序列表嗎？ – 2013-02-14 18:43:38

使用一些HashSet的實施，檢查「包含」條件也應給予平均小於n的複雜性^ 2

來源

2013-02-14 18:46:24

注意：如果元素是**唯一**（即沒有重複元素），則此方法很有用。 – 2013-02-14 18:52:03

正確，但看起來像米洛已經有機制來識別某種唯一性，如果他發現並刪除列表之間的重複 – 2013-02-14 18:54:57

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.更新對象

//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將分別創建一個基於集合的數據結構，其中包含一個輸入序列中的所有項目，然後使用基於O（1）集合的操作迭代另一個項目。

來源

2013-02-14 18:53:15 Servy

儘快確定2個列表之間變化的算法？

回答

相關問題