numpyのin1dマスク関数より優れた処理をする：順序付けられた配列？

Question

この操作は、数百万の要素を含む実際の配列と同じくらい速く適用する必要があります。これは簡単な問題のバージョンです。

したがって、私はのユニークなの整数（通常は何百万という要素）のランダム配列を持っています。

totalIDsの= [5,4,3,1,2,9,7,6,8 ...]私は（通常は数十万の）一意の整数の別の配列を持っている

私はマスクを作ることができます。私は

マスク= np.in1d（totalIDs、subsampleIDs、assume_unique =真）

を行うためにnumpyのを使用することができます

subsampleIDs1 = [5,1,9] 
subsampleIDs2 = [3,7,8] 
subsampleIDs3 = [2,6,9] 
... 

私はその後、別の配列の私が欲しい情報を抽出することができますマスクを使用して（たとえば、カラム0には必要なものが含まれています）。

可変=のallvariables [マスク] [:, 0]次にIDが両方の配列内で一意であることを所与

は、有意にこれをスピードアップする方法があります。数百万のID（totalID）に一致する数千ポイント（サブサンプルID）のマスクを構築するには、長い時間がかかります。

私はそれを一度行って、インデックスのバイナリファイルを書き出すことを考えました（将来の検索を高速化するため）。

for i in range(0,3): 
    mask = np.in1d(totalIDs,subsampleIDs,assume_unique=True) 
    index[mask] = i 

ここで、XはサブサンプルID Xである。それでは、私はできるだけ：

for i in range(0,3): 
    if index[i] == i: 
     rowmatch = i 
     break 

variable = allvariables[rowmatch:len(subsampleIDs),0] 

右か？しかし、これは遅いです。なぜなら、最初に一致するときに見つけるループの条件があるからです。条件付きでループを遅らせることがないように、番号が最初に順序付けられた配列に現れたときに、より速く発見する方法はありますか？

Answer 1

私はあなたがパンダにデータフレームを使用することをお勧め。 DataFrameのインデックスはtotalIDで、サブサンプルIDはdf.ix[subsampleIDs]で選択できます。

最初のいくつかのテストデータを作成します。

import numpy as np 
N = 2000000 
M = 5000 
totalIDs = np.random.randint(0, 10000000, N) 
totalIDs = np.unique(totalIDs) 
np.random.shuffle(totalIDs) 
v1 = np.random.rand(len(totalIDs)) 
v2 = np.random.rand(len(totalIDs)) 

subsampleIDs = np.random.choice(totalIDs, M) 
subsampleIDs = np.unique(subsampleIDs) 
np.random.shuffle(subsampleIDs) 

を次にDATAFRAMEにしてあなたのデータを変換します

import pandas as pd 
df = pd.DataFrame(data = {"v1":v1, "v2":v2}, index=totalIDs) 
df.ix[subsampleIDs] 

DATAFRAMEはそれが場所だし、インデックスをマッピングするハッシュテーブルを使用し、それは非常に高速です。

Answer 2

この種の索引付けは、しばしばDB（適切な列索引付けを使用）を使用して実行するのが最善です。

もう1つのアイデアは、前処理段階としてtotalIDsを一度ソートし、独自のバージョンのin1dを実装することで、すべてのソートを回避します。 in1dのnumpyの実装（少なくとも私がインストールしたバージョンでは）はかなり簡単で、簡単にコピーして変更することができます。

EDIT：

または、より良い、利用バケットソート（または基数ソート）。それはあなたにO（N + M）、NはtotalIDsのサイズ、MはsampleIDs（バケツの数を変えることで遊ぶことができる時間）のサイズを与えます。ここでも、totalIDsをバケットに1回だけ分割することができます。これにより、O（N + M1 + M2 + ...）という気分になります。

残念ながら、私はnumpyの実装を認識していないんだけど、私はこれを見つけた：http://en.wikipedia.org/wiki/Radix_sort#Example_in_Python