56

私は次のようにできることを知っています：

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

ただし、完全なソートを行ったため、非常に低速です。

numpy が高速に実行できるメソッドを提供しているかどうか疑問に思います。

4

7 に答える 7

78

numpy 1.8O(n) * log(n) である完全な並べ替えとは対照的に、O(n) 時間で部分的な並べ替えを実装partitionし、実行します。argpartition

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
于 2013-11-24T17:50:20.710 に答える
47

この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 ミリ秒
  • np.argsort(): 1 ループあたり 198 ミリ秒
  • heapq.nlargest(): ループあたり 358 ミリ秒
于 2012-04-26T16:35:58.790 に答える
11

提案されたボトルネック ソリューションの各マイナス記号

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

データのコピーを作成します。次のようにしてコピーを削除できます

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

また、提案されたnumpyソリューション

a.argsort()[-10:]

値ではなくインデックスを返します。修正は、インデックスを使用して値を見つけることです。

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

2 つのボトルネック ソリューションの相対速度は、初期配列の要素の順序に依存します。これは、2 つのアプローチがデータを異なるポイントで分割するためです。

言い換えれば、特定のランダム配列のタイミングにより、どちらの方法もより速く見えるようになります。

それぞれが 1,000,000 個の要素を持つ 100 個のランダムな配列全体でタイミングを平均すると、

-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)
于 2012-05-05T15:02:18.250 に答える
8

多分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最大の要素のインデックスを検索する場合は、bottleneckbottleneck.argpartsort

>>> x = np.array([1,-5,4,6,-3,3])
>>> z = bottleneck.argpartsort(-x, 3)[:3]
>>> z
array([3, 2, 5]
于 2012-04-26T16:34:54.627 に答える
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 ミリ秒
  • np.パーセンタイル (): 54 ミリ秒
于 2015-12-05T22:44:06.780 に答える
1

配列を数値のリストとして保存しても問題ない場合は、次を使用できます

import heapq
heapq.nlargest(N, a)

N最大のメンバーを取得します。

于 2012-04-26T16:35:47.373 に答える