Python - Subtract a list of dicts from another

Question

I'm interested in comparing multiple lists, taking the difference and iterating through that.

Both are list of dicts that contain the following keys: 'ssid' - str, 'bssid' - str, 'channel' - int, 'flags' - list, 'found' - bool

I've tried:

 list = list(set(networks_list).difference(missing_networks))

But I receive the error:

unhashable type 'dict'

My data structure looks like this:

list: [{'found': False, 'flags': ['WPA2-PSK-CCMP', 'WPS', 'ESS'], 'ssid': 'SOHO_BROADCAST', 'bssid': '30:46:9a:9d:11:1a', 'channel': 1}, {'found': False, 'flags': ['WPA-EAP-TKIP', 'WPA2-EAP-CCMP', 'ESS'], 'ssid': 'Cisco 2.4ghz', 'bssid': '40:f4:ec:7f:3c:5a', 'channel': 11}, {'found': False, 'flags': ['WPA-EAP-TKIP', 'WPA2-EAP-CCMP', 'ESS'], 'ssid': 'Cisco 5.0ghz', 'bssid': '40:f4:ec:7f:3c:54', 'channel': 149}]

Missing networks is initially empty.

Is there a simple way of doing this?

Answer 1

This approach works:

>>> import random
>>> items = [{'ssid': 'foo%s' % i, 'bssid': 'bar%s' % i, 'channel': i, 'flags': 'abc%s' % i, 'found': random.choice([True, False])} for i in range(1, 11)]
>>> items1 = random.sample(items, 7)
>>> items2 = random.sample(items, 5)
>>> print "\n".join(map(str, items1))
{'found': True, 'flags': 'abc9', 'ssid': 'foo9', 'bssid': 'bar9', 'channel': 9}
{'found': True, 'flags': 'abc7', 'ssid': 'foo7', 'bssid': 'bar7', 'channel': 7}
{'found': False, 'flags': 'abc10', 'ssid': 'foo10', 'bssid': 'bar10', 'channel': 10}
{'found': True, 'flags': 'abc5', 'ssid': 'foo5', 'bssid': 'bar5', 'channel': 5}
{'found': False, 'flags': 'abc4', 'ssid': 'foo4', 'bssid': 'bar4', 'channel': 4}
{'found': True, 'flags': 'abc3', 'ssid': 'foo3', 'bssid': 'bar3', 'channel': 3}
{'found': True, 'flags': 'abc2', 'ssid': 'foo2', 'bssid': 'bar2', 'channel': 2}
>>> print "\n".join(map(str, items2))
{'found': True, 'flags': 'abc3', 'ssid': 'foo3', 'bssid': 'bar3', 'channel': 3}
{'found': True, 'flags': 'abc9', 'ssid': 'foo9', 'bssid': 'bar9', 'channel': 9}
{'found': False, 'flags': 'abc1', 'ssid': 'foo1', 'bssid': 'bar1', 'channel': 1}
{'found': False, 'flags': 'abc8', 'ssid': 'foo8', 'bssid': 'bar8', 'channel': 8}
{'found': True, 'flags': 'abc5', 'ssid': 'foo5', 'bssid': 'bar5', 'channel': 5}
>>> print "\n".join(map(str, [dict(itemset) for itemset in set([tuple(sorted(grp.items())) for grp in items1]).difference([tuple(sorted(grp.items())) for grp in items2])]))
{'found': False, 'flags': 'abc10', 'ssid': 'foo10', 'bssid': 'bar10', 'channel': 10}
{'found': False, 'flags': 'abc4', 'ssid': 'foo4', 'bssid': 'bar4', 'channel': 4}
{'found': True, 'flags': 'abc7', 'ssid': 'foo7', 'bssid': 'bar7', 'channel': 7}
{'found': True, 'flags': 'abc2', 'ssid': 'foo2', 'bssid': 'bar2', 'channel': 2}

Answer 2

Instead of making them list of dicts make them a list of objects which implement __eq__ and __hash__ and the code you provide should work

Answer 3

A dict is a mutable item. This means it has no constant hash value over the course of its life, and cannot be put into a set.

If you convert all the dicts to strings with the same function, they become hashable and you can use them in a set...

Answer 4

