语境
我正在尝试使用CUDA实现Boruvka MST算法，但是完全不需要了解该算法即可在这里为我提供帮助。
问题
因此，让我描述一下问题：我有一个图，以边列表形式存储（边的数组，每个边用2个相邻的顶点ID及其权重表示）。
但是，（非常重要！）为了优化对设备内存的访问，我没有将边缘存储为结构的单个数组，而是存储为三个单独的数组：
要访问单边，可以使用相同的索引对该数组进行迭代：
现在，当我描述数据格式时，这就是问题所在
我想从这三个数组中删除具有以下条件的element（edges）：
1）如果src_id [i] == dst_id [i]，则删除第i个边
2）如果src_id [i]！= dst_id [i]，但是存在另一个边缘j，其具有相同的src_id [j]和dst_id [j]，但权重[j]小于删除第i个边缘
换句话说，我想：
第一个很简单：我可以使用推力::: remove_if或按此处所述进行扫描，从数组中并行删除元素，以删除具有相同id的边缘。（我已经通过扫描实现了第二种形式）。
但是我没有实现第二部分，即删除重复边缘。我有一个主意，但不确定这种方法是否有效。让我描述一下。
首先，我们将通过以下方式对这三个数组进行重新排序（或排序）：
当所有边缘以这种方式排序时，相对容易地删除重复的非最小边缘：
问题*
但是问题是我不知道如何高效地对三个数组进行排序。（也许我可以对转换后的数据和结构的单个数组使用推力::排序，但似乎速度很慢，最好不要完全删除重复的边）
或者，也许有人可以建议一种更好的方法来删除重复的边缘，而不用这种方式对其进行排序。
感谢您阅读本文，任何建议表示赞赏！
您可以使用轻松在一个thrust::sort呼叫中对多个向量进行排序thrust::zip_iterator。
主要思想是：
auto z = thrust::make_zip_iterator(thrust::make_tuple(d_src_ids.begin(),d_dst_ids.begin(), d_weights.begin()));
thrust::sort(z,z+N);
这将首先按第一个向量对三个向量进行排序，然后对第二个向量进行排序，然后对第三个向量进行排序。
下面的代码显示了如何在一个完整的示例中使用它。它使用自定义函子（从中复制thrust::detail）来完成remove_if单个调用中的步骤，而不必存储中间结果。
#include <thrust/sort.h>
#include <thrust/iterator/zip_iterator.h>
#include <iostream>
#include <thrust/copy.h>
#include <thrust/device_vector.h>
#include <thrust/remove.h>
#define PRINTER(name) print(#name, (name))
template <template <typename...> class V, typename T, typename ...Args>
void print(const char* name, const V<T,Args...> & v)
{
std::cout << name << ":\t";
thrust::copy(v.begin(), v.end(), std::ostream_iterator<T>(std::cout, "\t"));
std::cout << std::endl;
}
// copied from https://github.com/thrust/thrust/blob/master/thrust/detail/range/head_flags.h
#include <thrust/iterator/transform_iterator.h>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/iterator/counting_iterator.h>
#include <thrust/tuple.h>
#include <thrust/functional.h>
template<typename RandomAccessIterator,
typename BinaryPredicate = thrust::equal_to<typename thrust::iterator_value<RandomAccessIterator>::type>,
typename ValueType = bool,
typename IndexType = typename thrust::iterator_difference<RandomAccessIterator>::type>
class head_flags
{
// XXX WAR cudafe issue
//private:
public:
struct head_flag_functor
{
BinaryPredicate binary_pred; // this must be the first member for performance reasons
IndexType n;
typedef ValueType result_type;
__host__ __device__
head_flag_functor(IndexType n)
: binary_pred(), n(n)
{}
__host__ __device__
head_flag_functor(IndexType n, BinaryPredicate binary_pred)
: binary_pred(binary_pred), n(n)
{}
template<typename Tuple>
__host__ __device__ __thrust_forceinline__
result_type operator()(const Tuple &t)
{
const IndexType i = thrust::get<0>(t);
// note that we do not dereference the tuple's 2nd element when i <= 0
// and therefore do not dereference a bad location at the boundary
return (i == 0 || !binary_pred(thrust::get<1>(t), thrust::get<2>(t)));
}
};
typedef thrust::counting_iterator<IndexType> counting_iterator;
public:
typedef thrust::transform_iterator<
head_flag_functor,
thrust::zip_iterator<thrust::tuple<counting_iterator,RandomAccessIterator,RandomAccessIterator> >
> iterator;
__host__ __device__
head_flags(RandomAccessIterator first, RandomAccessIterator last)
: m_begin(thrust::make_transform_iterator(thrust::make_zip_iterator(thrust::make_tuple(thrust::counting_iterator<IndexType>(0), first, first - 1)),
head_flag_functor(last - first))),
m_end(m_begin + (last - first))
{}
__host__ __device__
head_flags(RandomAccessIterator first, RandomAccessIterator last, BinaryPredicate binary_pred)
: m_begin(thrust::make_transform_iterator(thrust::make_zip_iterator(thrust::make_tuple(thrust::counting_iterator<IndexType>(0), first, first - 1)),
head_flag_functor(last - first, binary_pred))),
m_end(m_begin + (last - first))
{}
__host__ __device__
iterator begin() const
{
return m_begin;
}
__host__ __device__
iterator end() const
{
return m_end;
}
template<typename OtherIndex>
__host__ __device__
typename iterator::reference operator[](OtherIndex i)
{
return *(begin() + i);
}
private:
iterator m_begin, m_end;
};
template<typename RandomAccessIterator>
__host__ __device__
head_flags<RandomAccessIterator>
make_head_flags(RandomAccessIterator first, RandomAccessIterator last)
{
return head_flags<RandomAccessIterator>(first, last);
}
int main()
{
const int N = 6;
int src_ids[] = {3,1,2,2,3,3};
int dst_ids[] = {2,2,3,3,1,1};
float weights[] = {1,2,8,4,5,6};
thrust::device_vector<int> d_src_ids(src_ids,src_ids+N);
thrust::device_vector<int> d_dst_ids(dst_ids,dst_ids+N);
thrust::device_vector<float> d_weights(weights,weights+N);
std::cout << "--- initial values ---" << std::endl;
PRINTER(d_src_ids);
PRINTER(d_dst_ids);
PRINTER(d_weights);
auto z = thrust::make_zip_iterator(thrust::make_tuple(d_src_ids.begin(),d_dst_ids.begin(), d_weights.begin()));
thrust::sort(z,z+N);
std::cout << "--- after sort ---" << std::endl;
PRINTER(d_src_ids);
PRINTER(d_dst_ids);
PRINTER(d_weights);
auto z2 = thrust::make_zip_iterator(thrust::make_tuple(d_src_ids.begin(),d_dst_ids.begin()));
auto t = make_head_flags(z2,z2+N);
using namespace thrust::placeholders;
auto end = thrust::remove_if(z,z+N, t.begin(), !_1);
int new_size = thrust::get<0>(end.get_iterator_tuple()) - d_src_ids.begin();
d_src_ids.resize(new_size);
d_dst_ids.resize(new_size);
d_weights.resize(new_size);
std::cout << "--- after remove_if ---" << std::endl;
PRINTER(d_src_ids);
PRINTER(d_dst_ids);
PRINTER(d_weights);
return 0;
}
输出：
--- initial values ---
d_src_ids: 3 1 2 2 3 3
d_dst_ids: 2 2 3 3 1 1
d_weights: 1 2 8 4 5 6
--- after sort ---
d_src_ids: 1 2 2 3 3 3
d_dst_ids: 2 3 3 1 1 2
d_weights: 2 4 8 5 6 1
--- after remove_if ---
d_src_ids: 1 2 3 3
d_dst_ids: 2 3 1 2
d_weights: 2 4 5 1
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句