在fortran中尽可能快地查找随机列表之间的匹配(+openmp)

Question

我有两个列表，我需要将一个列表中的元素与另一个列表中的元素进行匹配，并将这些元素输出到一个新的矩阵(输出)中。在Fortran中实现这一点的最快方法是什么？目前为止的暴力行为：

do i = 1,Nlistone
   do j = 1,Nlisttwo
     if A(i).eq.B(j) then
        output(i) = B(j)
     end if
   end do
end do

openmp版本：

!$OMP PARALLEL PRIVATE(i,j)
do i = 1,NA
   do j = 1,NB
     if A(i).eq.B(j) then
        filtered(i) = A(j)
     end if
   end do
end do
!$OMP END PARALLEL DO

当然，有更好的方法可以做到这一点，并且排序在这里不是一个选项，对不起(+向量元素没有任何特定的顺序)。在python中有类似于mask的布尔参数吗？

Answer 1

使用内部ANY函数可能会更快，如下所示

do i = 1,Nlistone
     if (any(B==A(i))) output(i) = A(i)
end do

但我不敢打赌这会提高性能，我会同时测试两个版本。您应该能够安全地将其包装在!$OMP PARALLEL DO构造中，因为output的每个元素只由一个线程写入。

Answer 2

您还可以在使用相同语法的forall或(较新的) do concurrent构造中包含条件测试：

do concurrent(i = 1:Nlistone, any(a(i) == b)) 
  output(i) = a(i)
end do

这可能比您的代码清单更快，这取决于A和B的性质。但是它仍然具有O(n^2)的时间复杂度，而排序可以是O(n*log(n))。如果为Nlistone /= Nlisttwo，则可以通过仅循环较短的数组并将其元素与较长的数组进行匹配来获得等于这些大小的比率的因子。