Вопрос по python, sorting, numpy – Быстрый способ найти самые большие N элементов в массиве NumPy

37

Я знаю, что могу сделать это следующим образом:

<code>import numpy as np
N=10
a=np.arange(1,100,1)
np.argsort()[-N:]
</code>

Тем не менее, это очень медленно, так как он сделал полную сортировку.

Интересно, предоставляют ли numpy какие-то методы, чтобы сделать это быстро

Возможный дубликатHow to get indices of N maximum values in a numpy array? Seanny123

Ваш Ответ

7   ответов
54

numpy 1.8 инвентарьpartition а такжеargpartition которые выполняют частичную сортировку (за O (n) время, в отличие от полной сортировки, то есть O (n) * log (n)).

import numpy as np

test = np.array([9,1,3,4,8,7,2,5,6,0])

temp = np.argpartition(-test, 4)
result_args = temp[:4]

temp = np.partition(-test, 4)
result = -temp[:4]

Результат:

>>> result_args
array([0, 4, 8, 5]) # indices of highest vals
>>> result
array([9, 8, 6, 7]) # highest vals

Сроки:

In [16]: a = np.arange(10000)

In [17]: np.random.shuffle(a)

In [18]: %timeit np.argsort(a)
1000 loops, best of 3: 1.02 ms per loop

In [19]: %timeit np.argpartition(a, 100)
10000 loops, best of 3: 139 us per loop

In [20]: %timeit np.argpartition(a, 1000)
10000 loops, best of 3: 141 us per loop
@ User3080953. Я никогда не говорю, что результат гарантированно будет в порядке, вот что такое частичная сортировка. И в примере я приведу:[9, 8, 6, 7] Понятно, что n высших значений не в порядке.
Обратите внимание, что это может быть полезно для других: пример не лучший выбор, так как результат не гарантируется
@ User3080953. Попробуйте установить & quot; kth & quot; как последовательность, как отмечено в документе numpy.argpartition - «Если он снабжен последовательностью k-го, он сразу разделит их все в их отсортированную позицию». И пример, следующий за документом - & gt; & gt; & gt; x = np.array ([3, 4, 2, 1]) & gt; & gt; & gt; x [np.argpartition (x, 3)] array ([2, 1, 3, 4]) & gt; & gt; & gt; массив x [np.argpartition (x, (1, 3))] ([1, 2, 3, 4])docs.scipy.org/doc/numpy/reference/generated/…
да, задним числом, это очевидно, потому что вы не можете сортировать по O (n). Я потратил 20 минут на поиск ошибки, и подумал, что это может быть полезно для других людей, читающих это
Можем ли мы получить объяснение, почему массив инвертируется во времяargpartition? Не должно ли это быть по сути тем же самым, но с выбором наtemp[:5] вместоtemp[4:] затем? Или я здесь упускаю важную деталь?
6

heapq.nlargest

import numpy as np
import heapq

x = np.array([1,-5,4,6,-3,3])

z = heapq.nlargest(3,x)

Результат:

>>> z
[6, 4, 3]

Если вы хотите найти индексыn самые большие элементы, использующиеbottleneck вы могли бы использовать bottleneck.argpartsort

