推力ベクトル化検索：lower_boundとbinary_searchを効率的に組み合わせて位置と存在の両方を見つける

Question

私は推力を使って、配列の各要素が別の配列で見つけられるかどうか（両方の配列がソートされているか）を検出しようとしています。私はベクトル化された検索ルーチン（lower_boundとbinary_search）を見つけました。

lower_boundは、各値に対して、その順序を考慮してリストに挿入できるインデックスを返します。

また、その位置だけでなく、値が見つかったかどうか（binary_searchで行うこともできます）を知る必要があります。

2回の検索（binary_searchを呼び出してからlower_boundを呼び出す）を行うことなく、両方を効率的に達成できますか？

スカラーの場合、lower_boundは値が見つからない場合は配列の最後のポインタを返しますが、ベクトル化されたバージョンでは発生しません。

ありがとうございます！

Answer 1

lower_boundが返す要素が、検索した要素と同じであることを確認できます。例えば。 a = {1,3,5}を指定し、b = {1,4}を検索すると、結果はc = {0,2}になります。我々はa[c[0]] == b[0]を持っているので、b[0]はaであるが、a[c[1]] != b[1]だからb[1]はaではない。

（あなたはlower_boundは、配列の最後を超えてインデックスを返すことができますので、あなたは、任意の範囲外のメモリアクセスを行わないようにする必要がありますのでご注意ください。）

Answer 2

をtat0 @： arrayfireに、あなたが直接、2つの配列の「交差点」を取得）LOWER_BOUNDを使用して ベクトル化された検索（）（setintersectですぐに ながら、あなたに答えを与えるものではありません：あなたもArrayfireで遊ぶことができます

float A_host[] = {3,22,4,5,2,9,234,11,6,17,7,873,23,45,454}; 
int szA = sizeof(A_host)/sizeof(float); 

float B_host[] = {345,5,55,6,7,8,19,2,63}; 
int szB = sizeof(B_host)/sizeof(float); 

// initialize arrays from host data 
array A(szA, 1, A_host); 
array B(szB, 1, B_host); 

array U = setintersect(A, B); // compute intersection of 2 arrays 

int n_common = U.elements(); 
std::cout << "common: ";  
print(U); 

出力は次のとおりです。 common：U = 2.0000 5.0000 6.0000 7.0000

配列Aにおけるこれらの要素の実際の位置を得るために、あなたは（Aの要素が一意であることを提供する）は、次の 構文を使用できます。その後、

int n_common = U.elements(); 
array loc = zeros(n_common); // empty array  

gfor(array i, n_common) // parallel for loop 
    loc(i) = sum((A == U(i))*seq(szA)); 
print(loc); 

を：LOC = 4.0000 3.0000 8.0000 10.0000

さらに、推力:: LOWER_BOUNDは（））（setintersectよりも遅くなるように思われます、 私は次のプログラムでそれをベンチマーク：

int *g_data = 0; 
int g_N = 0; 

void thrust_test() { 
thrust::device_ptr<int> A = thrust::device_pointer_cast((int *)g_data), 
    B = thrust::device_pointer_cast((int *)g_data + g_N); 
thrust::device_vector<int> output(g_N); 
thrust::lower_bound(A, A + g_N, B, B + g_N, 
        output.begin(), 
        thrust::less<int>()); 
std::cout << "thrust: " << output.size() << "\n"; 
} 
void af_test() 
{ 
    array A(g_N, 1, g_data, afDevicePointer); 
    array B(g_N, 1, g_data + g_N, afDevicePointer); 
    array U = setintersect(A, B); 
    std::cout << "intersection sz: " << U.elements() << "\n"; 
} 
int main() 
{ 
    g_N = 3e6; // 3M entries 
    thrust::host_vector<int> input(g_N*2); 
    for(int i = 0; i < g_N*2; i++) { // generate some input 
    if(i & 1) 
     input[i] = (i*i) % 1131; 
    else 
     input[i] = (i*i*i-1) % 1223 ; 
} 
thrust::device_vector<int> dev_input = input; 
// sort the vector A 
thrust::sort(dev_input.begin(), dev_input.begin() + g_N); 
// sort the vector B 
thrust::sort(dev_input.begin() + g_N, dev_input.begin() + g_N*2); 
g_data = thrust::raw_pointer_cast(dev_input.data()); 
try { 
    info(); 
    printf("thrust: %.5f seconds\n", timeit(thrust_test)); 
    printf("af: %.5f seconds\n", timeit(af_test)); 
} catch (af::exception& e) { 
    fprintf(stderr, "%s\n", e.what()); 
} 
return 0; 
} 

および結果：

CUDAツールキット4.2、ドライバ295.59

GPU0のGeForce GT 650M、2048メガバイト、計算3。0（シングル、ダブル）

メモリ使用量：1937メガバイト無料（2048メガバイトの合計）

推力：0.13008秒

arrayfire：0.06702秒