如何使用CUDA/Thrust在一个数组中按值对两个数组/向量进行排序

Question

这是关于编程的概念问题。总结一下，我有两个数组/向量，需要对其中一个进行排序，同时在另一个数组中也进行相同的交换操作。我知道std::sort可以定义比较函数（针对自定义对象），我想定义一个函数来同时交换arrayTwo。

所以我的要求是：基于其中一个向量的值，使用CUDA对这两个向量进行排序。至于Thrust库是否支持自定义比较函数，我不确定，但如果支持的话，我还没有想到如何处理arrayTwo中的变化（因为它将基于CUDA）。

实际上，我没有时间在CUDA上实现自定义并行快速排序，尽管我应该/想要这样做。

原因是：我需要对一堆变量数组进行排序和计算，而不仅仅是单个数组（类似于回归树）。当然，我需要尽可能快地完成这些操作，CPU的排序速度太慢了。

更新：我应该强调的是，我没有问题在主机上对这两个数组进行排序，我正在寻找一个使用CUDA的解决方案。谢谢。

更新2：实际上，我发现自己很幸运，在发布问题后找到了解决方案，原来Thrust默认就提供了我需要的功能。

#include <thrust/sort.h>
  ...
  const int N = 6;
  int    keys[N] = {  1,   4,   2,   8,   5,   7};
  char values[N] = {'a', 'b', 'c', 'd', 'e', 'f'};
  thrust::sort_by_key(keys, keys + N, values);
  // keys is now   {  1,   2,   4,   5,   7,   8}
  // values is now {'a', 'c', 'b', 'e', 'f', 'd'}

*取自http://code.google.com/p/thrust/wiki/QuickStartGuide#Fancy_Iterators*

现在，我所要做的就是从这两个数组中获取两个thrust :: device_vectors（这两个数组来自2D数组）。 很高兴。

- Nisk

---

为什么不直接创建一个pair的向量，然后根据pair的第一个值进行排序呢？你可以为此目的向thrust::sort传递一个合适的谓词。 - Kerrek SB

当你说“pairs”时，我理解为你指的是二维向量？好主意，但需要循环遍历并分配值……除非有更巧妙的方法？ - Nisk

不是一个二维向量，而是一组成对的向量...你知道的，[(1,A), (3, B), (-11, X), (1, C), ...]。 - Kerrek SB

Answer 1

创建一个整数索引向量，初始化为 { 0, 1, 2, 3, 等等 }。每个整数代表向量中的一个位置。使用自定义比较函数对索引向量进行排序，该函数使用索引来引用 vector1。排序完成后，您可以使用排序后的索引重新排序向量1和向量2。

但我认为您无法原地进行此重新排序，因此您必须从向量复制到向量，所以我认为Kerrek的建议也很好。

- john

---

嗯，我已经使用过这种技术了（我在主机上实现了快速排序，并使用了类似于您所说的索引数组来传播对两个数组的更改 - 而不是交换值，交换逻辑索引）。但是，这对于Thrust库是否有效呢？ - Nisk

我很难想象为什么不行，但我没有使用过thrust库的经验。你提出了一个概念性问题，所以我给出了一个概念性答案。 - john

是的，您做到了！我只是想说可能会有某些限制，因为Thrust使用GPU（以及主机）。谢谢您的帮助 :-) - Nisk