Pythonic way to group a list using a dictionary that has lists as values

Question

I'm looking for a Pythonic way or more efficient way to solve this problem. I have a dictionary which has sets as values (duplicates allowed across keys). Given a list I must create a dictionary which maps each category to the element using the key from the master dictionary. I'll give an example to illustrate.

Master Dictionary

{
    "KeyA": ['Aron', 'Ranom Value', 'Abhishek'],
    "KeyB": ['Ball', 'Foo', 'Bar', 'Badge', 'Dog'],
    "KeyZ": ['Random Value', 'Foo', 'Bar']
}

Input

['Foo', 'Bar', 'Dog', 'Aron']

Output

{
    "KeyA": ['Aron'],
    "KeyB": ['Bar', 'Foo', 'Dog'],
    "KeyZ": ['Foo', 'Bar']
}

My Current Thoughts

Invert individual items in the sets as keys and then do a lookup.

{
     'Aron'         : ['KeyA'],
     'Foo'          : ['KeyB', 'KeyZ'],
     'Bar'          : ['KeyB', 'KeyZ'],
     'Random Value' : ['KeyA', 'KeyZ']
}

I'd initialise the inverted dictionary by going through every item in every set. Approx time to create such a dictionary is O(n). Look for an item in the list in the inverted dictionary so created. Say the value Bar. Create a new dictionary using the information 'Bar': ['KeyB', 'KeyZ']. Resultant dictionary would be {'KeyB': ['Bar'], 'KeyZ': ['Bar']}. For the next item I'd have to do some bookkeeping on the existing dictionary like key exists or not, if yes then append to the existing list and so on.

Use the in operator on the set mapped (check for membership) to every key

The master dictionary and input list are going to be pretty small most of the times. (less than 500 unique items in all the sets together). So I could check for membership in the set returned by each key and create a dictionary. This is obviously less efficient but works for most cases.

I have a few more manipulations that are similar to the example given above. I don't want to do manual bookkeeping for all of them because they are error prone and slower than inbuilt functions.

What I need?

• Better approaches (faster algorithm)
• Inbuilt functions in itertools because these are faster
• 3rd Party Library
• Some esoteric comprehensions that a normal Python user wouldn't think of?

Answer 1

How about you convert the list to a set before you start converting? Set-lookups are faster than linear search in lists.

input_set = set(input)

Once you have it, you can use regular dict-comprehension, in my opinion:

output = {key: [x for x in value if x in input_set] for key, value in master_dict.items()}

Result:

output == {'KeyB': ['Foo', 'Bar', 'Dog'], 'KeyA': ['Aron'], 'KeyZ': ['Foo', 'Bar']}

Answer 2

one way is using intersection in python as follows:

x={
    "KeyA": ['Aron', 'Ranom Value', 'Abhishek'],
    "KeyB": ['Ball', 'Foo', 'Bar', 'Badge', 'Dog'],
    "KeyZ": ['Random Value', 'Foo', 'Bar']
   }
items = ['Foo', 'Bar', 'Dog', 'Aron']

{k:  set(items).intersection(set(v)) for k, v in x.items()}

Answer 3

How about with defaultdict and list comprehension.

from collections import defaultdict

result = defaultdict(list)

d = {
    "KeyA": ['Aron', 'Ranom Value', 'Abhishek'],
    "KeyB": ['Ball', 'Foo', 'Bar', 'Badge', 'Dog'],
    "KeyZ": ['Random Value', 'Foo', 'Bar']
   }
items = ['Foo', 'Bar', 'Dog', 'Aron']

[result[k].append(e) for k,v in d.items() for e in v if e in items]

print(result) # defaultdict(<type 'list'>, {'KeyB': ['Foo', 'Bar', 'Dog'], 'KeyA': ['Aron'], 'KeyZ': ['Foo', 'Bar']})

print(dict(result)) # {'KeyB': ['Foo', 'Bar', 'Dog'], 'KeyA': ['Aron'], 'KeyZ': ['Foo', 'Bar']}

Answer 4

Another Posssible Approach:

One way to possibly speed up the search time for checking if a value exists in input_set is to use binary search, which is O(logn).

Here is some example code which also uses the convienient collections.defaultdict:

from collections import defaultdict

master = {
          "KeyA": ['Aron', 'Ranom Value', 'Abhishek'],
          "KeyB": ['Ball', 'Foo', 'Bar', 'Badge', 'Dog'],
          "KeyZ": ['Random Value', 'Foo', 'Bar']
         }    

input_set = ['Foo', 'Bar', 'Dog', 'Aron']

sorted_list = sorted(input_set)

d = defaultdict(list)
for key, value in master.items():
    for v in value:
        if binary_search(sorted_list, v):
            d[key].append(v)

print(d)

Which Outputs:

defaultdict(<class 'list'>, {'KeyA': ['Aron'], 'KeyB': ['Foo', 'Bar', 'Dog'], 'KeyZ': ['Foo', 'Bar']})

Where binary_search() is defined below:

def binary_search(item_list,item):
    first = 0
    last = len(item_list)-1

    while first <= last:
        mid = (first + last)//2
        if item_list[mid] == item :
            return True
        elif item < item_list[mid]:
            last = mid - 1
        else:
            first = mid + 1 
    return False

The above code does seem like reinventing the wheel. You can have a look at the bisect module which provides some ways to call binary search without having to write your own function.

Note: In order to use binary search, you also need to sort the values before hand, which is O(nlogn). I'm not entirely sure how much impact this will have, you'd have to run some tests with another approach to see the difference.

Additionally, as @SuperSaiyan posted, converting input_set to a set is the most efficient approach, because set lookup O(1) in the best case, and O(n) in the worst case(rare).

Answer 5

The OP proposed a reverse dictionary. It is arguably still pythonic, so here is how one can be implemented.

Given

import collections as ct


master_dict = {
    "KeyA": ['Aron', 'Random Value', 'Abhishek'],
    "KeyB": ['Ball', 'Foo', 'Bar', 'Badge', 'Dog'],
    "KeyZ": ['Random Value', 'Foo', 'Bar']
}

input_list = ['Foo', 'Bar', 'Dog', 'Aron']

Code

We use a collections.defaultdict to ease the creation of list values.

reverse_dict = ct.defaultdict(list)
for k, v in master_dict.items():
    for item in v:
        reverse_dict[item].append(k)
reverse_dict

Output

defaultdict(list,
            {'Abhishek': ['KeyA'],
             'Aron': ['KeyA'],
             'Badge': ['KeyB'],
             'Ball': ['KeyB'],
             'Bar': ['KeyB', 'KeyZ'],
             'Dog': ['KeyB'],
             'Foo': ['KeyB', 'KeyZ'],
             'Random Value': ['KeyA', 'KeyZ']})

Now that the inputs can be searched by key, lookups are faster than searching each list of strings. We build the final dictionary from an input list of lookup values.

final_dict = ct.defaultdict(list)
for v in input_list:
    for k in reverse_dict[v]:
        final_dict[k].append(v)

final_dict

Output

defaultdict(list,
            {'KeyA': ['Aron'],
             'KeyB': ['Foo', 'Bar', 'Dog'],
             'KeyZ': ['Foo', 'Bar']})

@SuperSaiyan proposed rebuilding lists for each key of the master dictionary by searching the set of the input list. This is a brilliant and superior approach for this particular application.