Finding added keys, removed keys, and unchanged keys in ordereddict

Question

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.

Answer 1

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])