c++ - 排序 vector 的交集

Question

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

我使用的是 gcc-4.9.2

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

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

提前非常感谢

Answer 1

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

使用 SIMD 也可以(有效地)做到这一点。我会使用内在函数或 SIMD vector 类显式地执行此操作。

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