查看一组值是否出现在数组中的有效方法? [英] 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屋!