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!
4 Antworten
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]
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.
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))
L = [4, 1, 0, 8, 5, 2]
sorted(range(len(L)), key=lambda i:L[i])
Verwandte Fragen
Verknüpfte Fragen
Neue Fragen
python
Python ist eine dynamisch typisierte Mehrzweck-Programmiersprache mit mehreren Paradigmen. Es wurde entwickelt, um schnell zu lernen, zu verstehen, zu verwenden und eine saubere und einheitliche Syntax durchzusetzen. Bitte beachten Sie, dass Python 2 ab dem 01.01.2020 offiziell nicht mehr unterstützt wird. Fügen Sie für versionenspezifische Python-Fragen das Tag [python-2.7] oder [python-3.x] hinzu. Wenn Sie eine Python-Variante (z. B. Jython, PyPy) oder eine Bibliothek (z. B. Pandas und NumPy) verwenden, fügen Sie diese bitte in die Tags ein.