Jak uzyskać indeksy posortowanej tablicy w Pythonie

199

Mam listę numeryczną:

myList = [1, 2, 3, 100, 5]

Teraz posortuję tę listę, aby uzyskać [1, 2, 3, 5, 100]. To, czego chcę, to indeksy elementów z oryginalnej listy w posortowanej kolejności, tj. [0, 1, 2, 4, 3] --- ala funkcja sortująca MATLAB, która zwraca zarówno wartości, jak i indeksy.

Gyan
źródło
2
Powiązane: stackoverflow.com/questions/7851077/…
kevinarpe
@unutbu To nie jest dupek (IMO). Pytanie nie jest sprzeczne z użyciem Numpy.argsort ()
Amit
@amit: Co rozumiesz przez „nie zaprzecza”?
unutbu
@unutbu Numpy.argsort () jest dobrą odpowiedzią na to pytanie, może to być duplikat do drugiego wątku, do którego link (który ty również zamknąłeś i myślę, że nie powinieneś), ale nie do tego, o którym wspomniałeś, jak Numpy. argsort () to dobra odpowiedź dla tych dwóch, ale NIE dla tej, o której mówiłeś.
amit
1
Niestety to pytanie ma poważną wadę w wyborze przykładu, ponieważ dwa różne sposoby czytania pytania dawałyby tę samą odpowiedź, gdy dane wejściowe są tylko transpozycją w nieporządku.

Odpowiedzi:

147

Coś jak następne:

>>> myList = [1, 2, 3, 100, 5]
>>> [i[0] for i in sorted(enumerate(myList), key=lambda x:x[1])]
[0, 1, 2, 4, 3]

enumerate(myList) daje listę zawierającą krotki (indeks, wartość):

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

