python - How to reverse a dictionary that has repeated values

12
votes

I have a dictionary with almost 100,000 (key, value) pairs and the majority of the keys map to the same values. For example:

mydict =  {'a': 1, 'c': 2, 'b': 1, 'e': 2, 'd': 3, 'h': 1, 'j': 3}

What I want to do, is to reverse the dictionary so that each value in mydict is going to be a key at the reverse_dict and is going to map to a list of all the mydict.keys() that used to map to that value in mydict. So based on the example above I would get:

reversed_dict = {1: ['a', 'b', 'h'], 2: ['c', 'e'] , 3: ['d', 'j']}

I came up with a solution that is very expensive and I want to hear any ideas for doing this more efficiently than this:

reversed_dict = {}
for value in mydict.values():
    reversed_dict[value] = []
    for key in mydict.keys():
        if mydict[key] == value:
            if key not in reversed_dict[value]: 
                reversed_dict[value].append(key)
6
pythondictionary

6 Answers

18
votes

Using collections.defaultdict:

from collections import defaultdict

reversed_dict = defaultdict(list)
for key, value in mydict.items():
    reversed_dict[value].append(key)
4
votes
reversed_dict = {}
for key, value in mydict.items():
    reversed_dict.setdefault(value, [])
    reversed_dict[value].append(key)
1
votes
for k,v in dict.iteritems():
    try:
      reversed_dict[v].append(k)
    except KeyError:
       reversed_dict[v]=[k]
1
votes

I think you're wasting a few cycles by replacing a key with the same key again and again...

reversed_dict = {}
for value in mydict.values():
    if value not in reversed_dict.keys(): #checking to be sure it hasn't been done.
        reversed_dict[value] = []
        for key in mydict.keys():
            if mydict[key] == value:
                if key not in reversed_dict[value]: reversed_dict[value].append(key)
1
votes

Using itertools.groupby:

from operator import itemgetter
from itertools import groupby

snd = itemgetter(1)

def sort_and_group(itr, f):
    return groupby(sorted(itr, key=f), f)

mydict =  {'a': 1, 'c': 2, 'b': 1, 'e': 2, 'd': 3, 'h': 1, 'j': 3}
reversed_dict = {number: [char for char,_ in v] 
                 for number, v in sort_and_group(mydict.items(), snd)}
0
votes
reversed_dict = collections.defaultdict(list)
for key, value in dict_.iteritems():
  reversed_dict[value].append(key)