python3 itertools.filterfalse非常慢。有哪些替代方案？

Question

我想获取两个dict变量列表之间的差异。这些列表每个包含100,000个项目。当我编写下面的代码时，它花费了超过2分钟的时间。 （我的旧笔记本电脑配有Intel®Core™i7-4700HQ CPU @ 2.40GHz×8）

added_items = list(itertools.filterfalse(lambda x: x in records_old, records_new))

这是示例记录；

[{"email": "[email protected]", "login": "user-01", "type": "member"},

此外，我还需要比较键和值。您能建议其他更快的方法吗？

Answer 1

您的代码是O（n ^ 2）时间复杂度和O（1）空间。

在编程中，我们经常可以用时间来换取空间。此方法应为O（n）时间和O（n）空间，并在运行时有所改进：

records_old_set = {frozenset(r.items()) for r in records_old}
added_items = [r for r in records_new if frozenset(r.items()) not in records_old_set]