Es tut mir im Voraus leid, wenn dies eine doppelte Frage ist. Ich habe nach diesen Informationen gesucht, sie aber immer noch nicht gefunden.

Ist es möglich, ein Numpy-Array (oder eine Python-Liste) anzuordnen, indem die Indizes der N größten Elemente in absteigender Reihenfolge sehr effizient verwendet werden?

Zum Beispiel das Array:

a = array([4, 1, 0, 8, 5, 2])

Die Indizes der größten Elemente in absteigender Reihenfolge würden ergeben (unter Berücksichtigung von N = 6 sind alle Elemente enthalten):

8 -> 3

5 -> 4

4 -> 0

2 -> 5

1 -> 1

0 -> 2

result = [3, 4, 0, 5, 1, 2]

Ich weiß, wie man es mit einem etwas albernen Ansatz macht (wie das Sortieren des Arrays und das Suchen nach jeder der N Zahlen für ihre Indizes), aber ich habe mich gefragt, ob es eine effiziente Bibliothek wie Engpass oder Heapq oder vielleicht einen pythonischen Ansatz gibt das sehr schnell. Ich muss es in mehreren Arrays mit jeweils 300.000 Elementen anwenden, daher ist die Leistung ein Problem.

Danke im Voraus!

UPDATE

Ich habe die Antworten gelesen und beschlossen, sie mit 300.000 zufälligen Ganzzahlen zu zeitigen. Hier sind die Ergebnisse:

Lösung 1: sorted(range(len(a)), key=lambda i:a[i]) Zeit: 230 ms

Lösung 2: heapq.nlargest(len(a), zip(a, itertools.count())) Zeit: 396 ms

Lösung 3: heapq.nlargest(len(a), enumerate(a), key=operator.itemgetter(1)) Zeit: 864 ms

Lösung 4: def f(a,N): return np.argsort(a)[::-1][:N] (N = len(a)) Zeit: 104 ms

Vielen Dank für die schnellen und sehr guten Antworten!

21
Willian Fuks 8 Okt. 2012 im 22:48

4 Antworten

Beste Antwort

Haben Sie sich die integrierte numpy argsort -Methode angesehen?:

http://docs.scipy.org/doc/numpy/reference/generated/numpy.argsort.html

Mit dieser Methode kann ich ein Array mit 300.000 zufälligen Floats in ca. 29 ms auf meinem Computer sortieren.

def f(a,N):
    return np.argsort(a)[::-1][:N]
20
halex 8 Okt. 2012 im 19:03

Sie können heapq verwenden, um dies einfach genug zu tun:

>>> heapq.nlargest(3, zip(a, itertools.count()))
[(8, 3), (5, 4), (4, 5)]

Tupel werden sortiert, indem nach dem ersten Wert, dann nach dem zweiten usw. sortiert wird. Dies bedeutet, dass wir einfach ein Tupel aus (value, index) erstellen und sortieren können, wobei wir die Indizes der Werte erhalten (die Werte werden auch angegeben). aber wir können diese leicht wegwerfen).

Ich verwende zip() und itertools.count(), da die Aufzählung uns die falsche Reihenfolge gibt, sodass sie nach Index und nicht nach Wert sortiert werden. Alternativ könnten Sie auch ((value, index) for index, value in enumerate(a)) ausführen, aber ich denke, das ist weniger klar.

Eine andere Alternative besteht darin, einen Schlüssel anzugeben und dabei heapq.nlargest(3, enumerate(a), key=operator.itemgetter(1)) auszuführen.

5
Gareth Latty 8 Okt. 2012 im 18:52

Eine andere Möglichkeit, heapq zu verwenden

heapq.nlargest(n, range(len(a)), key=a.__getitem__)

Wie an anderer Stelle kommentiert, wird das Sortieren nur dann übertroffen, wenn a sehr groß und n<<len(a) ist, da das Sortieren in Python eine relativ schnelle Operation ist. Irgendwann schlägt jedoch ein langsames O (n) immer das O (n * log (n))

1
John La Rooy 9 Okt. 2012 im 05:36
L = [4, 1, 0, 8, 5, 2]
sorted(range(len(L)), key=lambda i:L[i])
11
inspectorG4dget 8 Okt. 2012 im 18:52