6

Thrustを使用して、配列の各要素が別の配列で見つかるかどうか、およびどこにあるかを検出しようとしています(両方の配列がソートされています)。ベクトル化された検索ルーチン (lower_bound および binary_search) に出会いました。

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

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

2 つの検索 (binary_search を呼び出してから lower_bound を呼び出す) を行わずに両方を効率的に達成することは可能ですか?

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

ありがとう！

4

2 に答える 2

4

返された要素lower_boundが検索したものと同じであることを確認できます。たとえば、 を指定a = {1,3,5}して検索するb = {1,4}と、結果は になりますc = {0,2}。ありますがa[c[0]] == b[0]、そうではb[0]ありません。aa[c[1]] != b[1]b[1]a

lower_bound(配列の末尾を超えるインデックスを返す可能性があるため、範囲外のメモリ アクセスを行わないようにする必要があることに注意してください。)

于 2012-06-21T00:23:38.923 に答える
0

@tat0: Arrayfire をいじることもできます: lower_bound() を使用したベクトル化された検索ではすぐに答えが得られませんが、arrayfire で setintersect() を使用すると、2 つの配列の「交差」が直接得られます。

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);

出力は: 共通: 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

さらに、thrust::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 MB、Compute 3.0 (シングル、ダブル)

メモリ使用量: 1937 MB 空き (合計 2048 MB)

推力：0.13008秒

arrayfire: 0.06702 秒

于 2012-07-25T04:25:10.620 に答える