Thrust vektorisierte Suche: effizient kombinieren lower_bound und binary_search, um sowohl Position und Existenz zu finden

Question

Ich versuche Thrust zu verwenden, um festzustellen, ob jedes Element eines Arrays in einem anderen Array und wo (beide Arrays sind sortiert) gefunden werden kann. Ich stieß auf die vektorisierten Suchroutinen (lower_bound und binary_search).

lower_bound gibt für jeden Wert den Index zurück, wo er in eine Liste eingefügt werden könnte, die seine Reihenfolge berücksichtigt.

Ich muss auch wissen, ob der Wert gefunden wird oder nicht (was mit binary_search getan werden kann), nicht nur seine Position.

Ist es möglich, beide effizient zu erreichen, ohne zwei Suchen durchzuführen (Aufruf von binary_search und dann lower_bound)?

Ich weiß im unteren Fall, lower_bound wird einen Zeiger auf das Ende des Arrays zurückgeben, wenn ein Wert nicht gefunden werden kann, aber dies geschieht nicht in der vektorisierten Version.

Danke!

Answer 1

Sie können überprüfen, dass das Element, das lower_bound zurückgibt, dasselbe ist, das Sie gesucht haben. Z.B. gegeben a = {1,3,5} und Suche nach b = {1,4}, wird das Ergebnis c = {0,2} sein. Wir haben a[c[0]] == b[0], also b[0] ist in a, aber a[c[1]] != b[1] so b[1] ist nicht in a.

(Beachten Sie, dass Sie benötigen, um sicherzustellen, dass Sie machen keine out-of-bounds Speicherzugriffe, da lower_bound können einen Index zurück, die über das Ende des Arrays.)

Answer 2

@ tat0: vektorisiert Suche mit lower_bound() nicht geben Ihnen die Antwort sofort während mit setintersect() in arrayfire, Sie bekommen die „Kreuzung“ von zwei Arrays direkt:

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

die Sie können auch mit Arrayfire rumspielen Ausgabe ist: gemeinsam: U = 2.0000 5,0000 6,0000 7,0000

die tatsächlichen Positionen dieser Elemente in Array A zu erhalten, kann man die folgende Konstrukt verwenden (vorausgesetzt, dass Elemente in einer einzigartig sind):

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

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

Des Weiteren Schub :: lower_bound() scheint als setintersect langsamer zu sein(), i gebenchmarkt sie mit folgendem Programm:

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

und die Ergebnisse:

CUDA Toolkit 4.2-Treiber 295,59

GPU0 GeForce GT 650M, 2048 MB, Compute 3.0 (Einzel-, Doppel)

Speichernutzung: 1937 MB (2048 MB insgesamt)

Schub: 0,13008 Sekunden lang

arrayfire: 0,06702 Sekunden lang