How can I find dict keys for matching values in two dicts?
<p>I have two dictionaries mapping IDs to values. For simplicity, lets say those are the dictionaries:</p>

<pre><code>d_source = {'a': 1, 'b': 2, 'c': 3, '3': 3}
d_target = {'A': 1, 'B': 2, 'C': 3, '1': 1}
</code></pre>

<p>As named, the dictionaries are not symmetrical.
I would like to get a dictionary of <em>keys</em> from dictionaries <code>d_source</code> and <code>d_target</code> whose values match. The resulting dictionary would have <code>d_source</code> keys as its own keys, and <code>d_target</code> keys as that keys value (in either a <code>list</code>, <code>tuple</code> or <code>set</code> format).</p>

<p>This would be The expected returned value for the above example should be the following list:</p>

<pre><code>{'a': ('1', 'A'),
 'b': ('B',),
 'c': ('C',),
 '3': ('C',)}
</code></pre>

<p>There are two somewhat <a href="http://stackoverflow.com/questions/21631951/find-matching-key-value-pairs-of-two-dictionaries">similar</a> <a href="http://stackoverflow.com/questions/11615041/how-to-find-match-items-from-two-lists">questions</a>, but those solutions can't be easily applied to my question.</p>

<p>Some characteristics of the data:</p>

<ol>
<li>Source would usually be smaller than target. Having roughly few thousand sources (tops) and a magnitude more targets.</li>
<li>Duplicates in the same dict (both <code>d_source</code> and <code>d_target</code>) are not too likely on values.</li>
<li>matches are expected to be found for (a rough estimate) not more than 50% than <code>d_source</code> items.</li>
<li>All keys are integers.</li>
</ol>

<p>What is the best (performance wise) solution to this problem?
Modeling data into other datatypes for improved performance is totally ok, even when using third party libraries (i'm thinking <a href="http://www.numpy.org/" rel="nofollow">numpy</a>)</p>

<p>All answers have <code>O(n^2)</code> efficiency which isn't very good so I thought of answering myself.</p>

<p>I use <code>2(source_len) + 2(dict_count)(dict_len)</code> memory and I have <code>O(2n)</code> efficiency which is the best you can get here I believe.</p>

<p>Here you go:</p>

<pre><code>from collections import defaultdict

d_source = {'a': 1, 'b': 2, 'c': 3, '3': 3}
d_target = {'A': 1, 'B': 2, 'C': 3, '1': 1}

def merge_dicts(source_dict, *rest):
    flipped_rest = defaultdict(list)
    for d in rest:
        while d:
            k, v = d.popitem()
            flipped_rest[v].append(k)
    return {k: tuple(flipped_rest.get(v, ())) for k, v in source_dict.items()}

new_dict = merge_dicts(d_source, d_target)
</code></pre>

<p>By the way, I'm using a tuple in order not to link the resulting lists together.</p>

<hr>

<p>As you've added specifications for the data, here's a closer matching solution:</p>

<pre><code>d_source = {'a': 1, 'b': 2, 'c': 3, '3': 3}
d_target = {'A': 1, 'B': 2, 'C': 3, '1': 1}

def second_merge_dicts(source_dict, *rest):
    """Optimized for ~50% source match due to if statement addition.

    Also uses less memory.
    """
    unique_values = set(source_dict.values())
    flipped_rest = defaultdict(list)
    for d in rest:
        while d:
            k, v = d.popitem()
            if v in unique_values:
                flipped_rest[v].append(k)
    return {k: tuple(flipped_rest.get(v, ())) for k, v in source_dict.items()}

new_dict = second_merge_dicts(d_source, d_target)
</code></pre>

python dictionary optimization