CODEWITHSUNDEEP
pythonlistsortingmax
Kadaj13
Kadaj13

Reputation: 1541

finding the indices of the most maximum values in a list effectively

Suppose we have a list: [1, 3.5, -1, 7, 10, 20, 5, 17, 31, -5]

I want to write a function that returns the indices of the first 3 maximum values in order.

For example in this case the results would be: [8, 5, 7]

I know one way is to write nested-loops, however, can there be any other effective way to achieve this?

Upvotes: 2

Views: 170

Answers (8)

MagnusO_O
MagnusO_O

Reputation: 1283

While all 6 answers (right now available after ~24h) are effective in providing the requested result I was wondering which solution is the most efficient one.

I used timeit for the comparison (only runtime, no memory usage, 5k runs with an increased input list - the same for all).

Results in increasing order:

consecutive_max: 2.604 s
heapq_oneStep:   3.052 s
np_argsort:      3.234 s
lambda_unnamed:  6.182 s
heapq_nlargest:  4.522 s
lambda_function: 9.960 s
zip_sort:        15.402 s

Code of the evaluation:

import timeit

timeit_runs = 5_000


# heapq_oneStep by Mechanic Pic
# https://stackoverflow.com/a/73568080/11815313
def heapq_oneStep():
    timeit_setup_heapq_oneStep = '''
import heapq
import random
random.seed(42)
    
integer_list = random.sample(range(-10_000, 10_000), 10_000) 
lst = [x/100 for x in integer_list] 
    '''
    testcode_heapq_oneStep = ''' 
heapq.nlargest(3, range(len(lst)), lst.__getitem__)
    '''
    
    return timeit.timeit(stmt=testcode_heapq_oneStep, 
                         setup=timeit_setup_heapq_oneStep, number = timeit_runs)


# heapq_nlargest by Stef
# https://stackoverflow.com/a/73567876/11815313
def heapq_nlargest():
    timeit_setup_heapq_nlargest = '''
from heapq import nlargest
from operator import itemgetter
import random
random.seed(42)
    
integer_list = random.sample(range(-10_000, 10_000), 10_000) 
lst = [x/100 for x in integer_list] 
    '''
    testcode_heapq_nlargest = ''' 
[i for i,_ in nlargest(3, enumerate(lst), itemgetter(1))]
    '''
    
    return timeit.timeit(stmt=testcode_heapq_nlargest, 
                         setup=timeit_setup_heapq_nlargest, number = timeit_runs)
 

# zip_sort by Guy
# https://stackoverflow.com/a/73567874/11815313
def zip_sort():

    timeit_setup_zip_sort = '''
import random
random.seed(42)
    
integer_list = random.sample(range(-10_000, 10_000), 10_000) 
lst = [x/100 for x in integer_list] 
    '''
    testcode_zip_sort = ''' 
[i for _, i in sorted(zip(lst, range(len(lst))), reverse=True)[:3]]
    '''
    
    return timeit.timeit(stmt=testcode_zip_sort, 
                         setup=timeit_setup_zip_sort, number = timeit_runs)
    

# lambda_function by Mehmaam
# https://stackoverflow.com/a/73568027/11815313 
def lambda_function():

    timeit_setup_lambda_function = '''
import random
random.seed(42)
    
integer_list = random.sample(range(-10_000, 10_000), 10_000) 
lst = [x/100 for x in integer_list] 
    '''
    testcode_lambda_function = ''' 
def sort_index(lst, rev=True):
    index = range(len(lst))
    s = sorted(index, reverse=rev, key=lambda i: lst[i])
    return s
sort_index(lst)[:3]
    '''
    
    return timeit.timeit(stmt=testcode_lambda_function, 
                         setup=timeit_setup_lambda_function, number = timeit_runs)


# lambda_unnamed by uozcan12
# https://stackoverflow.com/a/73569339/11815313 
def lambda_unnamed():
    timeit_setup_lambda_unnamed = '''
import random
random.seed(42)
    
integer_list = random.sample(range(-10_000, 10_000), 10_000) 
lst = [x/100 for x in integer_list] 
    '''
    testcode_lambda_unnamed = ''' 
list(map(lambda x: lst.index(x), sorted(lst, reverse=True)[:3] ))
    '''
    
    return timeit.timeit(stmt=testcode_lambda_unnamed, 
                         setup=timeit_setup_lambda_unnamed, number = timeit_runs)