>>> x = np.array([1,-5,4,6,-3,3])
>>> z = bottleneck.argpartsort(-x, 3)[:3]
>>> z
array([3, 2, 5]
Но куча q на самом деле медленнее (также упоминается в следующем ответе). Hailiang Zhang
2

Вы также можете использовать процентильную функцию numpy. В моем случае это было немного быстрее, чем bottleneck.partsort ():

import timeit
import bottleneck as bn

N,M,K = 10,1000000,100

start = timeit.default_timer()
for k in range(K):
    a=np.random.uniform(size=M)
    tmp=-bn.partsort(-a, N)[:N]
stop = timeit.default_timer()
print (stop - start)/K

start = timeit.default_timer()
perc = (np.arange(M-N,M)+1.0)/M*100
for k in range(K):
    a=np.random.uniform(size=M)
    tmp=np.percentile(a,perc)
stop = timeit.default_timer()
print (stop - start)/K

Среднее время за цикл:

  • bottleneck.partsort(): 59 ms
  • np.percentile(): 54 ms
Обратите внимание, что процентиль может интерполировать некоторые значения по умолчанию. Если ты хочешьexactly те же значения, что и во входном массиве, вы можете добавить аргументinterpolation='nearest' на призыв кnp.percentile, Увидетьdocumentation Больше подробностей.
10

-bottleneck.partsort(-a, 10)[:10]

делает копию данных. Мы можем удалить копии, выполнив

bottleneck.partsort(a, a.size-10)[-10:]

Также предлагается решение NumPy

a.argsort()[-10:]

возвращает индексы, а не значения. Исправление заключается в использовании индексов для поиска значений:

a[a.argsort()[-10:]]

Относительная скорость решения двух узких мест зависит от упорядочения элементов в исходном массиве, поскольку эти два подхода разделяют данные в разных точках.

Другими словами, синхронизация с любым конкретным случайным массивом может заставить любой метод выглядеть быстрее.

Усреднение синхронизации по 100 случайным массивам, каждый с 1 000 000 элементов, дает

-bn.partsort(-a, 10)[:10]: 1.76 ms per loop
bn.partsort(a, a.size-10)[-10:]: 0.92 ms per loop
a[a.argsort()[-10:]]: 15.34 ms per loop

где временной код выглядит следующим образом:

import time
import numpy as np
import bottleneck as bn

def bottleneck_1(a):
    return -bn.partsort(-a, 10)[:10]

def bottleneck_2(a):
    return bn.partsort(a, a.size-10)[-10:]

def numpy(a):
    return a[a.argsort()[-10:]]

def do_nothing(a):
    return a

def benchmark(func, size=1000000, ntimes=100):
    t1 = time.time()
    for n in range(ntimes):
        a = np.random.rand(size)
        func(a)
    t2 = time.time()
    ms_per_loop = 1000000 * (t2 - t1) / size
    return ms_per_loop

t1 = benchmark(bottleneck_1)
t2 = benchmark(bottleneck_2)
t3 = benchmark(numpy)
t4 = benchmark(do_nothing)

print "-bn.partsort(-a, 10)[:10]: %0.2f ms per loop" % (t1 - t4)
print "bn.partsort(a, a.size-10)[-10:]: %0.2f ms per loop" % (t2 - t4)
print "a[a.argsort()[-10:]]: %0.2f ms per loop" % (t3 - t4)
39

bottleneck Модуль имеет быстрый метод частичной сортировки, который работает напрямую с массивами Numpy:bottleneck.partition().

Обратите внимание, чтоbottleneck.partition() возвращает отсортированные фактические значения, если вы хотите индексы отсортированных значений (чтоnumpy.argsort() возвращается) вы должны использоватьbottleneck.argpartition().

Я оценил:

  • z = -bottleneck.partition(-a, 10)[:10]
  • z = a.argsort()[-10:]
  • z = heapq.nlargest(10, a)

гдеa случайный массив из 1 000 000 элементов

Время было следующим:

  • bottleneck.partition(): 25.6 ms per loop
  • np.argsort(): 198 ms per loop
  • heapq.nlargest(): 358 ms per loop
@aix, извини, читаю какnargmaxнеnanargmax.
Возможно, узкое место быстрее, но поскольку оно не предусмотрено в EPD7.1, мы не можем использовать это. Hailiang Zhang
@HailiangZhang: я бы тоже хотел увидетьbottleneck добавлено в EPD.
@ Майк Грэм: спасибо за редактирование, ноnanargmax() делает что-то отличное от того, что просит ОП. Я собираюсь отменить редактирование. Поправь меня, если я что-то упустил.
Для записи,bottleneck.partsort() а такжеnp.argsort() делают две немного разные вещи. Они возвращают значение и индекс соответственно. Если вы хотите, чтобы узкое место вернуло индекс, используйтеbottleneck.argpartsort
8

и, так как этот вопрос 5 лет, мне пришлось повторить все тесты и изменить синтаксис узкого места (нетpartsort больше, этоpartition сейчас).

Я использовал те же аргументы, что и kwgoodman, за исключением количества извлеченных элементов, которое я увеличил до 50 (чтобы лучше соответствовать моей конкретной ситуации).

Я получил эти результаты:

bottleneck 1: 01.12 ms per loop
bottleneck 2: 00.95 ms per loop
pandas      : 01.65 ms per loop
heapq       : 08.61 ms per loop
numpy       : 12.37 ms per loop
numpy 2     : 00.95 ms per loop

Таким образом, bottleneck_2 и numpy_2 (решение adas) были связаны. Но, используяnp.percentile (numpy_2) у вас уже есть отсортированные элементы topN, что не относится к другим решениям. С другой стороны, если вас также интересуют индексы этих элементов, процентиль бесполезен.

Я также добавил панд, которые используют узкое место снизу, если доступно (http://pandas.pydata.org/pandas-docs/stable/install.html#recommended-dependencies). Если у вас уже есть серия Pandas или DataFrame для начала, вы в хороших руках, просто используйтеnlargest и вы сделали.

Код, используемый для теста, выглядит следующим образом (python 3, пожалуйста):

import time
import numpy as np
import bottleneck as bn
import pandas as pd
import heapq

def bottleneck_1(a, n):
    return -bn.partition(-a, n)[:n]

def bottleneck_2(a, n):
    return bn.partition(a, a.size-n)[-n:]

def numpy(a, n):
    return a[a.argsort()[-n:]]

def numpy_2(a, n):
    M = a.shape[0]
    perc = (np.arange(M-n,M)+1.0)/M*100
    return np.percentile(a,perc)

def pandas(a, n):
    return pd.Series(a).nlargest(n)

def hpq(a, n):
    return heapq.nlargest(n, a)

def do_nothing(a, n):
    return a[:n]

def benchmark(func, size=1000000, ntimes=100, topn=50):
    t1 = time.time()
    for n in range(ntimes):
        a = np.random.rand(size)
        func(a, topn)
    t2 = time.time()
    ms_per_loop =, 1000000 * (t2 - t1) / size
    return ms_per_loop

t1 = benchmark(bottleneck_1)
t2 = benchmark(bottleneck_2)
t3 = benchmark(pandas)
t4 = benchmark(hpq)
t5 = benchmark(numpy)
t6 = benchmark(numpy_2)
t0 = benchmark(do_nothing)

print("bottleneck 1: {:05.2f} ms per loop".format(t1 - t0))
print("bottleneck 2: {:05.2f} ms per loop".format(t2 - t0))
print("pandas      : {:05.2f} ms per loop".format(t3 - t0))
print("heapq       : {:05.2f} ms per loop".format(t4 - t0))
print("numpy       : {:05.2f} ms per loop".format(t5 - t0))
print("numpy 2     : {:05.2f} ms per loop".format(t6 - t0))
спасибо за код! Я также протестировал np.argpartition и обнаружил, что он в 10 раз медленнее, чем np.argmax, когда argpartition настроен на поиск верхнего 1 элемента.
1

Если сохранение массива в виде списка чисел не является проблематичным, вы можете использовать

import heapq
heapq.nlargest(N, a)

чтобы получитьN Крупнейшие участники.

Похожие вопросы