3

何千もの値を含む巨大なデータ ポイント セットで極大値を見つける最も効率的な方法を取得したいと考えています。入力として、x と y の値を持つ 2 つの長いリストが使用されます。

次の簡単な例を考えてみましょう。

xval = [-0.15, -0.02, 0.1, 0.22, 0.36, 0.43, 0.58, 0.67, 0.79, 0.86, 0.96 ]

yval = [-0.09, 0.13, -0.01, -0.1, -0.05, 0.2, 0.56, 0.47, 0.35, 0.43, 0.69]

ここに画像の説明を入力

目的の出力は、ピーク ポイントのインデックスを含むリストです。ここでは locMaxId =[1,6,10] です。最も近い隣人を比較することは解決策ですが、10kの値の場合は?

4

1 に答える 1

4

numpy に反復を処理させる、つまりベクトル化することができます。

def local_maxima(xval, yval):
    xval = np.asarray(xval)
    yval = np.asarray(yval)

    sort_idx = np.argsort(xval)
    yval = yval[sort_idx]
    gradient = np.diff(yval)
    maxima = np.diff((gradient > 0).view(np.int8))
    return np.concatenate((([0],) if gradient[0] < 0 else ()) +
                          (np.where(maxima == -1)[0] + 1,) +
                          (([len(yval)-1],) if gradient[-1] > 0 else ()))

EDITしたがって、コードは最初にすべてのポイントから nex( gradient) までの変動を計算します。次のステップは少しトリッキーです...そうするとnp.diff((gradient > 0)、結果のブール配列は、成長する（ ）から成長しない（ ）にTrue変化する場所です。boolean配列と同じサイズのsigned intにすることで、成長から非成長への遷移( )とその逆​​( )を区別​​することができます。ブール配列と同じ dtype サイズの符号付き整数型を取得することで、データのコピーを回避できます。> 0<= 0-1+1.view(np.int8).astype(int). あとは、最初と最後の点を処理し、すべての点を 1 つの配列に連結するだけです。今日わかったことの 1 つは、 に送信するタプルに空のリストを含めるとnp.concatenate、 dtype の空の配列として出力np.floatされ、結果の dtype になるため、空のタプルの連結がより複雑になることです。上記のコードで。

できます：

In [2]: local_maxima(xval, yval)
Out[2]: array([ 1,  6, 10], dtype=int64)

そしてかなり速いです：

In [3]: xval = np.random.rand(10000)

In [4]: yval = np.random.rand(10000)

In [5]: local_maxima(xval, yval)
Out[5]: array([   0,    2,    4, ..., 9991, 9995, 9998], dtype=int64)

In [6]: %timeit local_maxima(xval, yval)
1000 loops, best of 3: 1.16 ms per loop

また、ほとんどの場合、データをリストから配列に変換して並べ替えています。データが既にソートされ、配列に保持されている場合、おそらく上記のパフォーマンスを 5 倍向上させることができます。

于 2013-07-28T14:04:28.650 に答える