5
\$\begingroup\$

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 2n2 (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
\$\endgroup\$
6
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ This remove_keys = set(d) - keep_keys threw me off for a bit. At first, I thought, "of course, use sets." I think it's noteworthy that instantiating a set with a dict creates a set of that dict's keys. I never knew that! I would have thought set(d.keys()) would have been necessary. How is that possible? \$\endgroup\$ – Mox Sep 8 '17 at 13:37
  • 1
    \$\begingroup\$ @Mox This is due to the semantics of a dict. Since you can query 'some key' in dict_ (for instance), this means that, implicitly, a dict is a collection of keys. Check iter(d) in the documentation \$\endgroup\$ – 301_Moved_Permanently Sep 8 '17 at 13:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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