39

セルフインデックス（これが正しい用語かどうかはわかりません）のnumpy配列が与えられた場合、次に例を示します。

a = np.array([3, 2, 0, 1])

これは、この順列を表します（=>矢印です）。

0 => 3
1 => 2
2 => 0
3 => 1

Pythonで「手動」で逆変換を行わずに、逆変換を表す配列を作成しようとしています。つまり、純粋なnumpyソリューションが必要です。上記の場合に必要な結果は次のとおりです。

array([2, 3, 1, 0])

これは

0 <= 3                0 => 2
1 <= 2       or       1 => 3
2 <= 0                2 => 1
3 <= 1                3 => 0

とてもシンプルに見えますが、どうすればいいのかわからないです。グーグルを試しましたが、関連するものは見つかりませんでした。

4

3 に答える 3

52

ここでは、並べ替えはやり過ぎです。 これは、一定のメモリ要件を持つシングルパスの線形時間アルゴリズムです。

from __future__ import print_function
import numpy as np

p = np.array([3, 2, 0, 1])
s = np.empty(p.size, dtype=np.int32)
for i in np.arange(p.size):
    s[p[i]] = i

print('s =', s)

上記のコードは

 s = [2 3 1 0]

要求に応じ。

for残りの答えは、上記のループの効率的なベクトル化に関するものです。解決策を知りたいだけの場合は、この回答の最後にジャンプしてください。

（2014年8月27日からの元の回答。タイミングはNumPy 1.8で有効です。NumPy1.11での更新は後で続きます。）

np.argsortシングルパスの線形時間アルゴリズムは、 ;よりも高速であると予想されます。興味深いことに、上記のループの簡単なベクトル化（s[p] = xrange(p.size)、インデックス配列を参照for）は、実際には、次の場合よりもわずかに遅くなりますnp.argsort（p.size < 700 000私のマシンでは、マイレージは異なります）。

import numpy as np

def np_argsort(p):
    return np.argsort(p)

def np_fancy(p):
    s = np.zeros(p.size, p.dtype) # np.zeros is better than np.empty here, at least on Linux
    s[p] = xrange(p.size) 
    return s

def create_input(n):
    np.random.seed(31)
    indices = np.arange(n, dtype = np.int32)
    return np.random.permutation(indices)

IPythonノートブックから：

p = create_input(700000)
%timeit np_argsort(p)
10 loops, best of 3: 72.7 ms per loop
%timeit np_fancy(p)
10 loops, best of 3: 70.2 ms per loop

最終的に、漸近的な複雑さが始まり（シングルパスアルゴリズムの場合と比較して）、シングルパスアルゴリズムは十分に大きくなると一貫して高速になります（私のマシンではしきい値は約700kです）O(n log n)。argsortO(n)n = p.size

ただし、上記のforループをnp.put次のようにベクトル化する簡単な方法はありません。

def np_put(p):
    n = p.size
    s = np.zeros(n, dtype = np.int32)
    i = np.arange(n, dtype = np.int32)
    np.put(s, p, i) # s[p[i]] = i 
    return s

これはn = 700 000（上記と同じサイズ）を与えます：

p = create_input(700000)
%timeit np_put(p)
100 loops, best of 3: 12.8 ms per loop

これは、5.6倍のスピードアップで、ほとんど何もありません。

公平を期すために、それでも小さい方np.argsortのアプローチを打ち負かします（転換点は私のマシンの周りにあります）：np.putnn = 1210

p = create_input(1210)
%timeit np_argsort(p)
10000 loops, best of 3: 25.1 µs per loop
%timeit np_fancy(p)
10000 loops, best of 3: 118 µs per loop
%timeit np_put(p)
10000 loops, best of 3: 25 µs per loop

np.arange()これは、アプローチで（呼び出し時に）追加の配列を割り当てて入力するためである可能性がありnp_putます。

好奇心から、Cythonソリューションを要求しなかったのですが、私は次のCythonソリューションのタイミングをタイプされたmemoryviewsで設定しました。

import numpy as np
cimport numpy as np

def in_cython(np.ndarray[np.int32_t] p):    
    cdef int i
    cdef int[:] pmv
    cdef int[:] smv 
    pmv = p
    s = np.empty(p.size, dtype=np.int32)
    smv = s
    for i in xrange(p.size):
        smv[pmv[i]] = i
    return s

タイミング：

p = create_input(700000)
%timeit in_cython(p)
100 loops, best of 3: 2.59 ms per loop

したがって、np.putソリューションはまだ可能な限り高速ではありません（この入力サイズで12.8ミリ秒実行されました。argsortは72.7ミリ秒かかりました）。

2017年2月3日にNumPy1.11で更新

Jamie、Andris、Paulは、以下のコメントで、ファンシーインデックスのパフォーマンスの問題が解決されたことを指摘しました。ジェイミーはそれがNumPy1.9ですでに解決されたと言います。2014年に使用していたマシンでPython3.5とNumPy1.11を使用してテストしました。

def invert_permutation(p):
    s = np.empty(p.size, p.dtype)
    s[p] = np.arange(p.size)
    return s

タイミング：

p = create_input(880)
%timeit np_argsort(p)
100000 loops, best of 3: 11.6 µs per loop
%timeit invert_permutation(p)
100000 loops, best of 3: 11.5 µs per loop

確かに大幅な改善！

結論

全体として、私は

def invert_permutation(p):
    '''The argument p is assumed to be some permutation of 0, 1, ..., len(p)-1. 
    Returns an array s, where s[i] gives the index of i in p.
    '''
    s = np.empty_like(p)
    s[p] = np.arange(p.size)
    return s

コードを明確にするためのアプローチ。私の意見では、それはよりも曖昧さが少なくargsort、大きな入力サイズの場合も高速です。速度が問題になる場合は、Cythonソリューションを使用します。

于 2014-08-27T19:42:59.720 に答える
36

の順列の逆は、pソートするインデックスnp.arange(n)の配列です。sp

p[s] == np.arange(n)

すべて真でなければなりません。そのようなsものはまさにnp.argsort返されるものです：

>>> p = np.array([3, 2, 0, 1])
>>> np.argsort(p)
array([2, 3, 1, 0])
>>> p[np.argsort(p)]
array([0, 1, 2, 3])
于 2012-07-25T12:40:25.620 に答える
11

larsmansの正解にもう少し背景を提供したいと思います。行列による順列の表現を使用すると、正しい理由argsortを見つけることができます。置換行列の数学的な利点は、行列が「ベクトルで動作する」ことです。つまり、置換行列にベクトルを掛けたものがベクトルを置換します。 P

あなたの順列は次のようになります：

import numpy as np
a   = np.array([3,2,0,1])
N   = a.size
rows = np.arange(N)
P   = np.zeros((N,N),dtype=int)
P[rows,a] = 1

[[0 0 0 1]
 [0 0 1 0]
 [1 0 0 0]
 [0 1 0 0]]

順列行列が与えられると、その逆行列を乗算することにより、乗算を「元に戻す」ことができP^-1ます。置換行列の利点は、それらが直交していることです。P*P^(-1)=IつまりP(-1)=P^T、逆行列は転置です。これは、転置行列のインデックスを使用して、逆順列ベクトルを見つけることができることを意味します。

inv_a = np.where(P.T)[1]
[2 3 1 0]

あなたがそれについて考えるならば、これはP！の列をソートするインデックスを見つけることとまったく同じです。

于 2012-07-25T13:52:06.410 に答える