用于尽可能快地确定两个列表之间的变化的算法

本文关键字：两个 列表 之间 变化 算法 尽可能 用于 | 更新日期: 2023-09-27 17:59:06

我有项目。

这些项目通过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）更好的方法？

感谢

用于尽可能快地确定两个列表之间的变化的算法

使用一些HashSet实现来检查"Contains"条件也应该给出小于n^2 的平均复杂度

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）集合的操作对另一个进行迭代。

相关文章：