尽快确定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个列表之间变化的算法？

回答

相关问题