9

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

したがって、一意の整数 (通常は数百万の要素)のランダムな配列があります。

totalIDs = [5,4,3,1,2,9,7,6,8 ...]

マスクを作成できる一意の整数の別の配列 (通常は数万) があります。

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

numpy を使用して行うことができます

mask = np.in1d(totalIDs,subsampleIDs,assume_unique=True)

次に、マスクを使用して別の配列から必要な情報を抽出できます (たとえば、必要な情報が列 0 に含まれているとします)。

variable = allvariables[マスク][:,0]

ID が両方のアレイで一意であることを考えると、これを大幅に高速化する方法はありますか。数百万の ID (totalID) と一致する数千のポイント (subsampleID) のマスクを作成するには、長い時間がかかります。

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

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

ここで、X は subsampleIDsX にあります。次に、次のことができます。

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

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

右？ただし、最初に一致するタイミングを見つけるための条件がループ内にあるため、これも遅くなります。条件がループを遅くしないように、番号が順序付けられた配列に最初に表示されたときを見つけるためのより高速な方法はありますか?

4

2 に答える 2

3

PandasでDataFrameを使用することをお勧めします。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はハッシュテーブルを使用してインデックスをその場所にマップします。これは非常に高速です。

于 2013-03-08T02:36:16.073 に答える
1

多くの場合、この種のインデックス作成は、DB を使用して (適切な列インデックスを使用して) 実行するのが最適です。

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

編集：

または、さらに良いことに、バケット ソート (または基数ソート) を使用します。これにより、O(N+M) が得られます。N は のサイズでtotalIDs、M はsampleIDs(バケットの数を変更して操作できる定数の倍数) のサイズです。ここでも、バケツに分割できるtotalIDsのは 1 回だけで、気の利いた O(N+M1+M2+...) が得られます。

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

于 2013-03-07T19:36:45.603 に答える