Không thể hiểu được kết quả đầu ra có phần khó khăn

Question

Tôi đang cố gắng sử dụng arpgpartition từ gumpy, nhưng có vẻ như có điều gì đó sai và tôi dường như không thể tìm ra. Đây là những gì đang xảy ra:

Đây là 5 yếu tố đầu tiên của mảng được sắp xếp norms

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

Nhưng khi tôi sử dụng

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

Khi tôi nghĩ mình sẽ nhận được kết quả tương tự như sắp xếp mảng?

Nó hoạt động tốt khi tôi sử dụng 3 như tham số indices_sorted = np.argpartition(norms, 3)[:3]

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

này không làm cho nhiều ý nghĩa với tôi, hy vọng ai đó có thể cung cấp một số cái nhìn sâu sắc?

EDIT: Rephrasing câu hỏi này cho dù argpartition bảo tồn thứ tự của các phần tử phân đoạn k có ý nghĩa hơn.

Answer 1

Chúng tôi cần sử dụng danh sách các chỉ mục được lưu giữ theo thứ tự được sắp xếp thay vì cho phép tham số thứ k dưới dạng vô hướng. Vì vậy, để duy trì tính chất được sắp xếp trên 5 yếu tố đầu tiên, thay vì np.argpartition(a,5)[:5], chỉ cần làm -

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

Dưới đây là một hoạt động mẫu để làm cho mọi việc rõ ràng -

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

Xin lưu ý rằng argpartition có ý nghĩa trên khía cạnh hiệu suất, nếu chúng ta đang tìm cách để có được các chỉ mục được sắp xếp cho một tập hợp con nhỏ các phần tử, giả sử số lượng các elem là một phần nhỏ trong tổng số các phần tử.

Hãy sử dụng một tập dữ liệu lớn hơn và cố gắng để có được chỉ số được sắp xếp cho tất cả elems để làm cho điểm nêu trên rõ ràng -

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 

Vì vậy, để sắp xếp tất cả elems, np.argpartition không phải là con đường để đi.

Bây giờ, chúng ta hãy nói rằng tôi muốn để có được chỉ số được sắp xếp cho chỉ 5 elems đầu tiên với tập dữ liệu lớn và cũng giữ trật tự cho những -

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 

Rất hữu ích ở đây!

Answer 2

Với nhiệm vụ inderectly sắp xếp một tập hợp con (đầu k, ý nghĩa hàng đầu đầu tiên trong thứ tự sắp xếp) có hai giải pháp dựng sẵn: argsort và argpartition cf. @ Câu trả lời của Divakar.

Nếu hiệu suất là cân nhắc thì có thể (tùy thuộc vào kích thước của dữ liệu và tập hợp con quan tâm) cũng có giá trị chống lại "thu hút một lớp", đầu tư thêm một dòng và áp dụng argsort trên đầu ra của 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 là O (n log n), argpartition với lập luận loạt dường như là O (nk), và argpartition + argsort là O (n + k log k) (?)

Do đó ở chế độ thú vị n >>k >> 1 phương pháp lai được mong đợi là nhanh nhất