サブアレイインデックスのリストで配列を分割する

Question

配列Xと、インデックスのリストk_ar（最大値はK - 1）を持っているとします。私がやりたいことはX[i]がサブアレイk_ar[i]に入るようにXを基本的に分割され

。これはこの種のものを行うには理想的なアルゴリズムですがnumpyの、scipyのダウンロードまたは他のライブラリがそれを行うためのより高速な方法を持っていた場合、私は思っていた

X = [5, 1, 3, 2, 2, 1] 

k_ar = [0, 1, 0, 1, 2] 

K = max(k_ar) + 1 

sub_X = [[] for k in range(K)] 

for k, x in zip(k_ar, X): 
    sub_X[k].append(x) 

：これを行うにはO(n)方法は、次のようになります。私は、例えば、この操作を行うことができ、それはnで非常に高速なものの、O(nK)代わりのO(n)、および大規模Kのためので、最適です：だから

import numpy as np 

X = np.ndarray([5, 1, 3, 2, 2, 1], dtype=np.int8) 

k_ar = np.ndarray([0, 1, 1, 0, 1, 2], dtype=np.int8) 

K = max(k_ar) 

sub_X = np.empty(K, dtype=np.ndarray) 

for k in range(K): 
    sub_X[k] = X[k_ar == k] 

、再び、これを高速化する方法があります例えば、 Numba、Cython、PyPy？

Answer 1

あなたのアルゴリズムはむしろO（n）です：最大必要回数nステップの繰り返し、リスト作成の繰り返しはnステップ、配置の繰り返しはnステップもあります。

また、繰り返し中に元のリストとインデックスをそのまま残す理由があるかどうかはわかりません。これは、ポップして2nではなくn個の要素にメモリを保持できることを意味します。

最終的なコード - O（n）のメモリ、O（n）のCPU：

X = [5, 1, 3, 2, 2, 1] 
k_ar = [0, 1, 0, 1, 2] 
sub_x = [] 
while X: 
    k = k_ar.pop() 
    try: 
     sub_x[k].append(X.pop()) 
    except IndexError: 
     sub_x.extend([] for i in range(len(sub_x), k+1)) 
     sub_x[k].append(X.pop())