查看一组值是否出现在数组中的有效方法? [英] Efficient way to see if a set of values appear in an array?

问题描述

我正在尝试检查 A 的一维整数数组是否包含在其 size(A)位置的每个位置上的任何元素整数集 S (也是一维数组)，一般情况为 size(S)> 1 .

I'm trying to check if an 1D array of integers A contains or not, at every one of it's size(A) positions, any of the elements of the set of integers S (also a 1D array), with the general case of size(S) > 1.

简单明了的方法是执行以下嵌套循环:

The easy and obvious way is to do the following nested loop:

DO i = 1, size(A)
   DO j = 1, size(S)
        IF(A(i) == S(j)) ** do something **
   ENDDO 
ENDDO

问题在于，对于大型数组 A 和 S ，此过程效率很低.是否有一个内在的FORTRAN子例程或函数可以更快地执行此操作?或其他任何方法?

The problem is that, for large arrays A and S, this process is very inefficient. Is there an intrinsic FORTRAN subroutine or function that does this faster? Or any other method?

我尝试执行以下操作，但是它不想编译:

I've tried to do the following, but it doesn't want to compile:

DO i = 1, NNODES
   IF(A(i) == ANY(S)) ** do something **
ENDDO

出现的错误消息如下:"错误#6362:自变量的数据类型无效."我正在将VS2010与Intel Parallel Studio 2013一起使用.

The error message that appears is the following: "error #6362: The data types of the argument(s) are invalid." I'm using VS2010 with Intel Parallel Studio 2013.

推荐答案

表达式

A(i) == ANY(S)

在 lhs 上有一个整数，在 rhs 上有一个逻辑.在C语言的启发下，我们不会把Fortran中的可比类型视作废话.实际上，比这更糟糕的是， any 返回一个逻辑，但是在输入时采用逻辑数组，因此 any(array_of_int)不会编译.

has an integer on the lhs and a logical on the rhs. We'll have none of that C-inspired nonsense of regarding those as comparable types in Fortran thank you very much. Actually, it's worse than that, any returns a logical but takes an array of logicals on input, so any(array_of_int) won't compile.

您可以尝试

ANY(S==A(i))

相反.那应该给你一个可编译的解决方案.

instead. That should give you a compilable solution.

现在，关于效率，您的第一段代码是 O(n ^ 2).您可以渐近地做得更好.对两个数组进行排序并一并扫描，这是 O(n + n log n)或类似的形式.如果您需要帮助进行编码，请更新您的问题，尽管我怀疑已经在SO上对其进行了询问和回答.

Now, as for efficiency, you're first snippet is O(n^2). You can do better, asymptotically. Sort both arrays and scan them in tandem, which is O(n + n log n) or something similar. If you need help coding that up, update your question, though I suspect it's already been asked and answered here on SO.

我强烈怀疑，您可以检查一下是否愿意在单个(显式)循环中使用 any 也是 O(n ^ 2)--由于 any 必须在最一般的情况下进行操作，因此我看不到任何可行的替代方法来扫描数组-换句话说就是另一个循环.

I strongly suspect, and you can check if you care to, that using any inside a single (explicit) loop will also be O(n^2) -- since any has to operate on the most general cases I can't see any realistic alternative to it scanning the array -- another loop in other words.

这篇关于查看一组值是否出现在数组中的有效方法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！