Нахождение индексов нескольких наименьших чисел в списке. python

#python #list #python_27

Как наиболее оптимальным образом найти индексы двух наименьших чисел в списке?
    

Ответы

Ответ 1

Быстрый способ получить значения:

from heapq import nsmallest

nsmallest(2, some_list)


И их индексы:

a, b = map(some_list.index, nsmallest(2, some_list))


Ответ 2

Чтобы индексы двух наименьших элементов в списке найти:

import heapq

i, j = heapq.nsmallest(2, range(len(lst)), key=lst.__getitem__)


Если только сами элементы нужны:

a, b = heapq.nsmallest(2, lst)


Ответ 3

Еще одно решение с использованием - array.argpartition() из модуля Numpy (гораздо
быстрее работает для больших списков):

import numpy as np

In [45]: a = np.random.randint(0, 100, size=10)

In [46]: a
Out[46]: array([ 8, 51, 63, 31, 21,  9, 28, 19, 70, 57])

In [47]: a.argpartition(2)[:2]
Out[47]: array([0, 5], dtype=int64)


дает такой же результат как и argsort()

In [48]: a.argsort()[:2]
Out[48]: array([0, 5], dtype=int64)


Сравнение производительности для массива из 1.000.000 элемтов:

In [32]: a = np.random.randint(0, 1000, size=10**6)

In [33]: lst = a.tolist()

In [34]: a.shape
Out[34]: (1000000,)

In [35]: len(lst)
Out[35]: 1000000

# Кирилл Малышев
In [51]: %timeit sorted(enumerate(lst), key=lambda x:x[1])[:2]
1.68 s ± 10.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# Alban
In [49]: %timeit smallest(lst, 2)
860 ms ± 5.44 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# jfs    
In [37]: %timeit nsmallest(2, range(len(lst)), key=lst.__getitem__)
212 ms ± 4.86 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

# avtomato    
In [38]: %timeit a.argsort()[:2]
193 ms ± 10.9 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# Sergey Gornostaev
In [36]: %timeit map(lst.index, nsmallest(2, lst))
75.4 ms ± 2.35 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

# MaxU    
In [39]: %timeit a.argpartition(2)[:2]
10.8 ms ± 37.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)


Ответ 4

Весьма эффективны массивы в NumPy

import numpy as np

x = np.array([2, 1, 4, 3, 5])
first, second, *other = np.argsort(x)
print(first, second)


Ответ 5

In [71]: smallest = lambda array, n: [array.index(x) for x in sorted(array)[:n]]


Более понятный вариант:

n [83]: def smallest(array, n):
    ...:     result = []
    ...:     for i in sorted(array)[:n]:
    ...:         result.append(array.index(i))
    ...:     return result


Результат в обоих случаях:

In [84]: smallest([5, 4, 3, 2, 1], 2)
Out[84]: [4, 3]


Ответ 6

sorted(enumerate([20, 60, 40, 10, 50, 30]), key=lambda x:x[1])


Вывод:

[(3, 10), (0, 20), (5, 30), (2, 40), (4, 50), (1, 60)]


Так получаем конкретно индексы:

[i[0] for i in sorted(enumerate([20, 60, 40, 10, 50, 30]), key=lambda x:x[1])]


P.S. Совершенно не претендую на эффективность