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每个都将创建一个基于集合的数据结构，其中包含一个输入序列中的所有项目，然后使用 O(1) 基于集合的操作迭代另一个。

于 2013-02-14T18:53:15.503 回答