# np_argsort by MagnusO_O
# https://stackoverflow.com/a/73567884/11815313 
def np_argsort():

    timeit_setup_np_argsort = '''
import numpy as np
import random
random.seed(42)

integer_list = random.sample(range(-10_000, 10_000), 10_000) 
lst = [x/100 for x in integer_list] 
lst_nparr = np.array(lst)
    '''
    testcode_np_argsort = ''' 
lst_nparr_max3 = np.argsort(lst_nparr)[::-1][0:3]
lst_nparr_max3.tolist()
    '''
    
    return timeit.timeit(stmt=testcode_np_argsort, 
                         setup=timeit_setup_np_argsort, number = timeit_runs)


# consecutive_max by cards
def consecutive_max():
    timeit_setup_consecutive_max = '''
import random
random.seed(42)
integer_list = random.sample(range(-10_000, 10_000), 10_000)
lst = [x/100 for x in integer_list]
    '''
    testcode_consecutive_max = '''
lst_cp = lst.copy()
indeces_max = []
for _ in range(3):
    m = max(lst_cp)
    indeces_max.append(lst.index(m))
    lst_cp.remove(m)
    '''
    return timeit.timeit(stmt=testcode_consecutive_max,
                         setup=timeit_setup_consecutive_max, number = timeit_runs)

time_heapq_oneStep = heapq_oneStep()
time_heapq_nlargest = heapq_nlargest()
time_zip_sort = zip_sort()
time_lambda_function = lambda_function()
time_lambda_unnamed = lambda_unnamed()
time_np_argsort = np_argsort()
time_consecutive_max = consecutive_max()

print(f'''consecutive_max:  {time_consecutive_max:.3f} s''')
print(f'''np_argsort:      {time_np_argsort:.3f} s''')
print(f'''heapq_oneStep:   {time_heapq_oneStep:.3f} s''')
print(f'''lambda_unnamed:  {time_lambda_unnamed:.3f} s''')
print(f'''heapq_nlargest:  {time_heapq_nlargest:.3f} s''')
print(f'''lambda_function: {time_lambda_function:.3f} s''')
print(f'''zip_sort:        {time_zip_sort:.3f} s''')

Upvotes: 0

cards
cards

Reputation: 4975

Using consecutive max to a copy of the list.

lst = [1, 3.5, -1, 7, 10, 20, 5, 17, 31, -5]
lst_cp = lst.copy()

indeces_max = []
for _ in range(3):
    m = max(lst_cp)
    indeces_max.append(lst.index(m))
    lst_cp.remove(m)
del lst_cp # just to remember that is not needed

print(indeces_max)

Upvotes: 1

uozcan12
uozcan12

Reputation: 427

l = [1, 3.5, -1, 7, 10, 20, 5, 17, 31, -5]
list(map(lambda x: l.index(x), sorted(l, reverse=True)[:3] )) # [8, 5, 7]

Upvotes: 1

MagnusO_O
MagnusO_O

Reputation: 1283

You could use np.argsort:

import numpy as np
ar = [1, 3.5, -1, 7, 10, 20, 5, 17, 31, -5]
ar_argsort = np.argsort(ar)
reversed_argsort = ar_argsort[::-1]
indices_3_max = reversed_argsort[0:3]
print(indices_3_max)

Result:

[8 5 7]

Concise version of above in one line:

ar_argsort = np.argsort(ar)[::-1][0:3]

Upvotes: 0

Mechanic Pig
Mechanic Pig

Reputation: 7736

This can generate the result in one step, but the less elegant dunder method is used as the key:

>>> lst = [1, 3.5, -1, 7, 10, 20, 5, 17, 31, -5]
>>> heapq.nlargest(3, range(len(lst)), lst.__getitem__)
[8, 5, 7]

Upvotes: 2

Mehmaam
Mehmaam

Reputation: 573

lambda function do this things easier.

Code:

def sort_index(lst, rev=True):
    index = range(len(lst))
    s = sorted(index, reverse=rev, key=lambda i: lst[i])
    return s
score = [1, 3.5, -1, 7, 10, 20, 5, 17, 31, -5]
sort_index(score)[:3]

Result:

[8, 5, 7]

Upvotes: 1

Stef
Stef

Reputation: 15505

Use heapq.nlargest to find the n largest values.

from heapq import nlargest
from operator import itemgetter

l = [1, 3.5, -1, 7, 10, 20, 5, 17, 31, -5]

indices_of_3_largest = [i for i,_ in nlargest(3, enumerate(l), itemgetter(1))]

print(indices_of_3_largest)
# [8, 5, 7]

Upvotes: 3

Guy
Guy

Reputation: 50864

zip the list with the indices, sort it, and take the first 3 values

lst = [1, 3.5, -1, 7, 10, 20, 5, 17, 31, -5]
indices = [i for _, i in sorted(zip(lst, range(len(lst))), reverse=True)[:3]]
print(indices) # [8, 5, 7]

Upvotes: 2

Related Questions