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

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

3 голосов
/ 12 августа 2011

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

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

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

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

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

Причина

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

# UPDATE

Я должен подчеркнуть, у меня нет проблем с сортировкой двух на хосте, я ищу решение, которое использует 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*

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

1 Ответ

1 голос
/ 12 августа 2011

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

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

...