CODEWITHSUNDEEP
pythondictionaryset-intersectiondisjoint-sets
Johannes
Johannes

Reputation: 3388

Check if two dictionaries are disjoint

Is there an easier/faster way to find out if two dictionaries are disjoint than calculating their intersection?

For the intersection I found this answer, so the disjoint-test would look like this:

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

However I think this is inefficient since it always calculates the whole intersection (no short-circuit quit).

Any better ideas?

Upvotes: 3

Views: 2072

Answers (4)

Franz Gastring
Franz Gastring

Reputation: 1130

Using only bit operation: variables

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

union

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

intersection

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

disjoint

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

Then set a condition:

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

An empty set() return "False" in boolean conditions

Upvotes: 1

Dom Weldon
Dom Weldon

Reputation: 1738

Edited to display methods and timings only

Since the OP asked about the fastest method to perform this operation, I've ranked the ones under discussion according to a (I hope) fair test on my machine. The aim is to find if the keys of a dictionary are disjoint, and it seems the dict_keys.isdisjoint() method wins out over other set or list operations.

However, as mentioned in other answers, this will vary considerably depending on the size of the relative dictionaries and whether or not they are disjoint.

These tests are only for two disjoint dictionaries of equal (small) size.

Fastest: dict_keys.isdisjoint()

Example:

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

Timing: 

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

Second Fastest: set.isdisjoint()

Example:

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

Timing:

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

Third Fastest: List Comp and all():

Example:

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

Timing:

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

Fourth Fastest: Symmetric Difference (^) with not()

Example:

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

Timing:

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

Upvotes: 4

Veedrac
Veedrac

Reputation: 60147

Don't convert to a set; a dict_keys object already supports isdisjoint.

d1.keys().isdisjoint(d2)

Upvotes: 10

AChampion
AChampion

Reputation: 30258

Are you looking for something like:

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

Or:

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

Both will short-circuit.

Upvotes: 4

Related Questions