m Kleinste Werte von den oberen Dreiecksmatrix mit ihrem Indizes als eine Liste von Tupeln

Question

Ich habe eine np.ndarray wie folgt:

[[ inf 1. 3. 2. 1.] 
[ inf inf 2. 3. 2.] 
[ inf inf inf 5. 4.] 
[ inf inf inf inf 1.] 
[ inf inf inf inf inf]] 

Gibt es einen Weg in die Indizes und die Werte des m kleinste Gegenstände zu erhalten Dieses nd-Array? Also, wenn ich die 4 kleinste wollte, es wäre

[(0,1,1),(0,4,1),(3,4,1),(0,3,2)] 

wo (row, col, val) die Schreibweise oben ist.

Wenn mehrere Werte vorhanden sind, wird einer von ihnen zufällig ausgewählt. Zum Beispiel gab es 3 Einsen und dann nächstkleinere ist ein Wert 2, aber (0,3,2), (1,2,2), (1,4,2) waren alle möglichen Entscheidungen.

Im Wesentlichen kann ich die k kleinsten Werte in diesem Format aus der oberen Dreiecksmatrix effizient extrahieren (die Matrix ist viel größer als das obige Beispiel). Ich habe versucht, es flach zu machen, quadratische Form, klein, aber ich habe Probleme, die Indizes und Werte auszurichten. Vielen Dank!

Answer 1

Für eine Inf gefüllt Array -

r,c = np.unravel_index(a.ravel().argsort()[:4], a.shape) 
out = zip(r,c,a[r,c]) 

Für Leistung, betrachten np.argpartition verwenden. Ersetzen Sie also a.ravel().argsort()[:4] durch np.argpartition(a.ravel(), range(4))[:4].

Probelauf -

In [285]: a 
Out[285]: 
array([[ inf, 1., 3., 2., 1.], 
     [ inf, inf, 2., 3., 2.], 
     [ inf, inf, inf, 5., 4.], 
     [ inf, inf, inf, inf, 1.], 
     [ inf, inf, inf, inf, inf]]) 

In [286]: out 
Out[286]: [(0, 1, 1.0), (0, 4, 1.0), (3, 4, 1.0), (0, 3, 2.0)] 

---

für einen allgemeinen Fall -

R,C = np.triu_indices(a.shape[1],1) 
idx = a[R,C].argsort()[:4] 
r,c = R[idx], C[idx] 
out = zip(r,c,a[r,c]) 

Probelauf -

In [351]: a 
Out[351]: 
array([[ 68., 67., 81., 23., 16.], 
     [ 84., 83., 20., 66., 48.], 
     [ 58., 72., 98., 63., 30.], 
     [ 61., 40., 1., 86., 22.], 
     [ 29., 95., 38., 22., 95.]]) 
In [352]: out 
Out[352]: [(0, 4, 16.0), (1, 2, 20.0), (3, 4, 22.0), (0, 3, 23.0)] 

Für Leistung, betrachten np.argpartition verwenden. Ersetzen Sie also a[R,C].argsort()[:4] durch np.argpartition(a[R,C], range(4))[:4].

Answer 2

So etwas wie dies funktioniert:

import numpy as np 
a = np.random.rand(4,4) 
tuples = [(ix,iy, a[ix,iy]) for ix, row in enumerate(a) for iy, i in enumerate(row)] 
sorted(tuples,key=lambda x: x[2])[:10] 

Wo k = 10 ([:10]) aus Ihrer Frage.

Wenn Sie nur die obere Dreieckselemente möchten Sie eine Bedingung der Liste Verständnis hinzufügen:

a = np.random.rand(4,4) 
tuples = [(ix,iy, a[ix,iy]) for ix, row in enumerate(a) for iy, i in enumerate(row) if ix<=iy] 
sorted(tuples,key=lambda x: x[2]) 

Answer 3

Wenn mein np.array()n ist kann ich die n kleinsten Werte von ihm erhalten, indem es (mit * np.ndenumerate()) und unter Verwendung des heapq Moduls .heapify Abflachung () und .smallest() Methoden wie so:

#!python 
flattened = [(y,x) for x,y in np.ndenumerate(n)] 
# tuples reversed for natural sorting on values rather than co-ords 
heapq.heapify(flattened) 
results = heapq.nsmallest(4, flattened) 

Aber viel zusätzlichen Speicher verwenden und die Daten und Koordinaten aus Numpy effizienten Arrays in Python nativen Listen extrahieren. Also gibt es wahrscheinlich viel bessere Möglichkeiten, es nativer in Python zu machen.