22

これが重複した質問である場合は事前に申し訳ありません。この情報を探しましたが、まだ見つかりませんでした。

N個の最大要素のインデックスを降順で非常に効率的に使用して、numpy配列(またはpythonリスト)を配置することは可能ですか?

たとえば、配列は次のとおりです。

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

降順の最大要素のインデックスは次のようになります (N = 6 を考慮すると、すべての要素が含まれます)。

8 --> 3

5 --> 4

4 --> 0

2 --> 5

1 --> 1

0 --> 2

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

私はややばかげたアプローチ（配列をソートし、インデックスのN個の数字のそれぞれを検索するなど）を使用してそれを作成する方法を知っていますが、ボトルネックやヒープqのような効率的なライブラリがあるかどうか、または作成するためのpythonicアプローチがあるかどうか疑問に思っていましたこれは非常に高速です。それぞれ 300k の要素を持ついくつかの配列に適用する必要があるため、パフォーマンスが問題になります。

前もって感謝します！

アップデート

私は答えを読んで、300kのランダムな整数を使用して時間を計ることにしました。結果は次のとおりです。

ソリューション 1: sorted(range(len(a)), key=lambda i:a[i]) 時間: 230 ミリ秒

解決策 2: heapq.nlargest(len(a), zip(a, itertools.count())) 時間: 396 ミリ秒

解決策 3: heapq.nlargest(len(a), enumerate(a), key=operator.itemgetter(1)) 時間: 864 ミリ秒

解決策 4: def f(a,N): return np.argsort(a)[::-1][:N] (N = len(a)) 時間: 104 ミリ秒

迅速で非常に良い回答をありがとうございます！

4

4 に答える 4

21

組み込みのnumpyargsortメソッドを見たことがありますか？：

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

この方法を使用すると、マシン上で約29ミリ秒で300,000個のランダムフロートを含む配列を並べ替えることができます。

def f(a,N):
    return np.argsort(a)[::-1][:N]
于 2012-10-08T18:58:31.097 に答える
11 
L = [4, 1, 0, 8, 5, 2]
sorted(range(len(L)), key=lambda i:L[i])
于 2012-10-08T18:52:38.200 に答える
6

heapqこれを十分に簡単に行うために使用できます。

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

タプルは、最初の値、次に 2 番目の値でソートすることによってソートされます。これは、値のインデックスを指定して、タプルとソートを簡単に作成できることを意味し(value, index)ます (値も指定されますが、簡単にスローできます)。これらは離れています）。

私はzip()and itertools.count()as enumerate を使用していると間違った順序になるため、値ではなくインデックスでソートされます。または、 を行うこともできますが((value, index) for index, value in enumerate(a))、それはあまり明確ではないと思います。

もう 1 つの方法は、 を実行してキーを指定することheapq.nlargest(3, enumerate(a), key=operator.itemgetter(1))です。

于 2012-10-08T18:52:58.320 に答える
1

heapq を使用する別の方法

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

他の場所でコメントされているように、 a が非常に大きくない限り、n<<len(a)Python ではソートが比較的高速な操作であるため、ソートに勝るものはありません。ただし、最終的には遅い O(n) は常に O(n*log(n)) を打ち負かします

于 2012-10-09T05:36:35.273 に答える