Spaces:
Runtime error
Runtime error
File size: 4,582 Bytes
be11144 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
#include <thrust/device_vector.h>
#include <thrust/merge.h>
#include <thrust/set_operations.h>
#include <thrust/iterator/discard_iterator.h>
#include <iostream>
// This example illustrates use of the set operation algorithms
// - merge
// - set_union
// - set_intersection
// - set_difference
// - set_symmetric_difference
//
// In this context a "set" is simply a sequence of sorted values,
// allowing the standard set operations to be performed more efficiently
// than on unsorted data. Since the output of a set operation is a valid
// set (i.e. a sorted sequence) it is possible to apply the set operations
// in a nested fashion to compute arbitrary set expressions.
//
// Set operation usage notes:
// - The output set size is variable (except for thrust::merge),
// so the return value is important.
// - Generally one would conservatively allocate storage for the output
// and then resize or shrink an output container as necessary.
// Alternatively, one can compute the exact output size by
// outputting to a discard_iterator. This approach is more computationally
// expensive (approximately 2x), but conserves memory capacity.
// Refer to the SetIntersectionSize function for implementation details.
// - Sets are allowed to have duplicate elements, which are carried
// through to the output in a algorithm-specific manner. Refer
// to the full documentation for precise semantics.
// helper routine
template <typename String, typename Vector>
void print(const String& s, const Vector& v)
{
std::cout << s << " [";
for(size_t i = 0; i < v.size(); i++)
std::cout << " " << v[i];
std::cout << " ]\n";
}
template <typename Vector>
void Merge(const Vector& A, const Vector& B)
{
// merged output is always exactly A.size() + B.size()
Vector C(A.size() + B.size());
thrust::merge(A.begin(), A.end(), B.begin(), B.end(), C.begin());
print("Merge(A,B)", C);
}
template <typename Vector>
void SetUnion(const Vector& A, const Vector& B)
{
// union output is at most A.size() + B.size()
Vector C(A.size() + B.size());
// set_union returns an iterator C_end denoting the end of input
typename Vector::iterator C_end;
C_end = thrust::set_union(A.begin(), A.end(), B.begin(), B.end(), C.begin());
// shrink C to exactly fit output
C.erase(C_end, C.end());
print("Union(A,B)", C);
}
template <typename Vector>
void SetIntersection(const Vector& A, const Vector& B)
{
// intersection output is at most min(A.size(), B.size())
Vector C(thrust::min(A.size(), B.size()));
// set_union returns an iterator C_end denoting the end of input
typename Vector::iterator C_end;
C_end = thrust::set_intersection(A.begin(), A.end(), B.begin(), B.end(), C.begin());
// shrink C to exactly fit output
C.erase(C_end, C.end());
print("Intersection(A,B)", C);
}
template <typename Vector>
void SetDifference(const Vector& A, const Vector& B)
{
// difference output is at most A.size()
Vector C(A.size());
// set_union returns an iterator C_end denoting the end of input
typename Vector::iterator C_end;
C_end = thrust::set_difference(A.begin(), A.end(), B.begin(), B.end(), C.begin());
// shrink C to exactly fit output
C.erase(C_end, C.end());
print("Difference(A,B)", C);
}
template <typename Vector>
void SetSymmetricDifference(const Vector& A, const Vector& B)
{
// symmetric difference output is at most A.size() + B.size()
Vector C(A.size() + B.size());
// set_union returns an iterator C_end denoting the end of input
typename Vector::iterator C_end;
C_end = thrust::set_symmetric_difference(A.begin(), A.end(), B.begin(), B.end(), C.begin());
// shrink C to exactly fit output
C.erase(C_end, C.end());
print("SymmetricDifference(A,B)", C);
}
template <typename Vector>
void SetIntersectionSize(const Vector& A, const Vector& B)
{
// computes the exact size of the intersection without allocating output
thrust::discard_iterator<> C_begin, C_end;
C_end = thrust::set_intersection(A.begin(), A.end(), B.begin(), B.end(), C_begin);
std::cout << "SetIntersectionSize(A,B) " << (C_end - C_begin) << std::endl;
}
int main(void)
{
int a[] = {0,2,4,5,6,8,9};
int b[] = {0,1,2,3,5,7,8};
thrust::device_vector<int> A(a, a + sizeof(a) / sizeof(int));
thrust::device_vector<int> B(b, b + sizeof(b) / sizeof(int));
print("Set A", A);
print("Set B", B);
Merge(A,B);
SetUnion(A,B);
SetIntersection(A,B);
SetDifference(A,B);
SetSymmetricDifference(A,B);
SetIntersectionSize(A,B);
return 0;
}
|