Removing key/value pairs in list of dicts

Question

I have a list of dicts that all have the same keys. If a key's value is None in all dicts then I want to remove them (A solution that creates a new dict is fine as well).

I'm concerned about my Big O complexity of 2n² (correct me if I'm wrong). Are there better solutions to what I have below?

dicts = [{'a': 1, 'b': None, 'c': 4},
         {'a': 2, 'b': None, 'c': 3},
         {'a': None, 'b': None, 'c': 3}]

expected = [{'a': 1, 'c': 4}, {'a': 2, 'c': 3}, {'a': None, 'c': 3}]

keys = dicts[0].keys()
keep_keys = []

for key in keys:
    vals = []
    for d in dicts:
        if d[key] is not None:
            vals.append(d[key])

    if len(vals) != 0:
        keep_keys.append(key)

for d in dicts:
    for k in d.keys():
        if k not in keep_keys:
            del d[k]

print dicts == expected

Answer 1

Any solution will have to read the values associated to each key of each dictionary; so you won't be able to drop under \$\mathcal{O}(n\times{}m)\$ where \$m\$ is the length of each dictionary. This is pretty much what you are doing, but the if k not in keep_keys call slows things a bit as it is \$\mathcal{O}(m)\$ when it could be \$\mathcal{O}(1)\$ by using a set or a dictionary.

If you change the keep_keys list into a set you simplify the logic a bit: as soon as you find a key whose value is not None you can add it into the set.

dicts = [{'a': 1, 'b': None, 'c': 4}, {'a': 2, 'b': None, 'c': 3}, {'a': None, 'b': None, 'c': 3}]
expected = [{'a': 1, 'c': 4}, {'a': 2, 'c': 3}, {'a': None, 'c': 3}]

keep_keys = set()

for d in dicts:
    for key, value in d.items():
        if value is not None:
            keep_keys.add(key)

remove_keys = set(d) - keep_keys

for d in dicts:
    for k in remove_keys:
        del d[k]

print dicts == expected

This code, as your original one, assume that there is at least one item in dicts; otherwise set(d) will generate an exception as the variable d is not defined yet.

---

But this code mixes the actual logic with some tests. You should wrap it in a function to ease reusability and put the testing code under an if __name__ == '__main__': clause:

def filter_nones(dictionaries):
    if not dictionaries:
        return

    keep_keys = set()

    for dict_ in dictionaries:
        for key, value in dict_.iteritems():
            if value is not None:
                keep_keys.add(key)

    remove_keys = set(dict_) - keep_keys

    for dict_ in dictionaries:
        for key in remove_keys:
            del dict_[key]


if __name__ == '__main__':
    dicts = [
            {'a': 1, 'b': None, 'c': 4},
            {'a': 2, 'b': None, 'c': 3},
            {'a': None, 'b': None, 'c': 3},
    ]
    expected = [
            {'a': 1, 'c': 4},
            {'a': 2, 'c': 3},
            {'a': None, 'c': 3},
    ]

    filter_nones(dicts)
    print dicts == expected