Fortran:设置操作 [英] Fortran: Set operations

问题描述

Fortran::有两个大的整数数组，目的是找出它们是否有共同的数字，如何?
您可能会认为两者的大小相同(情况1)或大小不同(情况2).它们也可能有许多重复的通用数字，因此应进行处理以避免不必要的搜索或运算符. 最简单的方法是进行不合适的蛮力搜索.我们正在考虑与 Python 类似的SET操作，如下所示:

Fortran: There are two large arrays of integers, the goal is to find out if they have any number in common or not, how?
You may consider that both are in the same size (case 1) or in different sizes (case 2). It is possible also that they have many common numbers repeated, so this should be handled to avoid unnecessary search or operators. The simplest way is to do Brute-Force search which is not appropriate. We are thinking about SET operations similar to Python as the following:

a = set([integers])
b = set([integers])
incommon = len(a.intersection(b)) > 0    #True if so, otherwise False

例如:

a = [1,2,3,4,5]
b = [0,6,7,8,9]
sa = set(a)
sb = set(b)
incommon = len(sa.intersection(sb)) > 0
>>> incommon: False
b = [0,6,7,8,1]
incommon = len(sa.intersection(sb)) > 0
>>> incommon: True

如何在Fortran中实现此功能?请注意，数组的大小很大(> 10000)，该操作将重复一百万次！

How to implement this in Fortran? note that arrays are of large size (>10000) and the operation would repeat for million times!

更新: [关于该问题的评论]我们绝对尝试了许多我们知道的方法.如前所述，例如BFS方法.它可以工作，但是效率不高，原因有二:1)该方法的性质需要大量的迭代，2)我们可以实现的代码. (yamajun所接受的答案)对我们的信息远不止于问题本身.快速排序，收缩和Isin的实现都非常容易想到和优雅地实现.我们非常感谢这种迅速而完善的解决方案.

Updates: [regarding the comment for the question] We absolutely have tried many ways that we knew. As mentioned BFS method, for example. It works but is not efficient for two reasons: 1) the nature of the method which requires large iterations, 2) the code we could implement. The accepted answer (by yamajun) was very informative to us much more than the question itself. How easy implementation of Quick-Sort, Shrink and Isin all are very nicely thought and elegantly implemented. Our appreciation goes for such prompt and perfect solution.

推荐答案

也许可以.

从此处添加

主要思想是使用内部函数ANY().

The main idea is using intrinsic function ANY().

1. ANY(x(:) == y)返回.true.如果数组x中存在标量值y.当y也是数组时，ANY(x == y)返回x(1)== y(1)& x(2)== y(2)& ...，因此我们必须对y的每个元素使用do循环.

现在，我们尝试删除数组中的重复数字.

Now we try to delete duplicate numbers in the arrays.

1. 首先，我们对数组进行排序.快速排序可以像Haskell一样简洁地编写. (参考:Arjen Markus，ACM Fortran论坛27(2008)2-5.) 但是由于递归会消耗堆栈，因此Shell-sort可能是更好的选择，因为它不需要额外的内存.教科书中经常说Shell-sort在O(N ^ 3/2〜5/4)中工作，但是使用特殊的gap函数可以更快地工作.

1. First we sort the arrays. Quick-sort can be written concisely in a Haskell-like manner. (Reference : Arjen Markus, ACM Fortran Forum 27 (2008) 2-5.) But because recursion consumes stacks, Shell-sort might be a better choice, which does not require extra memories. It is often stated in textbooks that Shell-sort works in O(N^3/2~5/4), but it works much faster using special gap functions.wikipedia

接下来，我们通过使用zip对的想法比较连续的元素来删除重复的数字. [x(2)/= x(1)，...，x(n)/= x(n-1)]我们需要添加一个额外的元素以匹配数组大小.固有函数PACK()用作过滤器.

Next we delete duplicate numbers by comparing successive elements using the idea of zip pairs. [x(2)/=x(1), ..., x(n)/=x(n-1)] We need to add extra one element to match array size. The intrinsic function PACK() is used as a Filter.

到这里

  program SetAny
    implicit none
    integer, allocatable :: ia(:), ib(:)
! fortran2008
!    allocate(ia, source = [1,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5])
!    allocate(ib, source = [0,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9])
    allocate(ia(size([1,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5])))
    allocate(ib(size([0,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9])))
    ia = [1,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5,2,3,4,5]
    ib = [0,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9,6,7,8,9]

    print *, isin( shrnk( ia ), shrnk( ib ) )
    stop
contains
  logical pure function isin(ia, ib)
    integer, intent(in) :: ia(:), ib(:)
    integer :: i
    isin = .true.
    do i = 1, size(ib)
      if ( any(ia == ib(i)) ) return 
    end do
    isin = .false.
    return
  end function isin

  pure function shrnk(ia) result(res)
    integer, intent(in) :: ia(:)
    integer, allocatable :: res(:) ! f2003
    integer :: iwk(size(ia))
    iwk = qsort(ia)
    res = pack(iwk, [.true., iwk(2:) /= iwk(1:)]) ! f2003
    return
  end function shrnk

  pure recursive function qsort(ia) result(res)
    integer, intent(in) :: ia(:)
    integer :: res(size(ia))
    if (size(ia) .lt. 2) then 
     res = ia
    else
     res = [ qsort( pack(ia(2:), ia(2:) < ia(1)) ), ia(1), qsort( pack(ia(2:), ia(2:) >= ia(1)) ) ]
    end if
    return
  end function qsort

end program SetAny

壳排序

  pure function ssort(ix) ! Shell Sort
    integer, intent(in) :: ix(:)  
    integer, allocatable :: ssort(:)
    integer :: i, j, k, kmax, igap, itmp
    ssort = ix
    kmax = 0
    do  ! Tokuda's gap sequence ; h_k=Ceiling( (9(9/4)^k-4)/5 ), h_k < 4N/9 ; O(N)~NlogN 
      if ( ceiling( (9.0 * (9.0 / 4.0)**(kmax + 1) - 4.0) / 5.0 ) > size(ix) * 4.0 / 9.0 ) exit
      kmax = kmax + 1
    end do

    do k = kmax, 0, -1
      igap = ceiling( (9.0 * (9.0 / 4.0)**k - 4.0) / 5.0 )
      do i = igap, size(ix)
        do j = i - igap, 1, -igap
          if ( ssort(j) <= ssort(j + igap) ) exit
            itmp           = ssort(j)
            ssort(j)       = ssort(j + igap)
            ssort(j + igap) = itmp
          end do
        end do
      end do
    return
  end function ssort

这篇关于Fortran:设置操作的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！