Fortran:设置操作

Question

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

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),操作将重复数百万次!

更新: [关于问题的评论]我们绝对尝试了很多我们所知道的方法.例如,如BFS方法所述.它有效但效率不高有两个原因:1)需要大量迭代的方法的性质,2)我们可以实现的代码.接受的答案(由yamajun提供)对我们来说非常有益,而不仅仅是问题本身.Quick-Sort,Shrink和Isin的实现非常简单,并且非常好地实现了.我们赞赏这种迅速和完美的解决方案.

Answer 1

也许这会奏效.

从这里添加

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

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

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

1. 首先我们对数组进行排序.快速排序可以像Haskell一样简洁地编写.(参考:Arjen Markus,ACM Fortran论坛27(2008)2-5.)但是因为递归消耗堆栈,Shell-sort可能是更好的选择,不需要额外的记忆.在教科书中经常说明Shell-sort在O(N ^ 3/2~5/4)中工作,但使用特殊的间隙函数它的工作速度要快得多.维基百科

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

到这里

  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