中間インデックス配列を持たないnumpy配列から高速選択する方法

Question

次の2列配列では、最初の列の "edges"に対応する2番目の列から項目を選択します。現実の私のaには、何百万行もの可能性があるため、これは単なる例です。だから、理想的には、これをできるだけ早く行い、中間結果を作成しないでください。

import numpy as np 
a = np.array([[1,4],[1,2],[1,3],[2,6],[2,1],[2,8],[2,3],[2,1], 
       [3,6],[3,7],[5,4],[5,9],[5,1],[5,3],[5,2],[8,2], 
       [8,6],[8,8]]) 

すなわち私はここa[:,0]変化に対応しa[:,1]のエントリである

desired = np.array([4,6,6,4,2]) 

、結果を検索します。

一つの解決策は、np.array([6,6,4,2])を与える

b = a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1, 1] 

ですが、私は単純に、何の問題を最初の項目を付加することができませんでした。ただし、これにより、最初の項目のインデックスの中間配列が作成されます。私は、リストの内包表記を使用することにより中間体を避けることができます：

c = [a[i+1,1] for i,(x,y) in enumerate(zip(a[1:,0],a[:-1,0])) if x!=y] 

これも[6,6,4,2]を与えます。生成元ベースのzip（Python 3ではtrue）を仮定すると、これは中間表現を作成する必要はなく、非常にメモリ効率が良いはずです。しかし、内側のループはnumpyではなく、リストを生成する必要があります。リストをnumpyの配列に戻す必要があります。

メモリ効率がcで、速度効率がbのnumpy専用のバージョンがありますか？理想的には、a以上のパスが1回だけ必要です。

aが非常に大きい場合を除いて、スピードを測定してもそれほど役に立ちませんので、私はベンチマークを行うことを迷うことはありません。理論的に高速でメモリ効率の良いものがほしいと思っています。 。aの行をファイルからストリーミングとアクセスに遅いですしていると仮定 - bソリューションを避けるために別の理由、それはa上の第二ランダムアクセスパスを必要とする）

編集：大aを生成する方法試験用マトリックス：

from itertools import repeat 
N, M = 100000, 100 
a = np.array(zip([x for y in zip(*repeat(np.arange(N),M)) for x in y ], np.random.random(N*M))) 

Answer 1

ベクトル化された方法でこれを行うことを望んでいるのであれば、中間配列を避けることはできません。

ここでは、より効率的かもしれないnonzero()以外のベクトル化アプローチを見てみましょう。 (a[1:,0]-a[:-1,0])の元のコードと同じように差異化を実行するという同じ考え方で、「エッジ」またはシフトに対応する非ゼロの微分を探した後、ブールインデックスを使用することができます。

a[np.append(True,np.diff(a[:,0])!=0),1] 

ランタイム試験

原溶液a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1,1]最初の行をスキップするであろう -

したがって、我々はそうのようなベクトル化手法を有することになります。しかし、タイミング目的のためだけに言えば、それは有効な結果です。ここでは、この記事で提案された解決策に対するそれとのランタイムがあります -

In [118]: from itertools import repeat 
    ...: N, M = 100000, 2 
    ...: a = np.array(zip([x for y in zip(*repeat(np.arange(N),M))\ 
           for x in y ], np.random.random(N*M))) 
    ...: 

In [119]: %timeit a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1,1] 
100 loops, best of 3: 6.31 ms per loop 

In [120]: %timeit a[1:][np.diff(a[:,0])!=0,1] 
100 loops, best of 3: 4.51 ms per loop 

さて、あなたはあまりにも最初の行を含めたいとしましょう。

d = np.fromiter((a[i+1,1] for i,(x,y) in enumerate(zip(a[1:,0],a[:-1,0])) if x!=y), int) 

私はこれがないと思う：

In [123]: from itertools import repeat 
    ...: N, M = 100000, 2 
    ...: a = np.array(zip([x for y in zip(*repeat(np.arange(N),M))\ 
           for x in y ], np.random.random(N*M))) 
    ...: 

In [124]: %timeit a[np.append(0,(a[1:,0]-a[:-1,0]).nonzero()[0]+1),1] 
100 loops, best of 3: 6.8 ms per loop 

In [125]: %timeit a[np.append(True,np.diff(a[:,0])!=0),1] 
100 loops, best of 3: 5 ms per loop 

Answer 2

OK]をクリックして、実際に私はちょうど約np.fromiter、発電機に基づ​​いてnumpyの配列を構築することができたことを学んだ、解決策を見つけた - 更新ランタイムはこのようになりますこれは、中間配列を持たない配列が少ない配列を生成します。しかし、注意すべきことは、効率的であるとは思われないということです！テストに関する質問で私が言ったことを忘れる：

t = [lambda a: a[(a[1:,0]-a[:-1,0]).nonzero()[0]+1, 1], 
    lambda a: np.array([a[i+1,1] for i,(x,y) in enumerate(zip(a[1:,0],a[:-1,0])) if x!=y]), 
    lambda a: np.fromiter((a[i+1,1] for i,(x,y) in enumerate(zip(a[1:,0],a[:-1,0])) if x!=y), int)] 

from timeit import Timer 
[Timer(x(a)).timeit(number=10) for x in t] 

[0.16596235800034265, 1.811289312000099, 2.1662971739997374] 

最初の解決策は非常に速いようです！これは、中間データを生成しても内部ループをnumpyで完全に実行することができ、もう一方では配列の各項目に対してPythonコードを実行するためです。私はベンチマークのこの種は、ここに理にかなってわからないんだけど、なぜ

私が言ったように、これは - aははるかに遅かったにアクセスした場合、ベンチマークはCPUロードされるのではないでしょう。思考？

私は誰かがより速く何かを思い付くことができることを望んでいるので、この答えを受け入れていません。

Answer 3

メモリ効率が問題になる場合は、次のように解決できます。入力データと同じサイズの唯一の中間は、bool（a [1：、0]！= a [ -1、0]）;あなたの入力データがint32の場合、それは 'a'その8倍です。そのバイナリ配列のnonzerosを数えて出力配列をあらかじめ割り当てることもできます。ただし、！=の出力があなたの例が示唆するように疎である場合は、それほど重要ではありません。