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

There are probably many pitfalls to a generic approach like this, but if your dictionaries are of mostly primitives, and not huge, you can do something like this:

Assuming your data looks something like this:

networks = [
        {'address': '192.168.1.1'},
        {'address': '127.0.0.1'},
    ]

missing = [
        {'address': '127.0.0.1'}
    ]

You can turn the lists of dictionaries into lists tuples (which are hashable)

def make_hashable(d):
    return (frozenset(x.iteritems()) for x in d)

networks_hashable = make_hashable(networks)
missing_hashable = make_hashable(missing)

Then subtract

diff = set(networks_hashable).difference(missing_hashable)

Now you have a list of tuples

print list(diff)

or, convert back to dictionaries

print [dict(x) for x in diff]

Update

I've changed the definition of make_hashable based on @gnibbler's comment.

Answer 2

No, in general it's quite difficult to do efficiently. You don't have to solve the general case though, just for your particular data structure which you haven't elaborated to us.

For example, if your dict keys are all intor str it's considerably easier than if the keys are complex numbers etc.

EDIT: Since you've now told us your data structure, I can tell you that a simple way is to convert the dicts to nametuples.

Note: You can't just convert the dict to a tuple with tuple(dict.items()) because the order of the keys can be different from one dict to the next

>>> d = dict(ssid="ssid", bssid="bssid", channel=1, flags="flags", found="True")
>>> networks_list = [d, ]
>>> from collections import namedtuple
>>> NT = namedtuple("my_struct", d.keys())
>>> set(NT(**i) for i in networks_list)
set([my_struct(found='True', flags='flags', channel=1, bssid='bssid', ssid='ssid')])

Answer 3

What if you try something as simple as:

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

(BTW: I've changed your variable named to lst here; binding some results to the name "list" is probably a bad idea given that Python supports a list() function. It's not a keyword, so it won't throw an exception, but you might trip over it later when you write some code that tries to call the list() function later).