Sometimes, while working with data, we can have a problem in which we have records and we require to find the highest N scores from it. This kind of application is popular in web development domain. Let’s discuss certain ways in which this problem can be solved.
Method #1 : Using sorted() + lambda The combination of above functionality can be used to perform this particular task. In this, we just employ sorted function with reverse flag true, and print the top N elements using list slicing.
Python3
# Python3 code to demonstrate working of# Get Top N elements from Records# Using sorted() + lambda# Initializing listtest_list = [('Manjeet', 10), ('Akshat', 4), ('Akash', 2), ('Nikhil', 8)]# Initializing NN = 2# printing original listprint("The original list is : " + str(test_list))# Get Top N elements from Records# Using sorted() + lambdares = sorted(test_list, key = lambda x: x[1], reverse = True)[:N]# printing resultprint("The top N records are : " + str(res)) |
The original list is : [('Manjeet', 10), ('Akshat', 4), ('Akash', 2), ('Nikhil', 8)]
The top N records are : [('Manjeet', 10), ('Nikhil', 8)]
Time Complexity: O(n*nlogn) where n is the number of elements in the list “test_list”. list comprehension + inbuilt functions performs n*nlogn number of operations.
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list
Method #2 : Using sorted() + itemgetter() The combination of above functions can also be used to perform this particular task. In this, the task performed by lambda function is performed by itemgetter() is used to get the index in tuple which has to be included in calculations.
Python3
# Python3 code to demonstrate working of# Get Top N elements from Records# Using sorted() + itemgetter()from operator import itemgetter# Initializing listtest_list = [('Manjeet', 10), ('Akshat', 4), ('Akash', 2), ('Nikhil', 8)]# Initializing NN = 2# printing original listprint("The original list is : " + str(test_list))# Get Top N elements from Records# Using sorted() + itemgetter()res = sorted(test_list, key = itemgetter(1), reverse = True)[:N]# printing resultprint("The top N records are : " + str(res)) |
The original list is : [('Manjeet', 10), ('Akshat', 4), ('Akash', 2), ('Nikhil', 8)]
The top N records are : [('Manjeet', 10), ('Nikhil', 8)]
Time Complexity: O(nlogn), where n is the length of the list test_list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list
Method #3 : Using heapq.nlargest()
This approach uses the heapq library’s nlargest() function, which returns the top N elements from an iterable. This approach is more efficient than the previous two, as it uses a heap data structure to keep track of the largest elements.
Python3
import heapq# Initializing listtest_list = [('Manjeet', 10), ('Akshat', 4), ('Akash', 2), ('Nikhil', 8)]# Initializing NN = 2# printing original listprint("The original list is : " + str(test_list))# Get Top N elements from Records# Using heapq.nlargest()res = heapq.nlargest(N, test_list, key = lambda x: x[1])# printing resultprint("The top N records are : " + str(res))#This code is contributed by Edula Vinay Kumar Reddy |
The original list is : [('Manjeet', 10), ('Akshat', 4), ('Akash', 2), ('Nikhil', 8)]
The top N records are : [('Manjeet', 10), ('Nikhil', 8)]
Time complexity: O(n log n) as it uses a heap data structure which is logarithmic in nature
Auxiliary space: O(n) as it stores the top N elements in memory.
Method #4: Using a dictionary to map the second element of each tuple to the corresponding tuple, and then using a loop to get the top N elements
- Create an empty dictionary to store the tuples.
- Loop through the tuples in the list and add them to the dictionary, with the second element of the tuple as the key and the tuple itself as the value.
- Get the keys of the dictionary in descending order by sorting them.
- Loop through the first N keys in the sorted keys list and append the corresponding tuple to a result list.
- Print the result list.
Python3
# Initializing listtest_list = [('Manjeet', 10), ('Akshat', 4), ('Akash', 2), ('Nikhil', 8)]# Initializing NN = 2# creating a dictionary that maps the second element of each tuple to the corresponding tupledict_list = {t[1]: t for t in test_list}# getting the keys in descending orderkeys = sorted(dict_list.keys(), reverse=True)# getting the top N tuplesres = []for i in range(N): res.append(dict_list[keys[i]])# printing the resultprint("The top N records are : " + str(res)) |
The top N records are : [('Manjeet', 10), ('Nikhil', 8)]
Time complexity: O(n log n) due to the sorting operation,
Auxiliary space: O(n) since we’re creating a dictionary to store the tuples.
