Geek asks and answers

Simplified vector search: Combine lower_bound and binary_search efficiently to find both position and existence

I am trying to use Thrust to determine if each element of an array can be found in another array and where (both arrays are sorted). I came across vectorized search procedures (lower_bound and binary_search).

lower_bound will return for each value an index into which it can be inserted into a list corresponding to its order.

I also need to know if a value is found or not (which can be done using binary_search), and not just by its position.

Is it possible to achieve efficiency efficiently without having to execute two queries (by calling binary_ source and then lower_bound)?

I know that in the scalar case lower_bound will return a pointer to the end of the array if the value cannot be found, but this does not happen in the vectorized version.

Thank!

+5
source share
2 answers

You can verify that the item returned lower_boundis the one you were looking for. For instance. given a = {1,3,5}and search b = {1,4}, the result will be c = {0,2}. We have a[c[0]] == b[0], therefore, b[0]is in a, but a[c[1]] != b[1], therefore, is b[1]not in a.

(Note that you will need to make sure that you are not making any memory accesses outside the limits, as it lower_boundmay return an index that is outside the array.)

+2
source

@tat0: Arrayfire: 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);

: : 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 , Compute 3.0 (single, double)

: 1937 ( 2048 )

: 0.13008

arrayfire: 0.06702

0

More articles:


All Articles