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.

  • 3
    You also have some spurious indentation (again). Try pasting your whole code, selecting it and pressing Ctrl+K (or use the {} button in the toolbar). – Graipher Dec 19 '17 at 11:40
  • 2
    the comprehension is not actually doing what it is intended to, aka creating a list Yes it does. You're just not using it. – Eric Duminil Dec 19 '17 at 17:47
  • 1
    Do you care about the order of the strings? If not, you might want to use sets. – Eric Duminil Dec 19 '17 at 20:10
  • @EricDuminil 1) Yeah, indeed, I meant that the comprehension is not assigned. And I am specially wary of unassigned things left into the wild. I may not know much about programming, but I heard that it is not especially good to do this, even if there is a garbage collector (some languages have a reputation for memory leaks). 2) I generally don't especially care about the order of the strings, and depending on the implementation I actually use sets or orderedsets, in particular because they avoid duplication so spare memory. But I took a general case for simplication. Thanks for the suggestion – Ando Jurai Dec 20 '17 at 8:33
  • 1
    @AndoJurai: One huge advantage of sets is that element in set is O(1) while element in list is O(n). – Eric Duminil Dec 20 '17 at 9:54
up vote 13 down vote accepted

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:

enter image description here

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)

enter image description here

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.

  • 3
    Bonus points for not abusing list comprehensions for side effects. There's a limit to their usefulness. The proposed solution is much more readable, although do you have any indication what the performance hit will be on large datasets? They tend to get large in bioinformatics, easily a couple of thousand entries in a dictionary. – Mast Dec 19 '17 at 11:56
  • 2
    @Mast I added some timings including for some large dicts (with 100k keys and lists of length up to 100k, as well). It is actually faster than the list comprehension. – Graipher Dec 19 '17 at 13:37
  • 2
    Very counter intuitive (intuition being actually the saying in the docs that comprehension are optimized compared to loops. This is a bit jarring). Awesome work! – Ando Jurai Dec 19 '17 at 14:24
  • 3
    you don't need zip([...], [...]), zip() will be happy to receive generators, so zip((x for x in ...), (x for x in ...)). – wvxvw Dec 19 '17 at 14:40
  • 4
    It doesn't seem so surprising to me. A list comprehension might be faster than creating a list with a for loop. In the OP case, the list comprehension creates a useless list full of Nones. And this list isn't created at all with the for loop. – Eric Duminil Dec 19 '17 at 17:41

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?

  • 1
    Well in my particular case at work, it was merely reversing the association to reprocess all newly formed groups. So it's a one time use. To mitigate the memory imprint I can get rid of the original dictionary. But your design is very interesting for specific searches, actually, thanks a lot. – Ando Jurai Dec 19 '17 at 13:41
  • 1
    Your first statement about dictionaries needing O(n log(n)) is completely false. In python they need O(n) space. – Oscar Smith Dec 19 '17 at 17:55
  • 1
    @OscarSmith yeah, my bad, I should've written O(n + log(n)). Which is kind of O(n), but it's not really helpful to say that in this context. – wvxvw Dec 20 '17 at 6:41
  • 1
    Where are you getting this log(n) from? Python dictionaries use quadratic probing, so the size is 1/.7 times the number of entries. – Oscar Smith Dec 20 '17 at 19:03
  • 1
    @OscarSmith you probably mean CPython, i.e. the official implementation of Python. Python language definition doesn't require any specific memory usage. But n + log(n) is also a good way to describe what happens there. You are counting the wrong thing though: you are looking at the length of an array that stores the bucket, but it's not the amount of storage required (obviously, you'd need at least n cells to store n items). You are also forgetting that since the hash-table is dynamic, it needs to be re-allocated sometimes, to prevent re-allocation dynmaic arrays, often use extra memory. – wvxvw Dec 21 '17 at 6:56

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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