Przeszukiwanie wektoryzacji ciągu: Efektywnie połącz funkcję niższą i pozycję binarną, aby znaleźć zarówno pozycję, jak i istnienie.

Question

Próbuję użyć ciągu, aby wykryć, czy każdy element tablicy można znaleźć w innej tablicy i gdzie (obie tablice są posortowane). Natknąłem się na wektorowe procedury wyszukiwania (lower_bound i binary_search).

lower_bound zwróci dla każdej wartości indeks, w którym może zostać wstawiony na liście, w odniesieniu do jego kolejności.

Potrzebuję również wiedzieć, czy wartość jest znaleziona, czy nie (co można zrobić z binary_search), a nie tylko jego pozycji.

Czy jest to możliwe, aby osiągnąć oba skutecznie, bez dwóch wyszukiwań (wywołanie binary_search, a następnie lower_bound)?

Wiem, że w przypadku skalarnym, lower_bound zwróci wskaźnik do końca tablicy, jeśli nie można znaleźć wartości, ale nie dzieje się to w wersji wektorowej.

Dzięki!

Answer 1

Możesz sprawdzić, czy element zwracany przez lower_bound jest taki sam jak ten, którego szukałeś. Na przykład. podając a = {1,3,5} i szukając b = {1,4}, wynikiem będzie c = {0,2}. Mamy a[c[0]] == b[0], więc b[0] jest w a, ale a[c[1]] != b[1], więc b[1] nie jest w a.

(Należy pamiętać, że trzeba będzie zapewnić, że nie robią żadnych out-of-granice pamięci dostępów, ponieważ lower_bound może powrócić indeks, który jest poza końcem tablicy.)

Answer 2

@ tat0: można również bawić się z Arrayfire: wektorowy wyszukiwania używając LOWER_BOUND() nie daje odpowiedzi natychmiast natomiast z setintersect() in arrayfire, masz „skrzyżowaniu” dwóch tablic bezpośrednio:

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

się wydajność: często: U = 2,0000 5,0000 6,0000 7,0000

uzyskać rzeczywiste rozmieszczenie tych elementów w tablicy A, można użyć następującego konstrukt (pod warunkiem, że elementy A są unikalne):

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

następnie: Loc = 4,0000 3,0000 8,0000 10,0000

Ponadto wzdłużne :: LOWER_BOUND() wydaje się być mniejsza niż setintersect() i odwzorować go z następującym programem:

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

i wyniki:

CUDA Toolkit 4.2, kierowca 295,59

GPU0 GeForce GT 650M, 2048 MB, Compute 3.0 (pojedyncze, podwójne)

Wykorzystanie pamięci 1937 MB wolnego (2048 MB całkowitej)

wzdłużne: 0.13008 sekund

arrayfire: 0.06702 sekund