Pythonでソートされた配列のインデックスを取得する方法

2011年06月21日に質問されました。  ·  閲覧回数 223.4k回  ·  ソース

Gyan picture
2011年06月21日

私は数値リストを持っています:

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

ここで、このリストを並べ替えて[1, 2, 3, 5, 100]を取得するとします。 私が欲しいのは、ソートされた順序での元のリストからの要素のインデックスです。つまり、 [0, 1, 2, 4, 3] ---値とインデックスの両方を返すMATLABのソート関数です。

回答

Matthew Lewis picture
2012年09月19日
208

numpyを使用している場合は、argsort()関数を使用できます。

>>> import numpy
>>> numpy.argsort(myList)
array([0, 1, 2, 4, 3])

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

これは、配列またはリストをソートする引数を返します。

Roman Bodnarchuk picture
2011年06月21日
155

次のようなもの:

>>> 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)は、(インデックス、値)のタプルを含むリストを提供します。

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

リストをsorted渡し、ソートキー(各タプルの2番目の要素。これがlambda目的です。最後に、それぞれの元のインデックス)を抽出する関数を指定することで、リストをソートします。ソートされた要素は、 [i[0] for i in ...]リスト内包表記を使用して抽出されます。

robert king picture
2011年06月21日
80
myList = [1, 2, 3, 100, 5]    
sorted(range(len(myList)),key=myList.__getitem__)

[0, 1, 2, 4, 3]
Ant6n picture
2013年07月23日
25

enumerateの答えは素晴らしいですが、私は個人的に、値でソートするために使用されるラムダが好きではありません。 以下は、インデックスと値を逆にして、それをソートするだけです。 したがって、最初に値でソートし、次にインデックスでソートします。

sorted((e,i) for i,e in enumerate(myList))
Nico Schlömer picture
2019年07月14日
13

perfplot (私のプロジェクト)を使用してこれらのパフォーマンスチェックを簡単に行ったところ、numpy以外のものを推奨するのは難しいことがわかりました(対数スケールに注意してください)。

enter image description here


プロットを再現するコード:

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)",
)
Matt picture
2011年06月21日
12

enumerateitemgetter回答を更新しました:

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

リストを一緒に圧縮します。タプルの最初の要素がインデックスになり、2番目が値になります(次に、タプルの2番目の値x[1]を使用して並べ替えます。xはタプルです)

または、 operatorモジュールからitemgetterを使用します `:

from operator import itemgetter
sorted(enumerate(a), key=itemgetter(1))
MSeifert picture
2019年08月18日
8

基本的にargsortを実行する必要があります。必要な実装は、外部ライブラリ(NumPyなど)を使用するか、依存関係のない純粋なPythonを維持するかによって異なります。

あなたが自分自身に尋ねる必要がある質問は:あなたは

  • 配列/リストをソートするインデックス
  • 要素がソートされた配列/リストに持つインデックス

残念ながら、質問の例では、どちらも同じ結果になるため、何が望ましいかが明確になりません。

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

argsort実装の選択

NumPyを自由に使用できる場合は、関数numpy.argsortまたはメソッドnumpy.ndarray.argsortます。

NumPyを使用しない実装は、他のいくつかの回答ですでに言及されているため、ここでベンチマークの回答に従って最速のソリューションを要約し

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

配列/リストをソートするインデックスを取得する

配列/リストを並べ替えるインデックスを取得するには、配列またはリストでargsortを呼び出すだけです。 ここではNumPyバージョンを使用していますが、Pythonの実装でも同じ結果が得られるはずです

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

結果には、ソートされた配列を取得するために必要なインデックスが含まれます。

ソートされた配列は[1, 2, 3, 4]ため、argsorted配列には、元の要素のこれらの要素のインデックスが含まれます。

  • 最小値は1で、元のインデックス1にあるため、結果の最初の要素は1です。
  • 2は元のインデックス2にあるため、結果の2番目の要素は2です。
  • 3は元のインデックス0にあるため、結果の3番目の要素は0です。
  • 最大値4であり、元のインデックス3にあるため、結果の最後の要素は3です。

要素がソートされた配列/リストに持つインデックスを取得する

この場合、 argsort 2回適用する必要があります。

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

この場合 :

  • 元の要素の最初の要素は3 、これは3番目に大きい値であるため、並べ替えられた配列/リストにインデックス2が含まれるため、最初の要素は2ます。
  • 元の要素の2番目の要素は1 。これは最小値であるため、並べ替えられた配列/リストにインデックス0が含まれるため、2番目の要素は0ます。
  • オリジナルの3番目の要素は2 、これは2番目に小さい値であるため、並べ替えられた配列/リストにインデックス1が含まれるため、3番目の要素は1ます。
  • 元の要素の4番目の要素は4で、これが最大値であるため、並べ替えられた配列/リストにインデックス3が含まれるため、最後の要素は3ます。
mab picture
2018年04月25日
7

numpyを使用したくない場合は、

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

ここに示さです

shahar_m picture
2019年05月14日
5

他の答えは間違っています。

argsort 1回実行することは、解決策ではありません。 たとえば、次のコード:

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

array([1, 2, 0], dtype=int64)が生成されますが、これは私たちが望んでいるものではありません。

答えは、 argsort 2回実行することです。

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

期待どおりにarray([2, 0, 1], dtype=int64)を与えます。

Jai dewani picture
2019年08月01日
1

0からn-1までのインデックスの別の配列を作成します。次に、これを元の配列に圧縮し、元の値に基づいて並べ替えます。

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

`