Invert a dictionary to a dictionary of lists

Question

I have a dictionary whose keys are related to list of values, but any value may be related to many keys, hence be contained in various lists-attached-keys.

To highlight such relation; I build (in Python 3.6.1) the reverse dictionary using this:

   from collections import defaultdict
   #defaultdict is a dict that you set up to output a datatype as default, instead of throwing a KeyError exception, when a key not contained into it is called, it outputs the default datatype and the corresponding key is created on the fly and kept.
   reversed_dict =defaultdict(list)
   primary_dict ={"abc":[1,2,3], "cde":[3,5,7],"efg":[4,2,1,7]}
   #in the call of default dict, you must input a callable
   [reversed_dict[term].append(key) for key, innerset in primary_dict.items() for term in innerset]
   #append should be used instead of extend, as keys are strings, and extend would result in their breakdown

   #desired output for reversed_dict:
   #defaultdict(list,
   #     {1: ['abc', 'efg'],
   #      2: ['abc', 'efg'],
   #      3: ['abc', 'cde'],
   #      4: ['efg'],
   #      5: ['cde'],
   #      7: ['cde', 'efg']})

The code is very simple, and efficient. My question is more about using the list comprehension to get the loading of the dict done, while it is not assigned to anything. Can't this cause any sort of problem? Shouldn't I better assign the comprehension and then delete it?

I am not very much used to "leaving in the air" something in Python. So I wonder if it is not "ugly", or problematic. I feel like it is bad because the comprehension is not actually doing what it is intended to, aka creating a list, I am only using its related feature of mimicking a for loop for it, because it is more efficient and readable than such loop.

What do you think?
I have been using such pattern for a long time now, but I was never completely satisfied with it, I only kept it because the other way I found were too convoluted to do this, or not using only one step.
About the context, it is difficult to say because I very often have to use such practice. I am in bioinformatics, so I often get associations between a key (say a gene or protein) and a list (of biological effects, related drugs and so on). Sometimes I use dataframes, but actually I find groupby not very convenient, as to get the related info you have to handle indexes (granted, you can set you keys as index and drop the column, but it is many operations, plus you have an index as output and this comes with its own kind of hassle.

Answer 1

You are right, you should not use a list comprehension just for its side-effects. It is not very readable and only confuses the reader of the code.

Instead, just make it for loops. And put it into a function, so it is re-usable:

from collections import defaultdict

def reverse_dict_of_lists(d):
    reversed_dict = defaultdict(list)
    for key, values in d.items():
        for value in values:
            reversed_dict[value].append(key)
    return reversed_dict

if __name__ == "__main__":
    d = {"abc": [1, 2, 3], "cde": [3, 5, 7], "efg": [4, 2, 1, 7]}
    print(reverse_dict_of_lists(d))
    # defaultdict(<type 'list'>, {1: ['abc', 'efg'], 2: ['abc', 'efg'], 3: ['cde', 'abc'], 4: ['efg'], 5: ['cde'], 7: ['cde', 'efg']})

This might take a very small performance hit (it doesn't, see below), but this should be negligible compared to actually being able to understand what the code does.

---

Here are some timings on my machine. First I generate a list of some randomly filled dictionaries:

import random

def generate_dicts(dict_length, step=1):
    return [{i: [random.randrange(1, 100) for _ in range(j)]
             for i, j in zip(
                 [random.randrange(1, n_keys) for _ in range(n_keys)],
                 [random.randrange(1, 100) for _ in range(n_keys)])}
            for n_keys in range(2, dict_length + 2, step)]

This will generate dictionaries of the form {i: [...]}, where there are an increasing number of keys in the dictionary and also the length of the lists increases (but is random).

Plotting the time it takes to reverse the dictionary for dict_length = 100000, step = 1000:

And, with a slightly more realistic sample dict, which does not overwrite the keys and therefore shows the quadratic behavior of the double loop:

import numpy as np

def generate_dicts(n_keys_values):
    return ({i: [random.randrange(1, 100) for _ in range(random.randrange(1, n_keys))] for i in range(n_keys)} for n_keys in n_keys_values)

n_keys_values = np.logspace(1, 4.5, num=20, dtype=int)

This is on Ubuntu 17.04, Python 3.6.3, IPython 6.2.1, Intel i7-4710MQ (8) @ 3.500GHz.

You can see that the loop based approach is actually slightly faster in both cases :). The reason being, as Eric Duminil put it succinctly in the comments:

A list comprehension might be faster than creating a list with a for loop. In [this] case, the list comprehension creates a useless list full of Nones. And this list isn't created at all with the for loop.

Answer 2

Another concern you may raise is: does it make sense to preprocess all the keys in the source dictionary? Dictionaries typically require storage on the order of O(n + log(n)) of the number of keys they store. Since your replica dictionary is going to have more keys than the source, it may require noticeably more memory to store. But what if you really need to make only few lookups, but memory footprint is important?

I'd consider creating a view of your dictionary. It won't be as efficient as pre-computing the dictionary in terms of speed, but it will allow to access the data without allocating much more memory. Example follows:

import functools


class ReverseDict:

    def __init__(self, source):
        self.source = source

    @functools.lru_cache(maxsize=256)
    def __getitem__(self, key):
        return list(self.get(key))

    def get(self, key):
        for k, v in self.source.items():
            if key in v:
                yield k

test:

>>> d = ReverseDict({"abc": [1, 2, 3], "cde": [3, 5, 7], "efg": [4, 2, 1, 7]})
>>> d[1]
['abc', 'efg']
>>> d[10]
[]

Depending on the memory vs speed requirements, this may also cut down on searches, since you'll be able to short-circuit them by using get() method. However, were you to pre-compute the dictionary specifically for search, then you would certainly want to sort the values in such a dictionary, so that you could use binary search later. Obviously, 256 was chosen arbitrarily. You would be in a better position to estimate the cache size.

---

Another, totally unrelated idea, certainly a shot in the dark: are you after searching inside this dictionary? If so, there are some other data-structures with better memory/speed characteristics, depending on your particular use. Perhaps if numeric values in your example can be interpreted as weights or some sort of edges between the keys, some sort of search tree would do a better job?