6

2 つの 2D numpy 配列が与えられ、行数が同じであるとしますa。さらに、とのb各行iには共通の要素が 1 つしかないことがわかっていると仮定します。ただし、この要素は複数回発生する可能性があります。この要素をできるだけ効率的に見つけるにはどうすればよいでしょうか?ab

例：

import numpy as np

a = np.array([[1, 2, 3],
              [2, 5, 2],
              [5, 4, 4],
              [2, 1, 3]])

b = np.array([[4, 5],
              [3, 2],
              [1, 5],
              [0, 5]])

desiredResult = np.array([[np.nan],
                          [2],
                          [5],
                          [np.nan]])

intersect1d最初の軸に沿って適用することで、簡単に実装を考え出すことができます。

from intertools import starmap

desiredResult = np.array(list(starmap(np.intersect1d, zip(a, b))))

どうやら、python の組み込みの set 操作を使用するとさらに高速です。結果を目的の形式に変換するのは簡単です。

ただし、できるだけ効率的な実装が必要です。starmapしたがって、すべての行に対して python 呼び出しが必要だと思うので、私は好きではありません。純粋にベクトル化されたオプションが欲しいのですが、これが行ごとに共通の値が最大で 1 つあるという追加の知識を活用できれば幸いです。

タスクをスピードアップし、ソリューションをよりエレガントに実装する方法を知っている人はいますか? C コードや cython を使用してもかまいませんが、コーディングの手間はあまりかかりません。

4

3 に答える 3

5

アプローチ #1

これは、に基づいてベクトル化されたものですsearchsorted2d-

# Sort each row of a and b in-place
a.sort(1)
b.sort(1)

# Use 2D searchsorted row-wise between a and b
idx = searchsorted2d(a,b)

# "Clip-out" out of bounds indices
idx[idx==a.shape[1]] = 0

# Get mask of valid ones i.e. matches
mask = np.take_along_axis(a,idx,axis=1)==b

# Use argmax to get first match as we know there's at most one match
match_val = np.take_along_axis(b,mask.argmax(1)[:,None],axis=1)

# Finally use np.where to choose between valid match 
# (decided by any one True in each row of mask)
out = np.where(mask.any(1)[:,None],match_val,np.nan)

アプローチ #2

メモリ効率のための Numba ベースのもの -

from numba import njit

@njit(parallel=True)
def numba_f1(a,b,out):
    n,a_ncols = a.shape
    b_ncols = b.shape[1]
    for i in range(n):
        for j in range(a_ncols):
            for k in range(b_ncols):
                m = a[i,j]==b[i,k]
                if m:
                    break
            if m:
                out[i] = a[i,j]
                break
    return out

def find_first_common_elem_per_row(a,b):
    out = np.full(len(a),np.nan)
    numba_f1(a,b,out)
    return out

アプローチ #3

これは、スタッキングとソートに基づく別のベクトル化されたものです -

r = np.arange(len(a))
ab = np.hstack((a,b))
idx = ab.argsort(1)
ab_s = ab[r[:,None],idx]
m = ab_s[:,:-1] == ab_s[:,1:]
m2 = (idx[:,1:]*m)>=a.shape[1]
m3 = m & m2
out = np.where(m3.any(1),b[r,idx[r,m3.argmax(1)+1]-a.shape[1]],np.nan)

アプローチ #4

エレガントなものについてはbroadcasting、リソースを大量に消費するメソッドに利用できます-

m = (a[:,None]==b[:,:,None]).any(2)
out = np.where(m.any(1),b[np.arange(len(a)),m.argmax(1)],np.nan)
于 2019-07-05T05:30:19.753 に答える