Ricerca vettoriale spinta: Combina in modo efficiente lower_bound e binary_search per trovare sia posizione che esistenza

Question

Sto provando a utilizzare Thrust per rilevare se ogni elemento di un array può essere trovato in un altro array e dove (entrambi gli array sono ordinati). Mi sono imbattuto nelle routine di ricerca vettorizzate (lower_bound e binary_search).

lower_bound restituirà per ogni valore l'indice in cui potrebbe essere inserito in un elenco rispettando l'ordine.

Ho anche bisogno di sapere se il valore è trovato o meno (che può essere fatto con binary_search), non solo la sua posizione.

È possibile ottenere entrambi efficientemente senza effettuare due ricerche (chiamando binary_search e quindi lower_bound)?

Conoscendo il caso scalare, lower_bound restituirà un puntatore alla fine dell'array se non è possibile trovare un valore, ma ciò non accade nella versione vettoriale.

Grazie!

Answer 1

È possibile verificare che l'elemento restituito da lower_bound sia uguale a quello cercato. Per esempio. dato a = {1,3,5} e cercando b = {1,4}, il risultato sarà c = {0,2}. Abbiamo a[c[0]] == b[0], quindi b[0] è in a, ma a[c[1]] != b[1] quindi b[1] non è in a.

(Si noti che è necessario per garantire che non si fanno alcun out-of-bounds accessi alla memoria, dal momento che lower_bound può restituire un indice che è oltre la fine della matrice.)

Answer 2

@ Tat0: si può anche giocare con Arrayfire: ricerca vectorized utilizzando lower_bound() non ti dà la risposta immediatamente mentre con setintersect() in arrayfire, si ottiene il "bivio" di due array direttamente:

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 l'output è: comune: U = 2,0000 5,0000 6,0000 7,0000

per ottenere le posizioni effettive di questi elementi in array A, è possibile utilizzare il costrutto seguente (a condizione che elementi di A sono unici):

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

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

Inoltre, la spinta :: lower_bound() sembra essere più lento di setintersect(), i benchmark con il seguente programma:

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

ei risultati:

CUDA toolkit 4.2, conducente 295,59

GPU0 GeForce GT 650M 2048 MB, Calcola 3.0 (singole, doppie)

utilizzo della memoria: 1937 MB (2048 MB totali)

di spinta: 0.13008 secondi

arrayfire: 0.06702 secondi