c++ - terminología - Empuje ¿Clasificar por tecla sobre la marcha o enfoque diferente?

ingles para contadores pdf

Question

Me preguntaba si es posible ordenar por claves usando Thrust Library sin la necesidad de crear un Vector para almacenar las claves (sobre la marcha). Por ejemplo, tengo los siguientes dos vectores: claves y valores:

vectorKeys:    0,  1,  2,  0,  1,  2,  0,  1,  2 

VectorValues: 10, 20, 30, 40, 50, 60, 70, 80, 90

Después de ordenar por claves:

thrust::sort_by_key(vKeys.begin(), vKeys.end(), vValues.begin());

Los vectores resultantes son:

vectorKeys:    0,  0,  0,  1,  1,  1,  2,  2,  2 

VectorValues: 10, 40, 70, 20, 50, 80, 30, 60, 90

¿Qué me gustaría saber si es posible ordenar_por_clave sin la necesidad del vector vKeys (sobre la marcha), así puedo guardar la memoria de almacenamiento y poder ordenar más datos?

Al final, quiero sumar por las mismas teclas y almacenar en un vector ... ¿hay un mejor enfoque en lugar de ordenar por clave y luego reducir por clave para obtener el mismo resultado?

FinalVector = 120, 150, 180  

Answer 1

El ejemplo de empuje original que enlazó realizó una suma de fila en un conjunto de datos subyacente que tenía almacenamiento principal de fila. Su pregunta es esencialmente cómo hacer lo mismo cuando el almacenamiento subyacente es column-major.

Podemos usar esencialmente el mismo método, pero debemos usar iteradores de permutación para convertir el almacenamiento subyacente de la columna principal al almacenamiento principal de la fila "sobre la marcha".

Para esto, podemos tomar prestado el functor que describí aquí .

Aquí hay un ejemplo completamente trabajado:

$ cat t466.cu
#include <thrust/host_vector.h>
#include <thrust/device_vector.h>
#include <thrust/reduce.h>
#include <thrust/functional.h>
#include <thrust/sequence.h>
#include <thrust/iterator/transform_iterator.h>
#include <thrust/iterator/permutation_iterator.h>
#include <thrust/iterator/counting_iterator.h>
#include <iostream>

#define COLS 3
#define ROWS 3
#define DSIZE (COLS*ROWS)
#define INIT 10
#define STEP 10

// convert a linear index to a row index
template <typename T>
struct linear_index_to_row_index : public thrust::unary_function<T,T>
{
  T C; // number of columns

  __host__ __device__
  linear_index_to_row_index(T C) : C(C) {}

  __host__ __device__
  T operator()(T i)
  {
    return i % C;
  }
};

struct rm2cm_idx_functor : public thrust::unary_function<int, int>
{
  int r;
  int c;

  rm2cm_idx_functor(int _r, int _c) : r(_r), c(_c) {};

  __host__ __device__
  int operator() (int idx)  {
    unsigned my_r = idx/c;
    unsigned my_c = idx%c;
    return (my_c * r) + my_r;
  }
};


int main(void)
{
  int C = COLS;     // number of columns
  int R = ROWS;     // number of rows
  thrust::host_vector<int> h_vals(DSIZE);
  // initialize data
  thrust::sequence(h_vals.begin(), h_vals.end(), INIT, STEP);
  thrust::device_vector<int> vals = h_vals;
  std::cout << " Initial data: " << std::endl;
  thrust::copy(h_vals.begin(), h_vals.end(), std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;
  // allocate storage for row sums and indices
  thrust::device_vector<int> row_sums(R);
  thrust::device_vector<int> row_indices(R);

  // compute row sums by summing values with equal row indices
  thrust::reduce_by_key
    (thrust::make_permutation_iterator(thrust::make_transform_iterator(thrust::counting_iterator<int>(0), linear_index_to_row_index<int>(R)), thrust::make_transform_iterator(thrust::counting_iterator<int>(0), rm2cm_idx_functor(R, C))),
     thrust::make_permutation_iterator(thrust::make_transform_iterator(thrust::counting_iterator<int>(0), linear_index_to_row_index<int>(R)) + (R*C), thrust::make_transform_iterator(thrust::counting_iterator<int>(0), rm2cm_idx_functor(R, C)) + (R*C)),
     thrust::make_permutation_iterator(vals.begin(), thrust::make_transform_iterator(thrust::counting_iterator<int>(0), rm2cm_idx_functor(R, C))),
     row_indices.begin(),
     row_sums.begin(),
     thrust::equal_to<int>(),
     thrust::plus<int>());

  // print data
  thrust::host_vector<int> h_row_sums = row_sums;
  std::cout << " Results: " << std::endl;
  thrust::copy(h_row_sums.begin(), h_row_sums.end(), std::ostream_iterator<int>(std::cout, ","));
  std::cout << std::endl;
  return 0;
}

$ nvcc -arch=sm_20 -o t466 t466.cu
$ ./t466
 Initial data:
10,20,30,40,50,60,70,80,90,
 Results:
120,150,180,
$

Tenga en cuenta que también he cambiado el linear_index_to_row_index del linear_index_to_row_index para darme un índice de fila adecuadamente organizado para el almacenamiento subyacente de columna principal (el funtor anterior devolvió el índice cuando se suponía que el almacenamiento subyacente era principal ). Esto solo implicó cambiar la operación de división a una operación de módulo y pasar R lugar de C para inicializar el funtor, así que tenga en cuenta la diferencia sutil.