Pythonリストで重複を効率的に処理する

Question

私はPythonリスト/ 1D numpy配列で重複をコンパクトに表現しようとしています。例えば、我々は

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

この配列は、特定のクラスタ内のすべての重複がx[group_id==<some_id>]で発見されたように、

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

で表すことができ、いくつかの重複要素を持っている持っていると言います。

重複ペアのリストを効率的に選別して計算することができる、

s_idx = np.argsort(x) 
diff_idx = np.nonzero(x[s_idx[:-1]] == x[s_idx[1:]])[0] 

ここ一対s_idx[diff_idx] < - >s_idx[diff_idx+1]は重複している元の配列内のインデックスに対応します。 （ここではarray([1, 2, 3]) < - >array([2, 5, 4])）。

しかし、大きな配列サイズ（N > 10⁶）のこのリンケージ情報からcluster_idを効率的に計算する方法がわかりません。

編集：@Chris_Randsにより示唆されるように、これは確かにitertools.groupbyで行うことができ、

import numpy as np 
import itertools 

def get_group_id(x): 
    group_id = np.zeros(x.shape, dtype='int') 
    for i, j in itertools.groupby(x): 
     j_el = next(j) 
     group_id[x==j_el] = i 
    return group_id 

しかしスケーリングがはO（n^2）ように見える、これはないだろう（N > 10⁶）、

for N in [50000, 100000, 200000]: 
     %time _ = get_group_id(np.random.randint(0, N, size=N)) 

    CPU times: total: 1.53 s 
    CPU times: total: 5.83 s 
    CPU times: total: 23.9 s 

私はユースケースにスケールしましたN=200000の重複ペアの計算が比較でわずか6.44μsで済むので、より効率的です。

Answer 1

あなたはnumpy.uniqueを使用することができます。

In [13]: x = np.array([1, 0, 0, 3, 3, 0]) 

In [14]: values, cluster_id = np.unique(x, return_inverse=True) 

In [15]: values 
Out[15]: array([0, 1, 3]) 

In [16]: cluster_id 
Out[16]: array([1, 0, 0, 2, 2, 0]) 

（クラスタIDがソートされた一意の値の順に、入力しないで値の最初の出現順に割り当てられている。）

場所

In [22]: cid = 0 

In [23]: values[cid] 
Out[23]: 0 

In [24]: (cluster_id == cid).nonzero()[0] 
Out[24]: array([1, 2, 5]) 

Answer 2

ここでは麻痺の最初の出現に応じて順序を維持するためにnp.uniqueを使用してのアプローチがあります：クラスタ0内の項目のER -

unq, first_idx, ID = np.unique(x,return_index=1,return_inverse=1) 
out = first_idx.argsort().argsort()[ID] 

サンプル実行 -

In [173]: x 
Out[173]: array([1, 0, 0, 3, 3, 0, 9, 0, 2, 6, 0, 0, 4, 8]) 

In [174]: unq, first_idx, ID = np.unique(x,return_index=1,return_inverse=1) 

In [175]: first_idx.argsort().argsort()[ID] 
Out[175]: array([0, 1, 1, 2, 2, 1, 3, 1, 4, 5, 1, 1, 6, 7])