Python – Key Lists Summations

Sometimes, while working with Python Dictionaries, we can have problem in which we need to perform the replace of key with values with sum of all keys in values. This can have application in many domains that include data computations, such as Machine Learning. Let’s discuss certain ways in which this task can be performed. 

Method #1 : Using sum() + loop This is one of the ways in which this task can be performed. In this, we perform the summation using sum, and iteration to each key is done in brute way using loop. 

  Method #2 : Using dictionary comprehension + sum() This is yet another way in which this task can be performed. This is similar to above method, just a shorthand version. 

 Method #3 : Using reduce

Approach

using the reduce() function from the functools module.

Algorithm

1. The dictionary d contains keys and values where each value is a list of integers.
2. A new dictionary summation_keys is created where each key in d is mapped to the sum of the corresponding list of integers.
3. This is achieved by using the reduce function from the functools module to sum the values in each list of integers, and then creating a new dictionary with the sums.

{'gfg': 18, 'is': 19, 'best': 15}

Time complexity: O(m), The time complexity of the reduce function is O(n), where n is the number of elements in the list being reduced.In this case, the list being reduced has length 3, so the time complexity of each call to reduce is O(3) = O(1). The loop that iterates over each item in the dictionary has a time complexity of O(m), where m is the number of key-value pairs in the dictionary. 

Auxiliary Space: O(N), where N is the number of elements in the dictionary d. This is because the code creates a new dictionary summation_keys that has the same number of elements as d. The memory required to store the new dictionary is proportional to the size of d. The code also uses the reduce() function to sum the values in each list of d. The reduce() function works by iteratively applying a function to the elements of a list, so it does not create any new data structures that would increase the space complexity. Therefore, the space complexity of the reduce() function is O(1).

METHOD 4:Using defaultdict.

APPROACH:

The function takes a dictionary with keys as strings and values as lists of integers. It returns a new dictionary where the keys are the same as the original dictionary, but the values are the sum of the corresponding lists.

ALGORITHM:

1.Define a function dict_key_sum_6 which takes in a dictionary as input.
2.Create a defaultdict with integer values as the default value.
3.Iterate over each key-value pair in the input dictionary.
4.Iterate over each value in the list associated with the current key.
5.Add the current value to the running total for the current key in the defaultdict.
6.Convert the defaultdict to a regular dictionary and return it as the result.

{'gfg': 18, 'is': 19, 'best': 15}

Time complexity:

The function iterates over all the keys and values in the original dictionary, so the time complexity is O(n*m), where n is the number of keys in the dictionary and m is the maximum length of the lists.

Auxiliary Space:

The function uses a defaultdict to store the result, which has a space complexity of O(n), where n is the number of keys in the dictionary. Additionally, the function creates a new dictionary to return the result, which has a space complexity of O(n). Overall, the space complexity is O(n).

METHOD 5:Using  heapq:

Algorithm:

1. Initialize a dictionary ‘test_dict’ with some key-value pairs.
2. Create an empty dictionary ‘res’ to store the sum of the values of the keys.
3. Iterate through the items in the dictionary using a for loop and calculate the sum of the values of each key.
4. Use the heapq module to get the n largest values from the list of values of each key, where n is the length of the list of values of each key.
5. Store the sum of the n largest values of the key in the ‘res’ dictionary with the corresponding key.
6. Print the resulting dictionary ‘res’.

The original dictionary is : {'gfg': [4, 6, 8], 'is': [9, 8, 2], 'best': [10, 3, 2]}
The summation keys are : {'gfg': 18, 'is': 19, 'best': 15}

Time Complexity:
The time complexity of this code is O(N log N), where N is the length of the largest list of values in the dictionary. This is because heapq.nlargest() takes O(N log N) time to find the n largest elements in a list.

Space Complexity:
The space complexity of this code is O(N), where N is the number of keys in the dictionary. This is because we are creating a new dictionary ‘res’ to store the sum of the values of each key. The space used by heapq.nlargest() is negligible compared to the size of the dictionary.

METHOD 6: Using  numpy:

Algorithm:

1. Initialise a list of dictionaries called ini_dict.
2. Define a numpy array called arr by iterating through each dictionary in ini_dict and creating a new list
3. containing the values associated with the keys ‘a’, ‘b’, and ‘c’. If a key is missing, the value is set to 0. This list is then added to arr.
4. Use the numpy sum function to sum the values in arr along the first axis (i.e., the rows).
5. Assign the summed values to a new dictionary called result, with the keys ‘a’, ‘b’, and ‘c’.
6. Print the resulting dictionary.

Output:

Resultant dictionary using numpy:  {'a': 140, 'b': 88, 'c': 100}

Time complexity:

The time complexity of this algorithm is O(nm), where n is the number of dictionaries in ini_dict and m is the number of keys in each dictionary. The reason for this is that we need to iterate through each dictionary in ini_dict, and for each dictionary, we need to iterate through each key in the list [‘a’, ‘b’, ‘c’]. The time complexity of the numpy sum function is O(nm) as well, since it needs to iterate through all the elements in the array.

Space complexity:

The space complexity of this algorithm is O(nm), since we are creating a new 2D numpy array arr that has n rows and m columns. We are also creating a new dictionary result that contains m key-value pairs. However, the space required for ini_dict and the temporary lists used during the creation of arr are negligible in comparison.

Method #7 : Using nested for loops

Approach

1. Initiate a for loop to traverse over keys of dictionary
2. Initiate another for loop to traverse through value list of each key and sum them
3. Create a new dictionary res outside of inner for loop with keys same as keys of test_dict and values  as value list sum
4. Display res

The original dictionary is : {'gfg': [4, 6, 8], 'is': [9, 8, 2], 'best': [10, 3, 2]}
The summation keys are : {'gfg': 18, 'is': 19, 'best': 15}

Time complexity:

The time complexity of this algorithm is O(nm), where n is the number of dictionaries in ini_dict and m is the number of keys in each dictionary. The reason for this is that we need to iterate through each dictionary in ini_dict, and for each dictionary, we need to iterate through each key in the list [‘a’, ‘b’, ‘c’]. 

Space complexity:

The space complexity of this algorithm is O(nm), since we are creating a new dictionary result that contains m key-value pairs. However, the space required for ini_dict and the temporary lists used during the creation of arr are negligible in comparison.