Given dictionary with tuple keys, sort dictionary items by tuple product of keys.
Input : test_dict = {(2, 3) : 3, (6, 3) : 9, (8, 4): 10, (10, 4): 12}
Output : {(2, 3) : 3, (6, 3) : 9, (8, 4): 10, (10, 4): 12}
Explanation : 6 < 18 < 32 < 40, key products hence retains order.Input : test_dict = {(20, 3) : 3, (6, 3) : 9, (8, 4): 10, (10, 4): 12}
Output : {(6, 3) : 9, (8, 4): 10, (10, 4): 12, (20, 3) : 3, }
Explanation : 18 < 32 < 40 < 60, key products hence adjusts order.
Method #1 : Using dictionary comprehension + lambda + sorted()
This is one of the ways in which this task can be performed. In this, we perform sort() using sorted() and lambda function is used to compute product over which sort can be performed.
Python3
# Python3 code to demonstrate working of # Sort dictionary by Tuple Key Product# Using dictionary comprehension + sorted() + lambda# initializing dictionarytest_dict = {(5, 6) : 3, (2, 3) : 9, (8, 4): 10, (6, 4): 12}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# sorted() over lambda computed product # dictionary comprehension reassigs dictionary by order res = {key: test_dict[key] for key in sorted(test_dict.keys(), key = lambda ele: ele[1] * ele[0])}# printing result print("The sorted dictionary : " + str(res)) |
The original dictionary is : {(5, 6): 3, (2, 3): 9, (8, 4): 10, (6, 4): 12}
The sorted dictionary : {(2, 3): 9, (6, 4): 12, (5, 6): 3, (8, 4): 10}
Method #2 : Using dict() + sorted() + lambda
The combination of above functions can be used to solve this problem. In this, similar method is used as above method. The only difference being items arrangement done using dict() rather than dictionary comprehension after computing keys ordering .
Python3
# Python3 code to demonstrate working of # Sort dictionary by Tuple Key Product# Using dict() + sorted() + lambda# initializing dictionarytest_dict = {(5, 6) : 3, (2, 3) : 9, (8, 4): 10, (6, 4): 12}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# sorted() over lambda computed product # dict() used instead of dictionary comprehension for rearrangementres = dict(sorted(test_dict.items(), key = lambda ele: ele[0][1] * ele[0][0]))# printing result print("The sorted dictionary : " + str(res)) |
The original dictionary is : {(5, 6): 3, (2, 3): 9, (8, 4): 10, (6, 4): 12}
The sorted dictionary : {(2, 3): 9, (6, 4): 12, (5, 6): 3, (8, 4): 10}
Method #3: Using itemgetter function from the operator module
Step by Step Algorithm
- Import itemgetter module from operator
- Initialize the test_dict
- Sort the dictionary based on the product of keys using itemgetter
- Reassign the sorted dictionary back to the original dictionary
- Print the sorted dictionary
Python3
from operator import itemgetter# initializing dictionarytest_dict = {(5, 6) : 3, (2, 3) : 9, (8, 4): 10, (6, 4): 12}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# sorting the dictionary based on product of keys using itemgetterres = dict(sorted(test_dict.items(), key=itemgetter(0), reverse=False))# printing resultprint("The sorted dictionary : " + str(res)) |
The original dictionary is : {(5, 6): 3, (2, 3): 9, (8, 4): 10, (6, 4): 12}
The sorted dictionary : {(2, 3): 9, (5, 6): 3, (6, 4): 12, (8, 4): 10}
Complexity Analysis :
Time complexity: O(nlogn) where n is the number of items in the dictionary. The time complexity is mainly due to the sorting operation.
Space complexity: O(n), where n is the number of items in the dictionary. The space complexity is mainly due to the storage of the sorted dictionary.
Method #4: Using the heapq module’s heapify() and heappop() functions
- Import the heapq module to use its functions for sorting.
- Initialize the dictionary to be sorted.
- Print the original dictionary.
- Convert the dictionary to a list of tuples, with the key product as the first element of each tuple.
- Use heapq.heapify() to sort the list of tuples in place based on the first element of each tuple (i.e., the key product).
- Create a new dictionary from the sorted list of tuples, with the first element (i.e., the tuple key) as the key of each dictionary element and the second element (i.e., the dictionary value) as the value of each dictionary element.
- Print the sorted dictionary.
Python3
import heapq# initializing dictionarytest_dict = {(5, 6) : 3, (2, 3) : 9, (8, 4): 10, (6, 4): 12}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# convert dictionary to list of tuples and heapifytemp_list = [(k, v) for k, v in test_dict.items()]heapq.heapify(temp_list)# create new dictionary from sorted listres = dict(heapq.heappop(temp_list) for i in range(len(temp_list)))# printing result print("The sorted dictionary : " + str(res)) |
The original dictionary is : {(5, 6): 3, (2, 3): 9, (8, 4): 10, (6, 4): 12}
The sorted dictionary : {(2, 3): 9, (5, 6): 3, (6, 4): 12, (8, 4): 10}
The time complexity of this implementation is O(nlogn) because of the sorting operation
The space complexity is also O(n) because we are creating a new dictionary of the same size as the original dictionary.
