python - python 中具有 o(n) 顺序的大列表的快速列表减法

Question

我在 python 中有两个大字符串列表。我想以 o(n) 的顺序快速减去这两个列表。我找到了一些方法，例如从第一个列表中删除循环中的第二个列表元素，或者将列表转换为 set() (问题:更改列表的顺序)并使用减号(-)运算符，但这些方法效率不高。有什么办法可以实现这个操作吗？

a=['1','2','3',...,'500000']
b=['1','2','3',...,'200000']

c=a-b

c=['200001','200002',...,'500000']

Answer 1

按照表述，您的问题是:

• 遍历A
• 对于每个元素，在B中查找，没有找到则取
• 不对元素做出任何假设

对于任意数据，列表搜索为 O(N)，集合搜索为 O(1)，转换为集合为 O(N)。遍历 A 的时间复杂度为 O(N)。

因此，仅使用列表的复杂度为 O(N^2)，如果将 B 转换为集合，则复杂度为 O(N)。

加快速度的唯一方法是提高迭代或搜索的效率——如果不使用一些关于数据的额外知识，这是不可能的。例如

• 在您的示例中，您的数据是连续的数字，因此您可以采用 A[len(B):]。
• 如果您要多次使用同一个 B，则可以缓存该集合
• 您可以立即将 B 设为一组(如果需要保留顺序，可以使用 an ordered set )
• 如果所有数据都属于同一类型且较短，you can use numpy arrays而且速度很快setdiff1d
• 等等