Как отсортировать два массива/вектора по значениям в одном из массивов, используя CUDA/Thrust

Это концептуальный вопрос в отношении программирования.

Подводя итог, у меня есть два массива/вектора, и мне нужно отсортировать один с изменениями, распространяющимися и на другой, так что, если я сортирую arrayOne, для каждого обмена в сортировке - то же самое происходит с arrayTwo. Теперь я знаю, что std::sort позволяет вам определить функцию сравнения (я полагаю, для пользовательских объектов), и я подумывал определить ее для одновременной замены arrayTwo.

Итак, что я хочу, это отсортировать два вектора на основе значений в одном из векторов, используя CUDA.

Вот где моя неуверенность возрастает, по сути, я хочу использовать библиотеку Thrust для сортировки. Поддерживает ли он определение пользовательской функции сравнения? Если это так, я до сих пор не понял, как распространить изменение в arrayTwo (поскольку оно будет основано на CUDA).

У меня действительно нет времени для реализации пользовательской параллельной быстрой сортировки на CUDA, как бы я ни хотел/не хотел.

Причина

По сути, мне нужно выполнить сортировку и вычисление множества массивов переменных вместо одного массива (например, деревья регрессии). Естественно, мне нужно сделать это как можно быстрее, сортировка на основе процессора просто недостаточно быстра.

#ОБНОВЛЕНИЕ

Я должен подчеркнуть, что у меня нет проблем с сортировкой двух на хосте, я ищу решение, использующее CUDA. Спасибо.

#ОБНОВЛЕНИЕ 2

Я думаю, что мне действительно повезло, и я нашел решение, так как я разместил вопрос, оказывается, Thrust на самом деле предоставляет именно то, что я ищу по умолчанию:

#include <thrust/sort.h>
  ...
  const int N = 6;
  int    keys[N] = {  1,   4,   2,   8,   5,   7};
  char values[N] = {'a', 'b', 'c', 'd', 'e', 'f'};
  thrust::sort_by_key(keys, keys + N, values);
  // keys is now   {  1,   2,   4,   5,   7,   8}
  // values is now {'a', 'c', 'b', 'e', 'f', 'd'}

*взято из http://code.google.com/p/thrust/wiki/QuickStartGuide#Fancy_Iterators*

Итак, теперь все, что мне нужно сделать, это получить два тяги::device_vectors из двух массивов (которые я должен получить из 2D-массива). Счастливый.


person Nisk    schedule 12.08.2011    source источник
comment
Почему бы вам просто не создать вектор пар и не отсортировать их по первому значению пары? Вы, конечно, можете передать соответствующий предикат в thrust::sort для этой цели.   -  person Kerrek SB    schedule 12.08.2011
comment
когда вы говорите пары - я так понимаю, вы имеете в виду 2D-вектор? Хорошая идея, но нужно будет пройтись по циклу и присвоить значения... если, может быть, нет более изящного способа?   -  person Nisk    schedule 12.08.2011
comment
Нет, не двумерный вектор, а вектор пар... знаете, [(1,A), (3, B), (-11, X), (1, C), ...].   -  person Kerrek SB    schedule 12.08.2011


Ответы (1)


Создайте вектор целочисленных индексов, инициализированных {0, 1, 2, 3 и т. д.}. Каждое целое число представляет одну позицию в вашем векторе. Отсортируйте свой вектор индексов, используя пользовательскую функцию сравнения, которая использует индексы для ссылки на vector1. Когда закончите, вы можете использовать отсортированные индексы, чтобы переупорядочить вектор1 и вектор2.

Но я не думаю, что вы можете сделать это переупорядочение на месте, поэтому вам все равно придется копировать из вектора в вектор, поэтому я думаю, что предложение Керрека тоже хорошо.

person john    schedule 12.08.2011
comment
Хм, я уже использовал эту технику (я реализовал быструю сортировку на хосте и использовал массив индексов, аналогичный тому, что вы сказали, для распространения изменений на оба массива - вместо обмена значениями меняйте местами логические индексы). Будет ли это работать для библиотеки Thrust? - person Nisk; 12.08.2011
comment
Мне трудно представить, почему нет, но у меня нет опыта работы с библиотекой тяги. У вас был концептуальный вопрос, поэтому я дал концептуальный ответ. - person john; 12.08.2011
comment
Да вы сделали! Я просто имел в виду, что могут быть некоторые ограничения, поскольку Thrust использует GPU (а также хост). Спасибо за попытку помочь :-) - person Nisk; 12.08.2011