1

I have two dictionaries:

dict1 = agent_id:agent_email
dict2 = user_id:agent_id

I want to create a dictionary:

agent_id: list of user_ids associated with agent_id

How do I search dict2 for each agent_id from dict1 and return the associated key? I've been told that creating a list of keys and then searching is very slow. Is there a faster way?

The question suggested as a dupe does not tell me what I'd like to know. I'm trying to search all the values without creating a separate list. Also, once I have the value, how to I get the corresponding key?

EDIT All the information I need is in dict2. The question is how do I get at it. Each agent_id is associated with multiple user_id's. I want to create a dict that looks like this:

{agent_id_1:(user_id_1, user_id_2, user_id_45), agent_id_2:(user_id_987), agent_id_3:(user_id_10, user_id_67)...etc}

based on one of the answers, I'm looking into created a 'reverse dict'. I'm don't really understand this yet, as the values in dict2 (the agent_ids) are not unique. Is this the way to go?

DBWeinstein
  • 8,605
  • 31
  • 73
  • 118
  • 1
    possible duplicate of [get key by value in dictionary](http://stackoverflow.com/questions/8023306/get-key-by-value-in-dictionary) – Jesse Webb Jun 01 '15 at 05:07
  • 1
    How large are both dicts? (i.e. does the intended optimization it even matter? which is the larger dict?) How often is lookup performed? – dhke Jun 01 '15 at 05:10
  • @dhke the dicts are large. over 10,000 each and growing. speed matters. – DBWeinstein Jun 01 '15 at 13:50

4 Answers4

2

If the values are unique (i.e. no repetitions, which I assume is so, from 'agent_id'), the easiest way is to maintain two dictionaries. The original one, and a second, where the keys are the values of the first, and its values are the indices of the first. This way lookup would be near-instant (only the time of the creation of the hash).

In case of repetitions in the values, little can be done but search. Again, it would be still faster if you maintain a tree structure with the values, and point back to the keys.

jcoppens
  • 5,306
  • 6
  • 27
  • 47
  • In case of repetitions, you could use a `value: set(key)` dict for the reverse lookup. – amon Jun 01 '15 at 05:44
0

Let's start giving your dicts somewhat more descriptive names:

agent_id_to_email = agent_id: agent_email
user_to_agent_id = user_id: agent_id

Now, you want all user_ids from user_to_agent_id such that the agent_id is in a valid key in agent_id_to_email.

Straightforward iterate and lookup approach

Time complexity: Approximately linear in the size of user_to_agent_id.

for user_id in (user_id
    for user_id, agent_id in user_to_agent_id.iteritems()
    if agent_id in agent_id_to_email
):
     # do something

This is time-linear in len(user_to_agent_id) since we iterate over all its items. The agent_id in agent_id_to_email lookup should be approximately constant (dicts are hash tables) or at worst O(n x ln(n)). Since both dictionaries seem to be roughly the same size, it does not matter if n is over user_to_agent_id or agent_id_to_email. If agent_id_to_email is small in comparison to user_to_agent_id the reverse dictionary approach becomes more efficient, but as it stands that is as good as it gets.

Note also that set intersection seems to have an O(N) computational lower bound.

dhke
  • 15,008
  • 2
  • 39
  • 56
0

Using an answer from this SO question [link], i've gone with the following code:

def dbwInvUserIdAgentId(dbwUserWithAgentD):
""" return dict of agents: user_id; only agents with 
    users and only one use per agent
    so this inverts the dict
    arguments:
            dbwUserWithAgentD =    dict of pure user_id: agent: id"""

    return {v:k for k, v in dbwUserWithAgentD.iteritems()}


def dbwAgentUserIdsListD(dbwInvUserIdAgentId, dbwUserWithAgentD):
    return_dict = {}
    for agent_id in dbwInvUserIdAgentId:
        temp_list = []
        for k, v in dbwUserWithAgentD.iteritems():
            if agent_id == v:
                temp_list.append(k)
        return_dict[agent_id] = temp_list
    return return_dict

can someone with a cs background tell me how efficient this is? Is there a better way? I'm having a hell of a time trying to apply what the other answers are saying. I think I probably didn't ask the question all that well.

Regardless, thank you very much for the answers.

Community
  • 1
  • 1
DBWeinstein
  • 8,605
  • 31
  • 73
  • 118
  • Assume the dictionary lookups are constant time, which leaves you with only the time for the for loops. `dbwAgentUserIdsListD()` nests two loops, hence O(n²). Note also that `dbwInvUserIdAgentId()` fails when the original mapping isn't 1:1. – dhke Jun 01 '15 at 17:38
  • @dhke thank you very much for all your attention to this question. The dict being inverted (dbwUserWithAgentD) is definitely not 1:1. Each agent_id has many user_id associated with it. So, I'm treating the inversion as filter of sorts, so the resulting inversion will have a complete list of agent_ids that I can then use to create my desired dict. Hope that makes sense. Would love to know where I'm going wrong. – DBWeinstein Jun 01 '15 at 17:47
  • Hmm. `dbwInvUserIdAgentId` has *last key wins* semantics. Put `{'a': 1, 'b': 1}` in and you get either `{1: 'b'}` or `{1: 'a'}` depending on the iteration order of the original dict (which is undefined). So yes, you get a filter, but one with undefined behaviour. – dhke Jun 02 '15 at 07:24
-1

Try this. 

 for key1, val1 in dict1.iteritems():
        for key2,val2 in dict2.iteritems():
            if key1 == val2:
                print key2
Harsha Biyani
  • 7,049
  • 9
  • 37
  • 61
  • 1
    The good thing about this solution is that it consumes no extra space. Unfortunately, it has O(n²) time complexity – it becomes unreasonably slow for large dicts. If we first build a reverse dict (O(n) space and time complexity), getting a list of all matches only costs O(n) time complexity, giving us O(n) overall. I would estimate the reverse dict approach to be faster even when the dicts only contain 20 elements each or so. – amon Jun 01 '15 at 05:50
  • @amon what is a reverse dict approach? – DBWeinstein Jun 01 '15 at 13:56
  • 1
    Reverse mapping concept: map = { 'a': 1, 'b':2 } reverse_map = { 1: 'a', 2: 'b' } This can be get as reverse_map = {val: key for key, val in map.items()} – Harsha Biyani Jun 01 '15 at 18:36