c++ - 理论上，find_end 是可并行化的吗？

Question

我目前正在研究 open-std proposal为我正在处理的项目带来并行功能，但我遇到了 find_end 的障碍。

现在find_end可以描述为:

An algorithm that searches for the last subsequence of elements [s_first, s_last) in the range [first, last). The first version uses operator== to compare the elements, the second version uses the given binary predicate p.

它的要求由 cppreference 列出.现在我并行化 find/findif/findifnot 等没问题了。这些可以很容易地分成单独的分区，异步执行，我有没事。 find_end 的问题在于，将算法分成多个 block 并不是解决方案，因为如果我们说一个 vector :

1 2 3 4 5 1 2 3 8

我们要搜索 1 2。

好的，首先我将 vector 异步分成 block ，然后只搜索每个 block 中的范围，对吗？对我来说似乎很容易，但是如果由于某种原因只有 3 个可用内核会发生什么，因此 vector 被分成 3 个 block :

1 2 3|4 5 1|2 3 8

现在我遇到了一个问题，第二个 1 2 范围被分成了不同的分区。这将导致大量无效结果，因为有人拥有 x 个核心，最终将搜索结果拆分为 y 个不同的分区。我想我会做一些 search chunks -> merge y chunks into y/2 chunks -> search -> 在递归式搜索中，但这看起来效率很低，这个算法是为了提高效率。我也可能想多了这个考验

tl;dr，有没有办法以我没有想到的方式并行化 find_end？

Answer 1

是的，有办法。

让 N 成为您要查找的范围的大小。

一旦你将 vector 分成 3 个 block (3 个独立的工作线程):

1 2 3|4 5 1|2 3 8

您可以允许每个线程运行 N-1 个元素的右侧相邻 block (如果有的话)(因为序列上只涉及读取操作，这非常好并且线程安全)。

在这种情况下:(N = 2)

• 核心 1 在 1 2 3 4

  上运行

• Core 2 在 4 5 1 2

  上运行

• Core 3 在 2 3 8

  上运行