быстрый способ найти наибольшее N элементов в массиве Numpy

Question

Я знаю, что могу это сделать так:

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

Однако, это очень медленно, так как он сделал полный вид.

Удивительно, дайте ли numpy некоторые методы, чтобы сделать это быстро.

Answer 1

Модуль 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 является случайный массив 1000000-элементов.

Тайминги были следующими:

• bottleneck.partition(): 25,6 мс на петле
• np.argsort(): 198 мс на петле
• heapq.nlargest(): 358 мс на петле

Answer 2

Возможно 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] 

Answer 3

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

import heapq 
heapq.nlargest(N, a) 

получить N крупнейших членов.

Answer 4

Каждый отрицательный знак в предлагаемое решение для узких мест

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

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

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

Также предлагаемого NumPy раствора

a.argsort()[-10:] 

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

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

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

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

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

-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) 

Answer 5

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] 

Результат:

Хронометраж:

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 

Answer 6

Вы также можете использовать функцию процентиля 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 мс
• np.percentile(): 54 мс

Answer 7

Я имел эту проблему и, поскольку этот вопрос 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 (решение Ādas) бросались привязанные. Но, используя np.percentile (numpy_2), у вас есть те элементы topN, которые уже отсортированы, что не относится к другим решениям. С другой стороны, если вас интересуют индексы этих элементов, процентиль не является полезным.

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

Код, используемый в тесте выглядит следующим образом (питон 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))