高效搜索数组中的一系列值？理想情况下 OpenCL 可用吗？

Question

我有一个大数组需要搜索（实际上它是一个由小数组组成的大数组，但出于所有意图和目的，让我们将其视为一个大数组）。我需要找到的是一系列特定的数字。显然，一个简单的 for 循环就可以了：

Pseudocode:
for(x = 0; x++) {
  if(array[x] == searchfor[location])
    location++;
  else
    location = 0;
  if(location >= strlen(searchfor))
    return FOUND_IT;
}

事情是我希望这是有效的。在一个完美的世界中，我不想 return 从 OpenCL 内核准备好的数据并进行简单的搜索循环。

我对非 OpenCL 的想法持开放态度，但我可以在 64 人的工作组中实现目标数组长度为 1024 的东西是理想的。

我正在考虑一些想法（将目标拆分到工作项中，比较每个项目，循环，针对每个目标，如果匹配，则设置一个标志。在所有工作项完成后，检查标志。虽然在我写的时候那，这听起来效率很低）但我确定我遗漏了一些东西。

另一个想法是，由于目标数组是 uchar，将它作为一个 double 组合在一起，并一次检查 8 个索引。不确定我能否在 opencl 中轻松做到这一点。

还尝试用一些快速的东西对搜索目标进行哈希处理，可能是 MD5，然后一次抓取 strlen(searchtarget) 个字符，对其进行哈希处理，然后查看它是否匹配。不确定散列多少会降低我的搜索速度。

哦 - 代码在 C 中，所以没有 C++ 映射（我在谷歌搜索时发现的东西似乎有帮助？）

Answer 1

根据以上评论，对于未来的搜索，简单的 for 循环扫描范围似乎是在给定 OpenCL 实现的情况下查找匹配项的最有效方法。

Answer 2

创建索引数组[sizeof uchar]。对于搜索字符串中的每个 uchar，使 array[uchar] = uchar 在搜索字符串中首次出现的位置。数组的其余部分包含 -1.

unsigned searchindexing[sizeof char] = { (unsigned)-1};
memcpy(searchindexing + 1, searchindexing, sizeof char - 1);
for (i = 0; i < strlen(searchfor); i++)
  searchindexing[searchfor[i]] = i;

如果您不从头开始，出现多次的 uchar 将在搜索索引中输入错误的位置。

然后通过步进 strlen(searchfor) 搜索数组，除非从 searchfor 中找到一个 uchar。

for (i = 0; i < MAXARRAYLEN; i += strlen(searchfor))
  if ((unsigned)-1 != searchindexing[array[i]]) {
    i -= searchindexing[array[i]];
    if (!memcmp(searchfor, &array[i], strlen(searchfor)))
      return FOUND_IT;
  }

如果数组中的大部分 uchar 不在搜索范围内，这可能是最快的方法。请注意代码尚未优化。

示例：searchfor = "banana"。 strlen 是 6。searchindexing['a'] = 5，['b'] = 0，['n'] = 4，其余值不在 0 到 5 之间，例如 -1 或 maxuint .如果 array[i] 不像 space 那样在 banana 中，i 递增 6。如果 array[i] 现在是 'a'，你可能在 banana 中，它可以是 3 [=] 中的任何一个23=]秒。所以我们假设最后一个 'a' 并向后移动 5 个位置并与 searchfor 进行比较。如果成功，我们就找到了，否则我们前进 6 位。

高效搜索数组中的一系列值？理想情况下 OpenCL 可用吗？

Efficient search for series of values in an array? Ideally OpenCL usable?

c

arrays

search

opencl