搜索数组n和m的一个好算法是什么,以便找到n中也存在于m中的元素?

1000是一个非常小的数字。另外,请记住,并行搜索只会随着内核数量的增加而加速。如果线程多于核心,则由于上下文切换和聚合信息,应用程序将再次开始减速。

对于您的问题,一个简单的解决方案是使用哈希连接。从生成哈希表 M ,然后查找 N 在它中(或者反之亦然;因为两个数组都很小,所以没什么关系)。

编辑 :作为对你的评论的回应,我的回答变化不大。只有当线程数等于处理器数,而不是超过处理器数时,才能线性加速。

如果您想要实现一个并行散列连接,这并不困难。首先构建X-1哈希表,其中X是您拥有的线程/处理器数量。使用第二个散列函数返回值modulo x-1,以确定每个元素应位于哪个散列表中。

在执行搜索时,您的主线程可以将辅助哈希函数应用于每个元素,以确定要将其传递给哪个线程进行搜索。

只需对n进行排序。然后对m的每个元素进行二进制搜索,搜索排序后的n。即使对大小为12的未排序n进行线性搜索,在n中查找m项也是非常平行的。