c++ - 并行 For 循环：查找已排序数组是否包含重复元素

这是一个巨大的数组，其中包含升序排列的元素。我们需要查找数组是否包含任何重复元素。蛮力方法很简单，当我们遍历循环时，如果对于任何给定的索引 i，a[i] == a[i+1]，我们可以提前返回指示数组包含重复元素。

但是，在多核环境中，我们绝对可以通过并行运行多个 for 循环来提高性能，每个循环处理输入循环的一部分。我们如何在那里实现同步？提前返回如何工作？

标签： c++multithreadingconcurrencysynchronization

您必须检查具有告诉循环提前结束的同步变量的性能是否比让线程运行通过数组的子集并在它们找到某些东西时返回。如果您没有无锁原子 bool，那么让线程运行到子集的末尾，然后同步可能会更快。

算法本身很简单，你只需要确保你处理了极端情况。假设您的数据集是

1, 2, 3, 4, 4, 6, 7, 8

你把它分成4个偶数线程。线程会得到

thread 1: 1, 2
thread 2: 3, 4
thread 3: 4, 6
thread 4: 7, 8

并且每个线程都不会找到重复项，因为重复的条目跨越两个不同的线程。这意味着每个线程都需要有一个子集，该子集通过一个元素与其他子集重叠，以便您可以找到重复项。这意味着线程应该真的像

thread 1: 1, 2, 3
thread 2: 3, 4, 4
thread 3: 4, 6, 7
thread 4: 7, 8 // the last thread does need to overlap anything

有了它，您可以线性检查每个子集a[i] == a[i+1]，如果存在，您可以保证找到重复项。

您无需担心同步对向量内容的读取操作。只要在检查时向量没有被修改，就可以让多个阅读器同时读取它。只有当您有多个线程并且其中一个或多个线程写入共享数据时，您才需要同步。