使用cuda Thrust进行多次出现子向量搜索 [英] Multiple occurrence subvector search with cuda Thrust

问题描述

我想使用推力库在GPU中的设备矢量中查找子矢量的出现。

I want to find occurrences of subvector in a device vector in GPU, with thrust library.

说说str = aaaabaaab数组，我需要查找substr = ab的出现。

Say for an array of str = "aaaabaaab", I need to find occurrences of substr = "ab".

如何使用 thrust :: find 函数搜索子矢量？

How shall I use thrust::find function to search a subvector?

简而言之，如何使用推力库实现字符串搜索算法？

In nutshell How shall I implement string search algorithm with thrust library?

推荐答案

我会同意注释提供了推力不提供以典型推力方式执行此功能的单个函数，并且您不希望使用推力函数序列（例如循环），因为这可能效率很低。

I would agree with the comments provided that thrust doesn't provide a single function that does this in "typical thrust fashion" and you would not want to use a sequence of thrust functions (e.g. a loop) as that would likely be quite inefficient.

可以编写一个相当简单的CUDA内核，以蛮力方式做到这一点。

A fairly simple CUDA kernel can be written that does this in a brute-force fashion.

对于相对简单的CUDA内核，我们通过简单地将CUDA内核代码作为函子传递给推力每个元素的操作（例如 thrust :: transform 或 thrust :: for_each 。

For relatively simple CUDA kernels, we can realize something equivalent in thrust in a "un-thrust-like" fashion, by simply passing the CUDA kernel code as a functor to a thrust per-element operation such as thrust::transform or 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,
$

对于这种类型的问题，这种强力方法是否有效不知道可能有更好/更有效的方法，尤其是在搜索较长字符串的情况下。

Whether or not such a "brute-force" approach is efficient for this type of problem I don't know. Probably there are better/more efficient methods, especially when searching for occurrence of longer strings.

这篇关于使用cuda Thrust进行多次出现子向量搜索的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！