Búsqueda vectorizada de empuje: combine de manera eficiente lower_bound y binary_search para encontrar la posición y la existencia

Question

Estoy tratando de utilizar Thrust para detectar si cada elemento de una matriz se puede encontrar en otra matriz y dónde (ambas matrices están ordenadas). Encontré las rutinas de búsqueda vectorizada (lower_bound y binary_search).

lower_bound devolverá para cada valor el índice donde podría insertarse en una lista respetando su orden.

También necesito saber si se encuentra o no el valor (que se puede hacer con binary_search), no solo su posición.

¿Es posible lograr ambos de manera eficiente sin realizar dos búsquedas (llamando a binary_search y luego lower_bound)?

Sé en el caso escalar, lower_bound devolverá un puntero al final de la matriz si no se puede encontrar un valor, pero esto no ocurre en la versión vectorizada.

Gracias!

Answer 1

Puede verificar que el elemento que lower_bound devuelve es el mismo que el que buscó. P.ej. dado a = {1,3,5} y buscando b = {1,4}, el resultado será c = {0,2}. Tenemos a[c[0]] == b[0], entonces b[0] está en a, pero a[c[1]] != b[1] así que b[1] no está en a.

(Tenga en cuenta que tendrá que asegurarse de que usted no hace ninguna fuera de los límites accesos a la memoria, ya que lower_bound puede devolver un índice que está más allá del final de la matriz.)

Answer 2

@ tat0: también se puede jugar con Arrayfire: búsqueda vectorizado usando LOWER_BOUND() no le da la respuesta inmediatamente mientras que con setintersect() en arrayfire, se obtiene la "intersección" de dos matrices directamente:

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

la salida es: en común: U = 2.0000 5,0000 6,0000 7,0000

para obtener las ubicaciones reales de estos elementos en la matriz A, se puede utilizar el constructo siguiente (siempre que los elementos en A son únicos):

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

entonces: loc = 4,0000 3,0000 8,0000 10,0000

Por otra parte, el empuje :: límite distinto() parece ser más lento que setintersect(), i Benchmarked con el siguiente programa:

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

y los resultados:

CUDA toolkit 4.2, conductor 295,59

GPU0 GeForce GT 650M, 2048 MB, Compute 3.0 (simple, doble)

Uso

memoria: 1937 MB libre (2,048 MB total)

de empuje: 0.13008 segundos

arrayfire: 0.06702 segundos