Hier ist ein möglicher Ansatz, die ich denken könnte als Sequenz schneller. Der Schlüsselgedanke ist, dass wir Daten vermeiden wollen, bei denen wir die Reihenfolge im Voraus kennen. Wenn wir das Bestellwissen, das wir haben, nutzen können, anstatt die Daten zu sortieren, können wir sie einfach in die gewünschte Anordnung umordnen.
Lassen Sie uns einige Beobachtungen über die Daten machen. Wenn Ihr key1 und key2 in der Tat sind die i, j Indizes einer oberen Dreiecksmatrix, dann können wir einige Beobachtungen über die Verkettung dieser beiden Vektoren machen:
Die verkettete Vektor zu gleichen Teilen enthalten wird von jeder Schlüssel. (Ich glaube, dass Sie darauf in Ihrer Frage hingewiesen haben.) Also in Ihrem Fall wird der Vektor drei 0 Schlüssel, drei 1 Schlüssel, drei 2 Schlüssel und drei 3 Schlüssel enthalten. Ich glaube, dass dieses Muster für jedes obere Dreiecksmuster unabhängig von der Matrixdimension gelten sollte. Eine Matrix der Dimension N, die das obere Dreieck ist, hat also N Schlüsselmengen im verketteten Indexvektor, wobei jeder Satz aus N-1-ähnlichen Elementen besteht.
In dem verketteten Vektor können wir eine konsistente Ordnung von Schlüsseln (basierend auf der Matrixdimension N) entdecken/etablieren, die es uns ermöglicht, den Vektor in der Reihenfolge der like-key-groups neu anzuordnen, ohne auf eine traditionelle Sortieroperation zurückzugreifen .
Wenn wir die oben genannten 2 Ideen kombinieren, dann können wir wahrscheinlich das ganze Problem mit einigen Streuoperationen lösen, um die Art zu ersetzen/fusionieren Aktivität, gefolgt von dem thrust::reduce_by_key Betrieb. Die Streuungsoperationen können mit thrust::copy zu einem geeigneten thrust::permutation_iterator kombiniert mit einem geeigneten Indexberechnungsfunktor durchgeführt werden. Da wir genau wissen, wie der neu angeordnete verkettete Vektor key aussehen wird (in Ihrem Dimension-4-Beispiel: {0,0,0,1,1,1,2,2,2,3,3,3}), müssen wir die Neuanordnung nicht explizit darauf durchführen. Allerdings müssen wir den Vektor value mit der gleichen Zuordnung neu anordnen. Also lassen Sie entwickeln die die Arithmetik für das Mapping:
dimension (N=)4 example
vector index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11
desired (group) order: 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3
concatenated keys: 0, 0, 0, 1, 1, 2, 1, 2, 3, 2, 3, 3
group start idx: 0, 0, 0, 3, 3, 6, 3, 6, 9, 6, 9, 9
group offset idx: 0, 1, 2, 0, 1, 0, 2, 1, 0, 2, 1, 2
destination idx: 0, 1, 2, 3, 4, 6, 5, 7, 9, 8,10,11
dimension (N=)5 example
vector index: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15,16,17,18,19
desired (group) order: 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4
concatenated keys: 0, 0, 0, 0, 1, 1, 1, 2, 2, 3, 1, 2, 3, 4, 2, 3, 4, 3, 4, 4
group start idx: 0, 0, 0, 0, 4, 4, 4, 8, 8,12, 4, 8,12,16, 8,12,16,12,16,16
group offset idx: 0, 1, 2, 3, 0, 1, 2, 0, 1, 0, 3, 2, 1, 0, 3, 2, 1, 3, 2, 3
destination idx: 0, 1, 2, 3, 4, 5, 6,10, 7, 8,11,14, 9,12,15,17,13,16,18,19
Wir können beobachten, dass in jedem Fall die Zielindex (dh die Position des ausgewählten Schlüssel oder Wert zu bewegen, um für die gewünschte Gruppenordnung) gleich der Gruppenstartindex plus Gruppenversatzindex. Der Gruppenstartindex ist einfach der Schlüssel multipliziert mit (N-1). Der Gruppenoffset-Index ist ein Muster, das einem oberen oder unteren dreieckigen Indexmuster ähnelt (in zwei verschiedenen Inkarnationen für jede Hälfte des verketteten Vektors). Die verketteten Schlüssel sind einfach die Verkettung der Vektoren key1 und key2 (wir erstellen diese Verkettung virtuell unter Verwendung von permutation_iterator). Die gewünschte Gruppenordnung ist a priori bekannt, sie ist einfach eine Folge ganzzahliger Gruppen mit N Gruppen, die jeweils aus N-1 Elementen bestehen. Es entspricht der sortierten Version des verketteten Schlüsselvektors. Daher können wir den Zielindex direkt in einem Funktor berechnen.
Für die Erstellung der Gruppenindexmuster versetzt, können wir Ihre beiden wichtigsten Vektoren (und subtrahieren eine zusätzliche 1) subtrahieren:
key2: 1, 2, 3, 2, 3, 3
key1: 0, 0, 0, 1, 1, 2
key1+1: 1, 1, 1, 2, 2, 3
p1 = key2-(key1+1): 0, 1, 2, 0, 1, 0
p2 = (N-2)-p1: 2, 1, 0, 2, 1, 2
grp offset idx=p1|p2: 0, 1, 2, 0, 1, 0, 2, 1, 0, 2, 1, 2
hier ein voll ausgearbeitetes Beispiel ist die oben genannten Konzepte mit Ihrem Beispiel demonstriert Daten:
$ cat t1133.cu
#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/reduce.h>
#include <thrust/copy.h>
#include <thrust/transform.h>
#include <thrust/iterator/transform_iterator.h>
#include <thrust/iterator/permutation_iterator.h>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/iterator/counting_iterator.h>
#include <iostream>
// "triangular sort" index generator
struct idx_functor
{
int n;
idx_functor(int _n): n(_n) {};
template <typename T>
__host__ __device__
int operator()(const T &t){
int k1 = thrust::get<0>(t);
int k2 = thrust::get<1>(t);
int id = thrust::get<2>(t);
int go,k;
if (id < (n*(n-1))/2){ // first half
go = k2-k1-1;
k = k1;
}
else { // second half
go = n-k2+k1-1;
k = k2;
}
return k*(n-1)+go;
}
};
const int N = 4;
using namespace thrust::placeholders;
int main(){
// useful dimensions
int d1 = N*(N-1);
int d2 = d1/2;
// iniitialize keys
int key_1[] = {0, 0, 0, 1, 1, 2};
int key_2[] = {1, 2, 3, 2, 3, 3};
thrust::device_vector<int> k1(key_1, key_1+d2);
thrust::device_vector<int> k2(key_2, key_2+d2);
// initialize values
double value_1[] = {0.5, 0.5, 0.5, -1.0, -1.0, 2.0};
double value_2[] = {-1, 2.0, -3.5, 2.0, -3.5, -3.5};
thrust::device_vector<double> v(d1);
thrust::device_vector<double> vg(d1);
thrust::copy_n(value_1, d2, v.begin());
thrust::copy_n(value_2, d2, v.begin()+d2);
// reorder (group) values by key
thrust::copy(v.begin(), v.end(), thrust::make_permutation_iterator(vg.begin(), thrust::make_transform_iterator(thrust::make_zip_iterator(thrust::make_tuple(thrust::make_permutation_iterator(k1.begin(), thrust::make_transform_iterator(thrust::counting_iterator<int>(0), _1%d2)), thrust::make_permutation_iterator(k2.begin(), thrust::make_transform_iterator(thrust::counting_iterator<int>(0), _1%d2)), thrust::counting_iterator<int>(0))), idx_functor(N))));
// sum results
thrust::device_vector<double> rv(N);
thrust::device_vector<int> rk(N);
thrust::reduce_by_key(thrust::make_transform_iterator(thrust::counting_iterator<int>(0), _1/(N-1)), thrust::make_transform_iterator(thrust::counting_iterator<int>(d1), _1/(N-1)), vg.begin(), rk.begin(), rv.begin());
// print results
std::cout << "Keys:" << std::endl;
thrust::copy_n(rk.begin(), N, std::ostream_iterator<int>(std::cout, ", "));
std::cout << std::endl << "Sums:" << std::endl;
thrust::copy_n(rv.begin(), N, std::ostream_iterator<double>(std::cout, ", "));
std::cout << std::endl;
return 0;
}
$ nvcc -std=c++11 -o t1133 t1133.cu
$ ./t1133
Keys:
0, 1, 2, 3,
Sums:
1.5, -3, 6, -10.5,
$
Der Nettoeffekt ist, dass Ihre thrust::sort_by_key und thrust::merge_by_key Operationen durch einen einzigen thrust::copy Betrieb ersetzt worden, die effizienter sein sollte.