0

I'm looking for an efficient way to find the intersection of two Python dictionaries where order matters, starting at the top. In other words, loop through the dictionaries and once their keys or values differ, stop. I think this is clearest with some examples.

  • The intersection of {a: 1, b: 0} and {a: 1, b: 1} is obviously {a: 1}.
  • The intersection of {a: 1, b: 0, c: 1} and {a: 1, c: 1, b: 0} is just {a: 1} since order matters.
  • The intersection of {a: 1, b: 0} and {b: 0, c: 1} is empty because they don't start on the same key.

I have the following function which works, but I'm wondering if there's an easier/faster way.

def find_ordered_intersection(d0, d1):
    d1keys = list(d1.keys())
    intersection = {}
    for i, (k, v) in enumerate(d0.items()):
        if (k == d1keys[i]) and (v == d1[k]):
            intersection.update({k:v})
        else:
            return intersection

p.s. I'm having a hard time succinctly describing my goal. If anyone has edits, please feel free.

martineau
  • 119,623
  • 25
  • 170
  • 301
dfried
  • 313
  • 2
  • 8
  • 1
    This problem might not be well-defined because dictionaries do not have a guaranteed order. – mkrieger1 Nov 09 '20 at 20:39
  • 1
    Is the code you have shown too slow? – mkrieger1 Nov 09 '20 at 20:40
  • But if you loop through them, they'll always have the same order, no? So my function above will work? – dfried Nov 09 '20 at 20:40
  • @mkrieger1 it's not terribly slow, I just thought there might be a faster or easier solution with set methods or something like that. If not, then that's a good answer too! – dfried Nov 09 '20 at 20:41
  • You also checking that the values are equal. Right? – Dani Mesejo Nov 09 '20 at 20:43
  • 1
    @mkrieger For versions of python 3.6+ the order of keys is [guaranteed](https://docs.python.org/3/whatsnew/3.6.html#new-dict-implementation) and no longer just an implementation detail. – DragonBobZ Nov 09 '20 at 20:44
  • @mkrieger1: The guaranteed order of dictionaries nowadays is insertion order. – martineau Nov 09 '20 at 20:46
  • @DaniMesejo yes checking values (that's what `v == d1[k]` should do) – dfried Nov 09 '20 at 20:48
  • @DragonBobZ yes I know. But there wasn't a Python version specified in the question and it isn't universally true. Plus, what I think I also meant was that dictionaries still aren't sequence types, meaning for example that they don't support indexing or slicing, and, [as far as I understand it](https://stackoverflow.com/questions/17217225/what-does-the-operator-actually-do-on-a-python-dictionary), differently ordered dictionaries might still compare equal, which poses the interesting problem that `a == b` might not imply `f(a) == f(b)`. I'm not sure if all this is relevant here. – mkrieger1 Nov 09 '20 at 21:05
  • 1
    @mkrieger Your caveat and my response are all good information to have in this comment chain for the asker. – DragonBobZ Nov 09 '20 at 21:08

3 Answers3

0

If you are ok with relying in the insertion order, you could do the following, using takewhile and dict:

from itertools import takewhile


def intersection(a, b):
    return dict(kb for ka, kb in takewhile(lambda x: x[0] == x[1], zip(a.items(), b.items())))


print(intersection({'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'c': 1, 'b': 0}))
print(intersection({'a': 1, 'b': 0, 'c': 1}, {'a': 1, 'b': 1, 'c': 1}))
print(intersection({'a': 1, 'b': 0}, {'a': 1, 'b': 1}))
print(intersection({'a': 1, 'b': 0, }, {'b': 0, 'c': 1}))

Output

{'a': 1}
{'a': 1}
{'a': 1}
{}
Dani Mesejo
  • 61,499
  • 6
  • 49
  • 76
0

This should be easier to understand.

def find_ordered_intersection(d0, d1):
    d0keys = list(d0.keys())
    d1keys = list(d1.keys())
    size = min(len(d0), len(d1))

    dic = {}

    for i in range(size):
        key0 = d0keys[i]
        key1 = d1keys[i]
        if key0 != key1:
            break
        elif d0[key0] != d1[key1]:
            break
        else:
            dic[key0] = d0[key0]
    return dic
Frank
  • 1,215
  • 12
  • 24
0
def find_ordered_intersection(d0, d1):
    intersection = {tpl[0][0]: tpl[0][1] for tpl in zip(d0.items(), d1.items()) if (tpl[0][0] == tpl[1][0]) and (tpl[0][1] == tpl[1][1])}
    return intersection
 
#The intersection of {a: 1, b: 0} and {a: 1, b: 1} is obviously {a: 1}.
#The intersection of {a: 1, b: 0, c: 1} and {a: 1, c: 1, b: 0} is just {a: 1} since order matters.
#The intersection of {a: 1, b: 0} and {b: 0, c: 1} is empty because they don't start on the same key.

d0 = {'a': 1, 'b': 0} 
d1 = {'a': 1, 'b': 1}
print(find_ordered_intersection(d0, d1))

d2 = {'a': 1, 'b': 0, 'c': 1}
d3 = {'a': 1, 'c': 1, 'b': 0}
print(find_ordered_intersection(d2, d3))

d4 = {'a': 1, 'b': 0}
d5 = {'b': 0, 'c': 1} 
print(find_ordered_intersection(d4, d5))

Output:

{'a': 1}
{'a': 1}
{}
Aaj Kaal
  • 1,205
  • 1
  • 9
  • 8