检查两个字典是否不相交

Question

有没有比计算它们的交集更容易/更快地找出两个字典是否不相交的方法？

对于交集，我找到了这个答案，所以不相交测试会像这样：

def dicts_disjoint(a, b):
    keys_a = set(a.keys())
    keys_b = set(b.keys())
    intersection = keys_a & keys_b
    return not len(intersection)

然而，我认为这种方法效率较低，因为它总是计算整个交集（没有短路退出）。

有更好的想法吗？

- Johannes

Answer 1

不要将其转换为集合；dict_keys对象已经支持isdisjoint。

d1.keys().isdisjoint(d2)

- Veedrac

---

+1，仅适用于Python 3，但我不知道这一点，似乎这是.keys()提供的唯一（非私有）方法！ - Chris_Rands

Answer 2

您是否在寻找类似以下的内容：

def dicts_disjoint(a, b):
    return not any(k in b for k in a)

或者：

def dicts_disjoint(a, b):
    return all(k not in b for k in a)

两个电路都会短路。

- AChampion

---

可能更容易阅读为all(k not in b for k in a)。我总是不得不两次阅读not any xD - Ma0

你确定这比集合交集更快（正如 OP 所需）吗？ - randomir

这将取决于字典的大小，对于较小的字典来说速度会更快。两者都是O(n)，但对于较大的字典，集合交集将具有C代码的优势，以克服set()构造，只要它们是不相交的。 - AChampion

我猜如果你有一个非常大的字典和一个非常小的字典，如果a是较小的那个，速度会更快。对吗？（假设字典查找是恒定时间） - Johannes

是的，dict 查找是 O(1)。 - AChampion

Answer 3

仅编辑显示方法和时间

由于OP询问了执行此操作的最快方法，我根据（希望）在我的电脑上进行的公平测试对讨论中的方法进行了排名。目标是找到字典键是否不相交，似乎 dict_keys.isdisjoint() 方法优于其他集合或列表操作。

但是，如其他答案所述，这将根据相关字典的大小以及它们是否不相交而变化。

这些测试仅针对两个相等（小）大小且不相交的字典。

最快的方法： dict_keys.isdisjoint()

示例：

{"a": 1, "b": 2, "c": 3 }.keys().isdisjoint({ "d": 4, "e": 5, "f": 6}.keys())

时间：

>>> timeit.timeit('{"a": 1, "b": 2, "c": 3 }.keys().isdisjoint({ "d": 4, "e": 5, "f": 6}.keys())')
0.4637166199972853

第二快： set.isdisjoint()

示例：

set({"a": 1, "b": 2, "c": 3 }.keys()).isdisjoint(set({ "d": 4, "e": 5, "f": 6}.keys()))

时间:

>>> timeit.timeit('set({"a": 1, "b": 2, "c": 3 }.keys()).isdisjoint(set({ "d": 4, "e": 5, "f": 6}.keys()))')
0.774243315012427

第三快速方法：列表推导式和 all() 函数：

示例：

all(k not in {"a": 1, "b": 2, "c": 3 } for k in { "d": 4, "e": 5, "f": 6})

时间：

>>> timeit.timeit('all(k not in {"a": 1, "b": 2, "c": 3 } for k in { "d": 4, "e": 5, "f": 6})')
0.8577601349970791

第四快的方法：使用对称差异（^）和not()

示例：

not set({"a": 1, "b": 2, "c": 3 }.keys()) ^ set({ "d": 4, "e": 5, "f": 6}.keys())

时间：

>>> timeit.timeit('not set({"a": 1, "b": 2, "c": 3 }.keys()) ^ set({ "d": 4, "e": 5, "f": 6}.keys())')
0.9617313010094222

- Dom Weldon

---

这当然是指如果您只想查看是否共享了任何密钥。 - Dom Weldon

not bool(x) 就是 not x。使用 set 转换浪费时间且不会短路。^ 不会短路。 - Veedrac

好观点@Veedrac - 尽管我有时会写bool()来帮助可读性，但删除它可以显著加快脚本的速度。不过，我不确定你所说的关于短路^的意思是什么？据我所知，此操作仅适用于集合... - Dom Weldon

你的第三个测试不是有效的比较。你应该使用字典而不是列表，k not in list 的运行时间是线性的，而 k not in dict 的运行时间是常数级别的。因此它高度依赖于输入大小。 - Johannes

谢谢 - 我已经编辑过了，以反映出所有方法的公平时间。 - Dom Weldon

Answer 4

仅使用位运算符：

变量

dict1 = {"a":1, "b":2}
dict2 = {"a":4, "c":2}

联合

dict1.keys() | dict2.keys()
# {'b', 'a', 'c'}

交集

dict1.keys() & dict2.keys()
# {'a'}

不相交

dict1.keys() ^ dict2.keys()
# {'b', 'c'}

然后设置一个条件：

"different" if dict1.keys() ^ dict2.keys() else "equal"

在布尔条件中，空集合()返回"False"

- Franz Kurt