5
\$\begingroup\$

I'm comparing two OrderedDict objects and I need to find added keys, removed keys, and keys that are present in both (the intersection). Sets are designed for exactly that sort of thing, so my initial attempt involved getting the keys, converting to sets and then comparing/intersecting appropriately. The trouble I ran into is that I need the order of the original keys to be preserved all the way through the process (hence the use of OrderedDict) and sets don't seem to do that. I did some googling about ordered sets in python3, but there don't appear to be any native solutions, and I don't really want to bring in another class/library for this one small computation. Instead, I came up with these lines of code:

def differences(a, b):
    added = []
    removed = []
    overlap = []
    for key in a.keys():
        if key in b:
            overlap.append(key)
        else:
            removed.append(key)

    for key in b.keys():
        if not key in a:
            added.append(key)

    return (added, removed, overlap)

I'm especially interested in hearing suggestions on different ways of tackling this problem, but I'm happy to hear any general suggestions.

Improve this question
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Since you are ehphasizing the importance of the keys' order, do you consider each member of pair of keys unchanged if the pairs order changed in the other dict? E.g do you consider the keys in {'a': True, 'b': False} and {'b': False, 'a': True} unchanged? If so, in which order should the keys occur in overlap? ['a', 'b'] or ['b', 'a']? \$\endgroup\$ – Richard Neumann Sep 22 '17 at 13:52
  • 1
    \$\begingroup\$ Thanks @RichardNeumann, that's an important point I hadn't considered, so I'm glad to store it away for later. Having given my particular use-case some thought though, the answer is that I only care about the order of new keys: when considering removed elements or elements that remain in both, the order no longer matters. \$\endgroup\$ – Conor Mancone Sep 22 '17 at 14:08
6
\$\begingroup\$

A few notes about your current approach:

  • there is no need to call .keys(), the default iteration over a dict would go over the keys:

    for key in a:
    # ...

for key in b:
    # ...
  • I think doing if key not in a: is a bit more readable than if not key in a:

  • added can be defined using a list comprehension:

    added = [key for key in b if key not in a]

  • we can define the initial list values using unpacking:

    added, removed, overlap = [], [], []

  • you can remove parenthesis around the return tuple value:

    return added, removed, overlap
  • adding a docstring would really make sense here especially considering the return type and format which can be explicitly mentioned there

  • we can even go a bit further and return a collections.namedtuple() instead of a regular tuple:

    from collections import namedtuple

Difference = namedtuple('Difference', ['added', 'removed', 'overlap'])

  • and we can add type hints as well

At the end we can get something along these lines:

from collections import namedtuple
from typing import MutableMapping, NamedTuple


Difference = namedtuple('Difference', ['added', 'removed', 'overlap'])


def differences(a: MutableMapping, b: MutableMapping) -> NamedTuple:
    """
    Calculates the difference between two OrderedDicts.

    :param a: OrderedDict
    :param b: OrderedDict
    :return: Difference
    """
    removed, overlap = [], []

    for key in a:
        if key in b:
            overlap.append(key)
        else:
            removed.append(key)

    added = [key for key in b if key not in a]

    return Difference(added=added, removed=removed, overlap=overlap)

Or, if we gonna apply Mathias's suggestion to loop over the a twice we can shorten that to:

from collections import namedtuple
from typing import MutableMapping, NamedTuple


Difference = namedtuple('Difference', ['added', 'removed', 'overlap'])


def differences(a: MutableMapping, b: MutableMapping) -> NamedTuple:
    """
    Calculates the difference between two OrderedDicts.

    :param a: OrderedDict
    :param b: OrderedDict
    :return: Difference
    """

    return Difference(added=[key for key in b if key not in a],
                      removed=[key for key in a if key not in b],
                      overlap=[key for key in a if key in b])
Improve this answer
\$\endgroup\$
2
  • 2
    \$\begingroup\$ You could extend the list-comprehension to the 3 lists: overlap = [key for key in a if key in b] and removed = [key for key in a if key not in b]. This makes 2 iterations over a rather than 1 but removes the need for the append and the looping in Python (loops will be performed in C). \$\endgroup\$ – 301_Moved_Permanently Sep 22 '17 at 13:47
  • 2
    \$\begingroup\$ You know, I skipped out on the list comprehensions the first time around because I didn't want to have to do a third loop (and was avoiding the "unbalancedness" of one list comprehension and one loop). However, looking at it all the options, I find having the three list comprehensions next to eachother much easier to read and understand. I dropped it in and of course all tests pass beautifully. Thanks for taking the time to really break it down! \$\endgroup\$ – Conor Mancone Sep 22 '17 at 14:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.