已排序向量的交集

Question

我知道可以使用 std::set_intersection() 执行两个排序向量或集合之间的交集。是否可以使用 openMP 4.0 SIMD 执行相同的集合交集。我需要在我的代码中多次执行两个排序向量之间的集合交集，所以 c++ set_intersection() 原来是这里的瓶颈（由 perf 工具识别）。是否可以使用 SIMD 执行 set_intersection 以加速大向量之间的集合交集。如果是，那又如何？

我正在使用 gcc-4.9.2

我需要在两个排序的向量之间执行交集——其中第一个向量的大小最多为 1,000，第二个向量的大小最多为 10,000 个元素。

如果无法使用 openMP 4.0 SIMD 执行 set_intersection，那么是否可以使用 Boost SIMD 进行集合交集。如果是，那么如何。

非常感谢

Answer 1

下面是我整理的一些 OpenMP 代码，用于查找两个排序集的交集。合并结果时可以在没有关键部分的情况下执行此操作（以及合并它们并行排序）但我没有在这里这样做。

使用 SIMD（高效）也可能做到这一点。我会明确地使用内部或 SIMD 向量 class.

size_t intersect_scalar_omp(int *A, int *B, size_t s_a, size_t s_b, int *C) {
    size_t counter = 0;
    #pragma omp parallel
    {
        size_t i_a = 0, i_b = 0;
        size_t aend = s_a, bend = s_b;
        size_t counter_private = 0;
        int ithread = omp_get_thread_num();
        int nthreads = omp_get_num_threads();   

        if (s_a > s_b) {
            i_a = ithread*s_a / nthreads;
            aend = (ithread + 1)*s_a / nthreads;            
        }
        else {
            i_b = ithread*s_b / nthreads;
            bend = (ithread + 1)*s_b / nthreads;
        }
        int *C_private = new int[aend > bend ? aend : bend];
        while (i_a < aend && i_b < bend) {
            if (A[i_a] < B[i_b]) {
                i_a++;
            }
            else if (B[i_b] < A[i_a]) {
                i_b++;
            }
            else {
                C_private[counter_private++] = A[i_a];
                i_a++; i_b++;
            }
        }
        #pragma omp critical
        {
            memcpy(&C[counter], C_private, sizeof(int)*counter_private);
            counter += counter_private;
        }
        delete[] C_private;
    }
    std::sort(C, C + counter);
    return counter;
}

已排序向量的交集

Intersection of sorted vectors

c++

openmp

simd