sorting - 使用 Thrust 对数组结构进行排序

Question

我正在研究 CUDA 并面临以下问题。我有以下数组结构：

typedef struct Edge{
    int *from, *to, *weight;
}

我想在权重数组上对这个结构进行排序，以便相应的“from”和“to”数组也得到更新。我想过使用 Thrust 库，但它只适用于向量是我所理解的。我可以 sort_by_key 并对两个数组进行排序，但我无法理解如何对三个数组进行排序？我什至查看了 zip_iterator 但不明白如何使用它来达到我的目的。请帮忙

Answer 1

首先将结构解耦为 1) 键和 2) 填充。然后对键进行排序并相应地重新排序填充。例如，打破这个结构：

typedef struct Edge{
    int from, to, weight;
}

进入：

int weight[N];
typedef struct Edge{
    int from, to;
}

完整代码在这里：

#include <thrust/device_vector.h>
#include <thrust/host_vector.h>
#include <cmath>
#include <thrust/sort.h>

typedef struct pad {
        int from;
        int to;
} padd;

__host__ padd randPad() {
        padd p;
        p.from = rand();
        p.to = rand();
        return p;
}

__host__ std::ostream& operator<< (std::ostream& os, const padd& p) {
        os << "(" << p.to << " , " << p.from << " )";
        return os;
}

int main(void)
{
  // allocation
  #define N 4
  thrust::host_vector<int> h_keys(4);
  thrust::host_vector<padd> h_pad(4);

  // initilization
  thrust::generate(h_keys.begin(), h_keys.end(), rand);
  thrust::generate(h_pad.begin(), h_pad.end(), randPad);

  // print unsorted data
  std::cout<<"Unsorted keys\n";
  thrust::copy(h_keys.begin(), h_keys.end(), std::ostream_iterator<int>(std::cout, "\n"));
  std::cout<<"\nUnsorted paddings\n";
  thrust::copy(h_pad.begin(), h_pad.end(), std::ostream_iterator<padd>(std::cout, "\n"));

  // transfer to device
  thrust::device_vector<int> d_keys = h_keys;
  thrust::device_vector<padd> d_pad = h_pad;
  //thrust::sort(d_keys.begin(), d_keys.end());

  // sort
  thrust::sort_by_key(d_keys.begin(), d_keys.end(), d_pad.begin());

  // transfer back to host
  thrust::copy(d_keys.begin(), d_keys.end(), h_keys.begin());
  thrust::copy(d_pad.begin(), d_pad.end(), h_pad.begin());

  // print the results
  std::cout<<"\nSorted keys\n";
  thrust::copy(h_keys.begin(), h_keys.end(), std::ostream_iterator<int>(std::cout, "\n"));
  std::cout<<"\nSorted paddings\n";
  thrust::copy(h_pad.begin(), h_pad.end(), std::ostream_iterator<padd>(std::cout, "\n"));

  return 0;
}

输出将是这样的：

Unsorted keys
1804289383
846930886
1681692777
1714636915

Unsorted paddings
(424238335 , 1957747793 )
(1649760492 , 719885386 )
(1189641421 , 596516649 )
(1350490027 , 1025202362 )

Sorted keys
846930886
1681692777
1714636915
1804289383

Sorted paddings
(1649760492 , 719885386 )
(1189641421 , 596516649 )
(1350490027 , 1025202362 )
(424238335 , 1957747793 )