2

У меня есть массив расстояний между точками dists. Расстояния в нем записаны в произвольном порядке. Я хочу найти индекс минимального расстояния. Для этого использую np.argpartition следующим образом:

indices = np.argpartition(dists, number)[:number]

Если я задаю number = 1, то получаю

[413]

Если number = 5, то

[375 410 413 58 51]

Если number = 10, то вывод

[ 58 29 413 166 410 92 1980 375 51 2043]

Правильный ответ в задаче — 413 (то есть получаю только при number = 1). Я думал, что np.argpartition(dists, n)[:n] вернет мне индексы n минимальных элементов массива по возрастанию для любых n, то есть индекс 413 всегда должен был бы быть первым в списке в моем случае. Подскажите, какова логика np.argpartition(dists, n)[:n] для n > 1?

2
  • Попробуйте так: np.argpartition(dists, range(n))[:n] 5 ноя 2018 в 7:08
  • @MaxU Большое спасибо! Да, работает. Не могли бы пояснить почему и что происходит за сценой (в чем интуиция)? 5 ноя 2018 в 7:47

1 ответ 1

3

np.argpartition(a, kth, axis=-1, kind='introselect', order=None) возвращает индексы (позиции) элементов массива a таким образом, чтобы kth элемент(ы) массива соответствовал(и) позициям в отсортированном массиве a.

NOTE: порядок всех остальных элементов не гарантируется (может, но не должен, совпадать с отсортированным массивом).

Пример:

In [8]: a = np.array([30, 40, 20, 10])

получим индексы массива таким образом, чтобы 3-й (последний) элемент оказался в отсортированном массиве (позиции остальных элементов не определены):

In [9]: np.argpartition(a, 3)
Out[9]: array([2, 3, 0, 1], dtype=int64)
#                       ^

тоже самое, но теперь покажем элементы вместо индексов:

In [10]: a[np.argpartition(a, 3)]
Out[10]: array([20, 10, 30, 40])
#                           ^^

теперь получим индексы первых двух элементов в отсортированном массиве:

In [11]: np.argpartition(a, [0, 1])
Out[11]: array([3, 2, 1, 0], dtype=int64)
#               ^  ^

In [12]: a[np.argpartition(a, [0, 1])]
Out[12]: array([10, 20, 40, 30])
#               ^^  ^^

PS если нам надо отсортировать небольшую часть большого массива, то np.partition(), np.argpartition() будут работать гораздо быстрее по сравнению с np.sort(), np.argsort(), которые сортирует весь массив целиком:

In [15]: a = np.random.rand(10**7)

In [16]: %timeit np.partition(a, range(10))[:10]
358 ms ± 5.14 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [17]: %timeit np.sort(a)[:10]
2.58 s ± 12.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Если вас интересует только минимальный элемент, то выгоднее будет воспользоваться функцией ndarray.min() / ndarray.argmin():

In [19]: %timeit a.min()
10.2 ms ± 18 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [20]: %timeit np.partition(a, 0)
103 ms ± 9.03 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
1
  • 1
    Большое спасибо! Теперь понял, в чем дело было. 5 ноя 2018 в 19:42

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.