Тяга: удаление дубликатов в массивах ключ-значение

Question

У меня есть пара массивов одинакового размера, я буду называть их ключами и значениями.

Например:

K: V
1: 99
1: 100
1: 100
1: 100
1: 103
2: 103
2: 105
3: 45
3: 67

Ключи отсортированы, а значения, связанные с каждым ключом, отсортированы. Как удалить дубликаты значений, связанные с каждым ключом и соответствующим ключом?

То есть я хочу сжать вышеупомянутое, чтобы:

1: 99
1: 100
1: 103
2: 103 <-- This should remain, since key is different
2: 105
3: 45
3: 67

Я посмотрел на функции сжатия потоков, доступные в Thrust, но не смог найти ничего, что делает это. Это возможно с Thrust? Или мне нужно написать собственное ядро, чтобы отметить дубликаты в трафарете, а затем удалить их?

Answer 1

Ключи отсортированы, и значения, связанные с каждым ключом, также отсортированы. Таким образом, мы можем считать, что пары ключ-значение отсортированы. thrust::unique будет работать непосредственно над этим, если он может видеть эти 2 вектора как один вектор. Это может быть достигнуто путем архивирования 2 элементов (ключ-значение) в каждой позиции в один кортеж, используя zip_iterator,

Вот как это сделать на месте, а также обрезать векторы ключ-значение только по уникальным элементам:

typedef thrust::device_vector< int >                IntVector;
typedef IntVector::iterator                         IntIterator;
typedef thrust::tuple< IntIterator, IntIterator >   IntIteratorTuple;
typedef thrust::zip_iterator< IntIteratorTuple >    ZipIterator;

IntVector keyVector;
IntVector valVector;

ZipIterator newEnd = thrust::unique( thrust::make_zip_iterator( thrust::make_tuple( keyVector.begin(), valVector.begin() ) ),
                                     thrust::make_zip_iterator( thrust::make_tuple( keyVector.end(), valVector.end() ) ) );

IntIteratorTuple endTuple = newEnd.get_iterator_tuple();

keyVector.erase( thrust::get<0>( endTuple ), keyVector.end() );
valVector.erase( thrust::get<1>( endTuple ), valVector.end() );

Если вы хотите сжать и создать отдельный поток результатов, вам нужно написать собственный двоичный предикат для вашего типа, который рассматривает оба элемента кортежа. thrust::zip_iterator может использоваться для формирования виртуального итератора кортежей из отдельных массивов.

Полный рабочий пример того, как вы можете это сделать, выглядит следующим образом:

#include <iostream>
#include <thrust/tuple.h>
#include <thrust/functional.h>
#include <thrust/device_vector.h>
#include <thrust/iterator/zip_iterator.h>
#include <thrust/unique.h>

// Binary predicate for a tuple pair
typedef thrust::tuple<int, int> tuple_t;
struct tupleEqual
{
  __host__ __device__
    bool operator()(tuple_t x, tuple_t y)
    {
      return ( (x.get<0>()== y.get<0>()) && (x.get<1>() == y.get<1>()) );
    }
};

typedef thrust::device_vector<int>::iterator  intIterator;
typedef thrust::tuple<intIterator, intIterator> intIteratorTuple;
typedef thrust::zip_iterator<intIteratorTuple> zipIterator;
typedef thrust::device_vector<tuple_t>::iterator tupleIterator;

int main(void)
{
  thrust::device_vector<int> k(9), v(9);
  thrust::device_vector<tuple_t> kvcopy(9);

  k[0] = 1; k[1] = 1; k[2] = 1; 
  k[3] = 1; k[4] = 1; k[5] = 2;
  k[6] = 2; k[7] = 3; k[8] = 3;

  v[0] = 99;  v[1] = 100; v[2] = 100;
  v[3] = 100; v[4] = 103; v[5] = 103;
  v[6] = 105; v[7] = 45;  v[8] = 67;

  zipIterator kvBegin(thrust::make_tuple(k.begin(),v.begin()));
  zipIterator kvEnd(thrust::make_tuple(k.end(),v.end()));
  thrust::copy(kvBegin, kvEnd, kvcopy.begin());

  tupleIterator kvend = 
        thrust::unique(kvcopy.begin(), kvcopy.end(), tupleEqual());

  for(tupleIterator kvi = kvcopy.begin(); kvi != kvend; kvi++) {
    tuple_t r = *kvi;
    std::cout << r.get<0>() << "," << r.get<1>() << std::endl;
  }

  return 0;
}

Answer 2

Уплотнение потока с небольшой подготовкой подойдет. Вы можете в основном запустить поток для каждой пары ключ-значение, проверить, равна ли предыдущая пара ключ-значение, если нет: установить флаг (int = 1) в отдельном массиве того же размера, что и эти пары. Все остальные флаги остаются неустановленными (int = 0). Затем выполните потоковое сжатие пар ключ-значение на основе массива флагов.