無法理解numpy的argpartition輸出

Question

我想從numpy使用arpgpartition，但似乎出現了問題，我似乎無法弄清楚。這是發生了什麼：

這些數組排序norms

np.sort(norms)[:5] 
array([ 53.64759445, 54.91434479, 60.11617279, 64.09630585, 64.75318909], dtype=float32) 

的第5個元素但是當我使用

norms[indices_sorted] 
array([ 60.11617279, 64.09630585, 53.64759445, 54.91434479, 64.75318909], dtype=float32) 

當我覺得我應該得到相同的結果排序陣列？

它工作得很好，當我使用3，因爲這不是我做出多大意義的參數indices_sorted = np.argpartition(norms, 3)[:3]

norms[indices_sorted] 
array([ 53.64759445, 54.91434479, 60.11617279], dtype=float32) 

，希望有人能提供一些見解？

編輯：改寫這個問題，因爲是否argpartition保留k分區元素的順序更有意義。

Answer 1

我們需要使用將按照排序順序保存的索引列表，而不是將第k個參數作爲標量進行提供。因此，爲了保持整個第一5要素排序的性質，而不是np.argpartition(a,5)[:5]，根本就 -

np.argpartition(a,range(5))[:5] 

這裏有一個樣品運行，以把事情說清楚 -

In [84]: a = np.random.rand(10) 

In [85]: a 
Out[85]: 
array([ 0.85017222, 0.19406266, 0.7879974 , 0.40444978, 0.46057793, 
     0.51428578, 0.03419694, 0.47708 , 0.73924536, 0.14437159]) 

In [86]: a[np.argpartition(a,5)[:5]] 
Out[86]: array([ 0.19406266, 0.14437159, 0.03419694, 0.40444978, 0.46057793]) 

In [87]: a[np.argpartition(a,range(5))[:5]] 
Out[87]: array([ 0.03419694, 0.14437159, 0.19406266, 0.40444978, 0.46057793]) 

請注意，argpartition有道理的性能方面，如果我們希望爲一小部分元素獲得排序索引，我們假設k元素的數量是元素總數的一小部分。

讓我們用一個更大的數據集，並試圖讓所有elems的排序指標，以使上述點明確 -

In [51]: a = np.random.rand(10000)*100 

In [52]: %timeit np.argpartition(a,range(a.size-1))[:5] 
10 loops, best of 3: 105 ms per loop 

In [53]: %timeit a.argsort() 
1000 loops, best of 3: 893 µs per loop 

因此，所有elems的排序，np.argpartition是不是要走的路。

現在，讓我們說，我想僅前5個elems的與大數據集來分類的指數，並保持了爲了使這些 -

In [68]: a = np.random.rand(10000)*100 

In [69]: np.argpartition(a,range(5))[:5] 
Out[69]: array([1647, 942, 2167, 1371, 2571]) 

In [70]: a.argsort()[:5] 
Out[70]: array([1647, 942, 2167, 1371, 2571]) 

In [71]: %timeit np.argpartition(a,range(5))[:5] 
10000 loops, best of 3: 112 µs per loop 

In [72]: %timeit a.argsort()[:5] 
1000 loops, best of 3: 888 µs per loop 

非常有用的在這裏！

Answer 2

鑑於inderectly排序的子集（頂部ķ，頂部的含義首先在排序順序）有兩個內置的解決方案任務：argsort和argpartition比照@ Divakar的回答。

但是，如果性能是一個考慮因素，那麼它可能（取決於數據的大小和感興趣的子集）非常值得抵制「單線程的誘惑」，多投入一行並申請argsort上的argpartition輸出：

>>> def top_k_sort(a, k): 
...  return np.argsort(a)[:k] 
... 
>>> def top_k_argp(a, k): 
...  return np.argpartition(a, range(k))[:k] 
... 
>>> def top_k_hybrid(a, k): 
...  b = np.argpartition(a, k)[:k] 
...  return b[np.argsort(a[b])] 

>>> k = 100 
>>> timeit.timeit('f(a,k)', 'a=rng((100000,))', number = 1000, globals={'f': top_k_sort, 'rng': np.random.random, 'k': k}) 
8.348663672804832 
>>> timeit.timeit('f(a,k)', 'a=rng((100000,))', number = 1000, globals={'f': top_k_argp, 'rng': np.random.random, 'k': k}) 
9.869098862167448 
>>> timeit.timeit('f(a,k)', 'a=rng((100000,))', number = 1000, globals={'f': top_k_hybrid, 'rng': np.random.random, 'k': k}) 
1.2305558240041137 

argsort是O（n log n）的，argpartition與範圍的參數似乎是O（NK），和argpartition + argsort是O（n + k中的日誌K）（？）

因此在一個有趣的政權n >>k >> 1混合方法預計最快