I'm going to go by Eric's answer here.

First, the problem at hand. Why is a dict unhashable? Simply put, because it's a mutable container. If you change the content of the dict, the hash changes. The same will happen for any other mutable container like lists. So, you have to use something that's immutable.

The simplest solution in my mind would be to use a wrapper class. Essentially, a class that has a single property being the dict you originally wanted. You can spice it up with whatever magic functions you want for comparisons.

So, if I have your original list of networks

network_list = [
{'found': False, 'flags': ['WPA2-PSK-CCMP', 'WPS', 'ESS'], 'ssid': 'SOHO_BROADCAST', 'bssid': '30:46:9a:9d:11:1a', 'channel': 1},
{'found': False, 'flags': ['WPA-EAP-TKIP', 'WPA2-EAP-CCMP', 'ESS'], 'ssid': 'Cisco 2.4ghz', 'bssid': '40:f4:ec:7f:3c:5a', 'channel': 11},
{'found': False, 'flags': ['WPA-EAP-TKIP', 'WPA2-EAP-CCMP', 'ESS'], 'ssid': 'Cisco 5.0ghz', 'bssid': '40:f4:ec:7f:3c:54', 'channel': 149}
]

I can easily apply a wrapper class.

class Wrapper(object):
    def __init__(self, **kwargs):
        for key, value in kwargs.items():
            setattr(self, key, value)

wrapped_networks = [Wrapper(**{'net_dict': network}) for network in network_list]

That way, the dictionary is stored and accessible through

wrapped_networks[0].net_dict # etc...

or whatever else you could possibly want to name it. Also, because of the way the class is implemented, you can use it to wrap whatever you want, even if there are multiple things per Wrapper!

What this does, as you might be well aware, is make is so what's actually getting hashed is the object, according to a unique id assigned to it at runtime. A little refactoring for your difference functions to work with these wrappers, and you should be well on your way (unless you come up with a better solution =D )

Answer 5

As mentioned earlier, dicts are mutable and therefor can't be operated by set() -- that's because there's no guarantee that once placed inside a set, a dict won't change and become equal to another existing element of the set, thus violating the set quality.

If you are only checking the dicts for equality, you can convert them to tuples, then use tuples in set() operations, then convert tuples in the resulting set back into dicts.

>>> d = {1:1, 2:2}
>>> t = tuple(d1.items())
>>> t
((1, 1), (2, 2))
>>> d_ = dict(t)
>>> d_
{1: 1, 2: 2}
>>> d == d_
True

Wrapping dicts into classes can be quite a bit more cumbersome, as you still have to solve to conversion from a dict to a immutable data type.

As you have lists inside your dicts, you have more work. The simplest is if you could just replace lists with tuples in the original dicts.

Assuming that's not feasible, your conversion process will have to be a function, as opposed to just calling tuple() and dict(), respectively. You'll need to conver lists to tuples first, then converts dicts with tuples instead of lists to tuples. For example:

>>> d = {'int1': 1, 'int2': 2, 'list1': ['a', 'b'], 'list2': ['x', 'y']}
>>> d_l = {}
>>> for key, value in d.iteritems():
...   if type(value) == list:
...     d_l[key] = tuple(value)
...   else:
...     d_l[key] = value
>>> d_l
{'int1': 1, 'int2': 2, 'list1': ('a', 'b'), 'list2': ('x', 'y')}
>>> d_ = tuple(d_l.iteritems())
>>> d_
(('int1', 1), ('int2', 2), ('list1', ('a', 'b')), ('list2', ('x', 'y')))

To convert back, you have two options. Either look at key values that you know correspond to lists (if your keys are known and don't change) or look at tuples where the second element is a tuple itself (of you don't store any tuples in the original dicts). If neither option applies, you have to write more complex conversion algorithms.

Answer 6

Use a list comprehension:

>>> l1 = [{1:1, 'a':2},{1:2, 'a':4},{1:5, 'a':'2'}]
>>> l2 = [{1:1, 'a':3},{1:2, 'a':4},{1:5, 'a':'t'}]
>>> l3 = [i for i in l1 if i not in l2]
>>> l3
[{'a': 2, 1: 1}, {'a': '2', 1: 5}]