How to reverse a dictionary that has repeated values

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)

Answers:

Thank you for visiting the Q&A section on Magenaut. Please note that all the answers may not help you solve the issue immediately. So please treat them as advisements. If you found the post helpful (or not), leave a comment & I’ll get back to you as soon as possible.

Method 1

Using collections.defaultdict:

from collections import defaultdict

reversed_dict = defaultdict(list)
for key, value in mydict.items():
    reversed_dict[value].append(key)

Method 2

reversed_dict = {}
for key, value in mydict.items():
    reversed_dict.setdefault(value, [])
    reversed_dict[value].append(key)

Method 3

for k,v in dict.iteritems():
    try:
      reversed_dict[v].append(k)
    except KeyError:
       reversed_dict[v]=[k]

Method 4

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)

Method 5

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)}

Method 6

reversed_dict = collections.defaultdict(list)
for key, value in dict_.iteritems():
  reversed_dict[value].append(key)

Method 7

def reverse_dict(mydict):
    v={}
    for x,y in mydict.items():
        if  y not in v:
            v[y]=[x]
        else:
            v[y].append(x)
    return v

print(reverse_dict(mydict))

All methods was sourced from stackoverflow.com or stackexchange.com, is licensed under cc by-sa 2.5, cc by-sa 3.0 and cc by-sa 4.0