Многократный поиск субвектора с помощью cuda Thrust - PullRequest
Новая
       15

Многократный поиск субвектора с помощью cuda Thrust

0 голосов
/ 06 мая 2019

Я хочу найти вхождения субвектора в векторе устройства в графическом процессоре, с библиотекой тяги.

Скажем, для массива str = "aaaabaaab", мне нужно найти вхождения substr = "ab".

Как использовать функцию thrust::find для поиска в подвекторе?

В двух словах Как реализовать алгоритм поиска строки с библиотекой тяги?

1 Ответ

1 голос
/ 06 мая 2019

Я бы согласился с комментариями при условии, что тяга не предоставляет ни одной функции, которая делает это «типичным способом тяги», и вы не захотите использовать последовательность функций тяги (например, цикл), поскольку это, вероятно, будетвесьма неэффективно.

Можно написать довольно простое ядро ​​CUDA, которое делает это методом грубой силы.

Для относительно простых ядер CUDA мы можем реализовать нечто эквивалентное в толчке в "un-подобная "мода", просто передавая код ядра CUDA в качестве функтора в операцию надстройки для каждого элемента, такую ​​как thrust::transform или thrust::for_each.

Вот пример: 

$ cat t462.cu
#include <iostream>
#include <thrust/device_vector.h>
#include <thrust/transform.h>
#include <thrust/copy.h>
#include <thrust/iterator/counting_iterator.h>

struct my_f
{
  char *array, *string;
  size_t arr_len;
  int    str_len;
  my_f(char *_array, size_t _arr_len, char *_string, int _str_len) :
    array(_array), arr_len(_arr_len), string(_string), str_len(_str_len) {};
  __host__ __device__
  bool operator()(size_t idx){
    for (int i=0; i < str_len; i++)
      if ((i+idx)>= arr_len) return false;
      else if (array[i+idx] != string[i]) return false;
    return true;
  }
};

int main(){
  char data[] = "aaaabaaab";
  char str[] = "ab";
  size_t data_len = sizeof(data)-1;
  int str_len = sizeof(str)-1;
  thrust::device_vector<char> d_data(data, data+data_len);
  thrust::device_vector<char> d_str(str, str+str_len);
  thrust::device_vector<bool> result(data_len);
  thrust::transform(thrust::counting_iterator<size_t>(0), thrust::counting_iterator<size_t>(data_len), result.begin(), my_f(thrust::raw_pointer_cast(d_data.data()), data_len, thrust::raw_pointer_cast(d_str.data()), str_len));
  thrust::copy(result.begin(), result.end(), std::ostream_iterator<bool>(std::cout, ","));
  std::cout << std::endl;
}
$ nvcc -o t462 t462.cu
$ ./t462
0,0,0,1,0,0,0,1,0,
$

Эффективен ли такой подход "грубой силы" для такого типа проблем, я не знаю.Вероятно, существуют лучшие / более эффективные методы, особенно при поиске появления более длинных строк.

...