algorithm - 您将如何在 CUDA 中实现此功能？ (排序整数向量中的偏移量)

Question

我的设备上有一个排序的整数数组，例如:

[0,0,0,1,1,2,2]

我想要另一个数组中每个元素的偏移量:

[0,3,5]

(因为第一个 0 在位置 0，第一个 1 在位置 3 等等)我事先知道会有多少不同的元素。你将如何在 CUDA 中有效地实现它？我不是要代码，而是要对您要实现以计算此转换的算法进行高级描述。我已经看过 thrust namespace 中的各种函数，但想不出任何 thrust 函数的组合来实现这一点。另外，这个转换是否有一个被广泛接受的名称？

Answer 1

您可以在 Thrust 中使用 thrust::unique_by_key_copy 和 thrust::counting_iterator 来解决这个问题。这个想法是将您的整数数组视为 unique_by_key_copy 的 keys 参数，并使用一系列递增的整数(即 counting_iterator)作为值。 unique_by_key_copy 会将 values 数组压缩到每个唯一 key 的索引中:

#include <thrust/device_vector.h>
#include <thrust/iterator/counting_iterator.h>
#include <thrust/iterator/discard_iterator.h>
#include <thrust/unique.h>
#include <thrust/copy.h>
#include <iterator>
#include <iostream>

int main()
{
  thrust::device_vector<int> keys(7);
  keys[0] = 0; keys[1] = 0; keys[2] = 0;
  keys[3] = 1; keys[4] = 1; keys[5] = 2; keys[6] = 2;

  std::cout << "keys before unique_by_key_copy: [ ";
  thrust::copy(keys.begin(), keys.end(), std::ostream_iterator<int>(std::cout," "));
  std::cout << "]" << std::endl;

  thrust::device_vector<int> offsets(3);

  thrust::unique_by_key_copy(keys.begin(), keys.end(),          // keys
                             thrust::make_counting_iterator(0), // [0, 1, 2, 3, ...] are the values
                             thrust::make_discard_iterator(),   // discard the compacted keys
                             offsets.begin());                  // the offsets are the values

  std::cout << "offsets after unique_by_key_copy: [ ";
  thrust::copy(offsets.begin(), offsets.end(), std::ostream_iterator<int>(std::cout," "));
  std::cout << "]" << std::endl;

  return 0;
}

这是输出:

$ nvcc test.cu -run
keys before unique_by_key_copy: [ 0 0 0 1 1 2 2 ]
offsets after unique_by_key_copy: [ 0 3 5 ]