Sortujesz listę, przekazując ją sortedi określając funkcję do wyodrębnienia klucza sortowania (drugi element każdej krotki; po to lambdajest. Na koniec oryginalny indeks każdego posortowanego elementu jest wyodrębniany przy użyciu [i[0] for i in ...]listy.

Roman Bodnarchuk
źródło
7
możesz użyć itemgetter(1)zamiast funkcji lambda
John La Rooy,
4
@gnibbler odnosi się do itemgetterfunkcji w operatormodule, FYI. Więc zrób to, from operator import itemgetteraby z niego skorzystać.
Lauritz V. Thaulow
1
możesz uzyskać posortowaną listę i wskazówki, używając zip:sorted_items, sorted_inds = zip(*sorted([(i,e) for i,e in enumerate(my_list)], key=itemgetter(1)))
Charles L.
@RomanBodnarchuk to nie działa, x = [3,1,2]; numpy.argsort(x)daje [1,2,0].
shahar_m
24

Odpowiedzi enumeratesą miłe, ale osobiście nie lubię lambda używanego do sortowania według wartości. Poniższe odwraca indeks i wartość i sortuje je. Więc najpierw posortuje według wartości, a następnie według indeksu.

sorted((e,i) for i,e in enumerate(myList))
Ant6n
źródło
11

Zaktualizowana odpowiedź za pomocą enumeratei itemgetter:

sorted(enumerate(a), key=lambda x: x[1])
# [(0, 1), (1, 2), (2, 3), (4, 5), (3, 100)]

Spakuj listy razem: pierwszy element w krotce będzie indeksem, drugi to wartość (następnie posortuj go przy użyciu drugiej wartości krotki x[1], x to krotka)

Lub używając itemgetterz operatormodułu`:

from operator import itemgetter
sorted(enumerate(a), key=itemgetter(1))
Matt
źródło
1
wyliczenie wydaje się w tym przypadku bardziej odpowiednie niż zip
njzk2
10

Zrobiłem szybką kontrolę wydajności tych przy pomocy perfplot (mój projekt) i stwierdziłem, że trudno jest polecić cokolwiek innego niż numpy (zwróć uwagę na skalę logów):

wprowadź opis zdjęcia tutaj


Kod do odtworzenia fabuły:

import perfplot
import numpy


def sorted_enumerate(seq):
    return [i for (v, i) in sorted((v, i) for (i, v) in enumerate(seq))]


def sorted_enumerate_key(seq):
    return [x for x, y in sorted(enumerate(seq), key=lambda x: x[1])]


def sorted_range(seq):
    return sorted(range(len(seq)), key=seq.__getitem__)


def numpy_argsort(x):
    return numpy.argsort(x)


perfplot.save(
    "argsort.png",
    setup=lambda n: numpy.random.rand(n),
    kernels=[sorted_enumerate, sorted_enumerate_key, sorted_range, numpy_argsort],
    n_range=[2 ** k for k in range(15)],
    xlabel="len(x)",
)
Nico Schlömer
źródło
6

Jeśli nie chcesz używać numpy,

sorted(range(len(seq)), key=seq.__getitem__)

jest najszybszy, jak pokazano tutaj .

mab
źródło
5

Zasadniczo musisz zrobić argsort , to jakiej implementacji potrzebujesz, jeśli chcesz korzystać z zewnętrznych bibliotek (np. NumPy) lub jeśli chcesz pozostać czystym Pythonem bez zależności.

Pytanie, które musisz sobie zadać, brzmi: czy chcesz

  • indeksy, które posortowałyby tablicę / listę
  • indeksy, które elementy miałyby w posortowanej tablicy / liście

Niestety przykład w pytaniu nie wyjaśnia, co jest pożądane, ponieważ oba dają ten sam rezultat:

>>> arr = np.array([1, 2, 3, 100, 5])

>>> np.argsort(np.argsort(arr))
array([0, 1, 2, 4, 3], dtype=int64)

>>> np.argsort(arr)
array([0, 1, 2, 4, 3], dtype=int64)

Wybierając argsort implementacji

Jeśli masz do dyspozycji NumPy, możesz po prostu użyć funkcji numpy.argsortlub metody numpy.ndarray.argsort.

Wdrożenie bez NumPy zostało już wspomniane w kilku innych odpowiedziach, więc po prostu podsumuję najszybsze rozwiązanie zgodnie z odpowiedzią testu porównawczego tutaj

def argsort(l):
    return sorted(range(len(l)), key=l.__getitem__)

Uzyskiwanie wskaźników, które posortowałyby tablicę / listę

Aby uzyskać indeksy, które posortowałyby tablicę / listę, możesz po prostu wywołać argsorttablicę lub listę. Używam tutaj wersji NumPy, ale implementacja Pythona powinna dawać takie same wyniki

>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(arr)
array([1, 2, 0, 3], dtype=int64)

Wynik zawiera indeksy potrzebne do uzyskania posortowanej tablicy.

Ponieważ posortowana tablica byłaby tablicą [1, 2, 3, 4]argsortowaną, zawiera indeksy tych elementów w oryginale.

  • Najmniejszą wartością jest 1i jest w indeksie 1w oryginale, więc pierwszym elementem wyniku jest1 .
  • 2Jest indeksem 2w oryginale więc drugi element wyniku jest 2.
  • 3Jest indeksem 0w oryginale więc trzeci element wyniku jest 0.
  • Największa wartość 4i jest w indeksie 3w oryginale, więc ostatnim elementem wyniku jest 3.

Uzyskiwanie indeksów, które elementy miałyby w posortowanej tablicy / liście

W takim przypadku należy złożyć argsort dwukrotnie wniosek :

>>> arr = np.array([3, 1, 2, 4])
>>> np.argsort(np.argsort(arr))
array([2, 0, 1, 3], dtype=int64)

W tym przypadku :

  • pierwszym elementem oryginału jest 3, co jest trzecią co do wielkości wartością, więc miałby indeks 2w posortowanej tablicy / liście, więc pierwszym elementem jest2 .
  • drugim elementem oryginału jest 1, która jest najmniejszą wartością, więc miałby indeks 0w posortowanej tablicy / liście, więc drugim elementem jest 0.
  • trzecim elementem oryginału jest 2, co jest drugą najmniejszą wartością, więc miałby indeks 1w posortowanej tablicy / liście, więc trzeci element to 1.
  • czwartym elementem oryginału jest 4największa wartość, więc miałby indeks 3w posortowanej tablicy / liście, więc ostatnim elementem jest 3.
MSeifert
źródło
4

Inne odpowiedzi są NIEPRAWIDŁOWE.

Uruchamianie argsortraz nie jest rozwiązaniem. Na przykład następujący kod:

import numpy as np
x = [3,1,2]
np.argsort(x)

plony, array([1, 2, 0], dtype=int64)których nie chcemy.

Odpowiedź powinna brzmieć argsortdwa razy:

import numpy as np
x = [3,1,2]
np.argsort(np.argsort(x))

daje array([2, 0, 1], dtype=int64)zgodnie z oczekiwaniami.

shahar_m
źródło
Twoje twierdzenie czyni x[2](3) najmniejszym elementem i x[1](1) największym elementem (ponieważ sortowanie liczb całkowitych porządkuje je od najmniejszej wartości do największej wartości). Ponadto, na przykładzie PO, pojedynczy np.argsort([1, 2, 3, 100, 5])dochód array([0, 1, 2, 4, 3]), który wydaje się być wskaźnikami, których chce PO.
0 0
1
@ 0 0 twój przykład jest konkretnym przypadkiem. Jeśli uciekniemy arr = [1,2,3,100, 5, 9] res = np.argsort(arr) print(res), dostaniemy [0 1 2 4 5 3]co jest złe.
shahar_m
Nie jestem pewien, co jest nie tak: arr[res]daje array([ 1, 2, 3, 5, 9, 100]), co wydaje się być całkowicie w porządku, ponieważ wynikowa tablica jest w (rosnącej) kolejności.
0 0
@ 0 0 dla arr=[1,2,3,100, 5, 9], oczekuję, że wynik będzie inds=[0,1,2,5,3,4], ponieważ jest to kolejność, w której będziesz porządkować elementy (coraz częściej) - 1 jest na miejscu 0, 2 na 1 miejscu, ...., 5 na 3 miejsce i 9 na 4 miejscu. Aby uzyskać ten wynik ( inds), muszę uruchomić argsortdwa razy, jak już wspomniałem.
shahar_m
Wskaźniki te są więc rodzajem rankingu elementów tablicy (0 miejsce, 1 miejsce itp.). Biorąc pod uwagę wzmiankę OP o MATLABsort , sądzę, że OP chce innej funkcjonalności, podobnie jak np.argsortzwykle jest używana (gdzie można użyć arr[np.argsort[arr]]do uzyskania posortowanej tablicy, jak w ostatnim przykładzie MATLAB). Twoja odpowiedź dotyczy tej sprawy / pytania .
0 0
0

Zaimportuj numpy jako np

DLA INDEKSU

S=[11,2,44,55,66,0,10,3,33]

r=np.argsort(S)

[output]=array([5, 1, 7, 6, 0, 8, 2, 3, 4])

argsort Zwraca indeksy S w posortowanej kolejności

DLA WARTOŚCI

np.sort(S)

[output]=array([ 0,  2,  3, 10, 11, 33, 44, 55, 66])
negi
źródło
0

Utworzymy kolejną tablicę indeksów od 0 do n-1, następnie spakujemy ją do oryginalnej tablicy, a następnie posortujemy na podstawie oryginalnych wartości

ar = [1,2,3,4,5]
new_ar = list(zip(ar,[i for i in range(len(ar))]))
new_ar.sort()

`

Jai dewani
źródło