Эффективный способ уменьшить подмножество вектора, используя тягу / куда

Question

Скажем, у нас есть вектор тяги устройства размером 10 ^ 16 и другой вектор размером 10 ^ 8, содержащий некоторые показатели (не обязательно отсортирован). Мы хотим суммировать все элементы первого вектора, если его индекс находится во втором векторе.

Наивным подходом для этого было бы использование transform_reduce of thrust. Тем не менее, я считаю, что это будет включать в себя итерацию по всем элементам первого вектора.

Есть ли эффективный способ?

Answer 1

Следуя предложению talonmies итератора перестановки, вот основная часть кода, которая реализует сокращение подмножества вектора. Я целенаправленно выбрал маленькие размеры вектора, чтобы объяснить идею. Для разумных размеров это быстрее, чем использование inner_product

    thrust::device_vector<double> vals(6);
    vals[0] = 2.0; vals[1] = 1.5; vals[2] = -1.2;
    vals[3] = 1.1; vals[4] = -4.3; vals[5] = 0.8;

    thrust::device_vector<int> indices(3);
    indices[0] = 1; indices[1] = 3; indices[2] = 5;

    thrust::device_vector<double> masks(6);

    for (auto elm:indices)
        masks[elm]=1.0;

    typedef thrust::device_vector<double>::iterator ValIterator;
    typedef thrust::device_vector<int>::iterator IndIterator;

    thrust::permutation_iterator<ValIterator, IndIterator> iter_begin(vals.begin(),
                                                                      indices.begin());
    thrust::permutation_iterator<ValIterator, IndIterator> iter_end(vals.end(),
                                                                    indices.end());

    double sum_reduce = thrust::reduce(iter_begin, iter_end);
    std::cout << "sum permutation iterator: " << sum_reduce << std::endl;

    double sum_inner_product = thrust::inner_product(vals.begin(), vals.end(),
                                                    masks.begin(), 0.0);
    std::cout << "sum inner product: " << sum_inner_product << std::endl;