[Python] Python: efficient unpacking large dictionary with list of strings as values to list...

I have a large dictionary with lists of strings as values. These strings can be duplicated. I would like to convert this dictionary to a list of lists of keys. The goal is to correlate the keys of original dictionary to unique strings so that later I can easily pick up all the keys for any unique string in subsequent analysis.

A simulation function is as follows:

import cProfile
import time
import string
import random
import collections
import numpy as np
from typing import Dict, List, Set


def test_large_dict():
char_pool: str = string.ascii_uppercase
# simulate a large dictionary with 300,001 keys, 10,000 unique strings.
test_dict: Dict[int, List[str]] = collections.defaultdict(list)
num_keys: int = 300001
str_nums: np.ndarray = np.random.randint(10, 300, size=num_keys)
str_len: List[int] = np.random.randint(7, 30, size=10000).tolist()
rand_strs: List[str] = [
''.join(random.choice(char_pool) for _ in range(str_len))
for i in range(10000)
]
for i in range(1, num_keys):
# no. of strings in current value: str_nums)
test_dict = [random.choice(rand_strs) for _ in range(str_nums)]

# In original dictionary
print(f"1: {test_dict[1]}")
print(f"2: {test_dict[2]}")

t = time.time()
str_index: Dict[str, int] = {}
key_lists: List[Set[int]] = []
k: int = 0
for ix, str_list in test_dict.items():
for s in str_list:
if s in str_index:
g = str_index
key_lists[g].add(ix)
else:
str_index = k
key_lists.append({ix})
k += 1
print(f"Elapsed time for the conversion: {time.time() - t:.2f} seconds.")


if __name__ == '__main__':
cProfile.run("test_large_dict()", sort="tottime")


The test time:

Elapsed time for the conversion: 24.77 seconds.


Profiling results are:

355043899 function calls in 148.398 seconds

Ordered by: internal time

ncalls tottime percall cumtime percall filename:lineno(function)
46487731 37.495 0.000 109.065 0.000 random.py:341(choice)
46487731 35.055 0.000 56.797 0.000 random.py:242(_randbelow_with_getrandbits)
1 27.915 27.915 147.832 147.832 test_proteolysis.py:104(test_large_dict)
92975462 14.773 0.000 14.773 0.000 {built-in method builtins.len}
76097488 13.163 0.000 13.163 0.000 {method 'getrandbits' of '_random.Random' objects}
46297043 10.721 0.000 10.721 0.000 {method 'add' of 'set' objects}
46487731 8.579 0.000 8.579 0.000 {method 'bit_length' of 'int' objects}
1 0.566 0.566 148.398 148.398 <string>:1(<module>)
190688 0.076 0.000 0.476 0.000 test_proteolysis.py:112(<genexpr>)
10000 0.040 0.000 0.517 0.000 {method 'join' of 'str' objects}
2 0.005 0.003 0.005 0.003 {method 'randint' of 'numpy.random.mtrand.RandomState' objects}
10000 0.005 0.000 0.005 0.000 {method 'append' of 'list' objects}
3 0.005 0.002 0.005 0.002 {built-in method builtins.print}
1 0.000 0.000 0.000 0.000 {method 'tolist' of 'numpy.ndarray' objects}
2 0.000 0.000 0.000 0.000 {method 'reduce' of 'numpy.ufunc' objects}
1 0.000 0.000 148.398 148.398 {built-in method builtins.exec}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
2 0.000 0.000 0.000 0.000 fromnumeric.py:71(_wrapreduction)
2 0.000 0.000 0.000 0.000 fromnumeric.py:2979(prod)
2 0.000 0.000 0.000 0.000 {built-in method builtins.getattr}
2 0.000 0.000 0.000 0.000 {built-in method time.time}
3 0.000 0.000 0.000 0.000 {method 'items' of 'dict' objects}
2 0.000 0.000 0.000 0.000 fromnumeric.py:2974(_prod_dispatcher)


Lots of time were spent to unpack this large dictionary into lists. Any more efficient way to unpack the large dictionary? I'm also free to any data structure to achieve the goal. In the provided example, I generated a dict str_index and list key_lists. The keys of str_index are unique strings, and values are the indexes of lists in the key_lists, so that all keys in original large dictionary for ith unique string are put in ith list in key_lists, e.g., all keys for ith unique string sj are key_lists[str_index[sj]].

Continue reading...