3
\$\begingroup\$

I want to find the intersection of two lists of dicts.

Note that equality—i.e.: what is to appear in the intersection—is given by which keys they must have equal. See the obj_equal_on function.

def obj_equal_on(obj0, obj1, keys):
    for key in keys:
        if obj0.get(key, False) != obj1.get(key, None):
            return False
    return True


def l_of_d_intersection(ld0, ld1, keys):
    """ Find intersection between two lists of dicts.
          At best, will return `ld0` in full. At worst: [].

    :param ld0 :type [DictType]
    :param ld1 :type [DictType]
    :param keys :type ListType

    :returns intersection of ld0 and ld1 where key is equal.
    """

    return [obj1 for obj0 in ld1 for obj1 in ld0
            if obj_equal_on(obj0, obj1, keys)]

Basic testing (self-contained for SE, usually I'd subclass unittest.TestCase):

def run_example(ld0, ld1, keys, expected_result):
    result = tuple(l_of_d_intersection(ld0, ld1, keys))
    assert result == expected_result, '{0} != {1}'.format(result,expected_result)


def main():
    run_example(
        ld0=[{'foo': 'bar', 'haz': 'more'},
             {'can': 'haz', 'more': 'haz'},
             {'foo': 'jar', 'more': 'fish'}],
        ld1=[{'foo': 'bar'},
             {'can': 'haz'},
             {'foo': 'foo'}],
        keys=('foo',),
        expected_result=({'foo': 'bar', 'haz': 'more'},)
    )

    run_example(
        ld0=[
            {'orange': 'black', 'blue': 'green', 'yellow': 'red'},
            {'blue': 'yellow'},
            {'orange': 'red', 'yellow': 'blue'}
        ],
        ld1=[
            {'orange': 'black', 'yellow': 'red'},
            {'blue': 'yellow'},
            {'orange': 'red', 'yellow': 'blue'}
        ],
        keys=('orange', 'yellow'),
        expected_result=({'orange': 'black', 'blue': 'green', 'yellow': 'red'},
                         {'orange': 'red', 'yellow': 'blue'})
    )

My example works, but my code is rather horribly inefficient.

\$\endgroup\$

3 Answers 3

2
\$\begingroup\$

Although a list comprehension is generally an efficient way to go about things, in this case it means you check every obj0 against every obj1, even if you've already found a match. To avoid that:

out = []
for obj0 in ld0:
    for obj1 in ld1:
        if obj_equal_on(obj0, obj1, keys):
            out.append(obj0)
            break
return out

Beyond that, you could consider using a custom immutable class rather than dictionaries, implementing __eq__ and __hash__ and using sets rather than lists to efficiently determine the intersection.

\$\endgroup\$
1
\$\begingroup\$

1. Bug

The intersection code duplicates elements of ld0 if more than one dictionary in ld1 compares equal to them. In this example, ld0 has two dictionaries, but the "intersection" has four!

>>> l0 = [{1:2}, {1:2, 3:4}]
>>> l1 = [{1:2}, {1:2}]
>>> l_of_d_intersection(l0, l1, [1])
[{1: 2}, {1: 2, 3: 4}, {1: 2}, {1: 2, 3: 4}]

2. Review

  1. In obj_equal_on, it would be better to put the keys argument first. That's because it's likely that the same keys will be used several times, and so putting this argument first makes it convenient to use with functools.partial:

    eq = partial(obj_equal_on, keys)
    

    Similarly for l_of_d_intersection.

  2. The arguments to this function need to be dictionaries (or more generally, mappings), so the names ought to reflect this.

  3. This line looks as if it will go wrong if the dictionaries have values False or None:

    obj0.get(key, False) != obj1.get(key, None):
    

    I guess the condition that you have in mind is that two dictionaries are equal if all keys are present in both dictionaries and the corresponding values are equal. In which case you need something like this:

    def dict_equal_on(keys, dict0, dict1):
        try:
            return all(dict0[key] == dict1[key] for key in keys)
        except KeyError:
            return False
    
  4. I don't like the name l_of_d_intersection: it's not easy to guess what the function might do, based on its name.

  5. This loop has unnecessarily confusing variable names:

    for obj0 in ld1 for obj1 in ld0
    
  6. The test cases can be made a bit more convenient to run using the unittest module.

3. Performance

If the two lists have \$m\$ and \$n\$ dictionaries respectively, and there are \$k\$ keys, then this algorithm is \$ \Omega(kmn) \$. Every pair of dictionaries has to be compared, and it takes \$ \Omega(k) \$ to compare a pair of dictionaries.

If the values in the dictionaries are hashable, then there's an \$O(k(m + n))\$ algorithm:

def lists_of_dicts_intersection_on(keys, list0, list1):
    """Return a list of the dictionaries in list0 that compare equal on
    keys to some dictionary in list1. The dictionaries must have
    hashable values.

    """
    def values(d):
        try:
            return tuple(d[k] for k in keys)
        except KeyError:
            return None
    values1 = set(v for v in map(values, list1) if v is not None)
    return [d for d in list0 if values(d) in values1]

If the values in the dictionaries are sortable, then there's an \$O(k(m + n \log n))\$ algorithm:

from bisect import bisect_left

def contains(a, x):
    """Return True if the sorted array a contains x."""
    i = bisect_left(a, x)
    return i != len(a) and a[i] == x

def lists_of_dicts_intersection_on(keys, list0, list1):
    """Return a list of the dictionaries in list0 that compare equal on
    keys to some dictionary in list1. The dictionaries must have
    sortable values.

    """
    def values(d):
        try:
            return tuple(d[k] for k in keys)
        except KeyError:
            return None
    values1 = sorted(v for v in map(values, list1) if v is not None)
    return [d for d in list0 if contains(values1, values(d))]
\$\endgroup\$
0
\$\begingroup\$

Experimenting with an alternative solution:

class hashabledict(dict):
    # From: http://stackoverflow.com/q/1151658
    def __key(self):
        return frozenset(self)

    def __hash__(self):
        return hash(self.__key())

    def __eq__(self, other):
        return self.__key() == other.__key()


def normalise(idx, obj, keys, obj_id):
    return hashabledict((k, namedtuple('Elem', 'idx id value')(idx,obj_id,v))
                        for k, v in obj.iteritems() if k in keys)


def l_of_d_intersection(ld0, ld1, keys):
    """ Find intersection between a list of dicts and a list of dicts/objects

    :param ld0 :type [DictType] or :type [AnyObject]
    :param ld1 :type [DictType]
    :param keys :type ListType

    :returns intersection of ld0 and ld1 where key is equal.
                 At best, will return `ld0` in full. At worst: [].
    """
    processed_ld0 = frozenset(
        ifilter(None,imap(lambda (idx, obj): normalise(idx,obj,keys,id(obj)),
                           enumerate(ld0))))

    processed_ld1 = frozenset(
        ifilter(None,imap(lambda (idx, obj): normalise(idx,obj,keys,id(obj)),
                           enumerate(ld1))))

    return [ld0[res.idx]
            for result in processed_ld0.intersection(processed_ld1)
            for res in result.values()]

It's working on the first example (with foo,) but not the second (with orange, yellow).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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