Question

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

So for example:


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

www.un.org/Depts/DGACM/index_spanish.htm 《》中如何执行这一规定,指出阵列面积大(>10000),行动将重复100万次!

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.

Answer 1

或许这项工作将继续下去。

<>strong> 增自>

主要想法是利用ANY(ANY)的固有功能。

ANY(x(:) == y) returns .true. if a scalar value y exists in an array x. When y is also an array ANY(x == y) returns x(1)==y(1) & x(2)==y(2) &..., so we have to use do loop for each element of y.

现在我们试图删除阵列中的重复数字。

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
其次,我们删除重复数字,根据奶粉的概念对接二连三的内容进行比较。我们需要增加一个因素,以适应阵列的规模。内在功能PACK(PACK)被用作过滤器。

http://www.ohchr.org。

  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:) &lt ia(1)) ), ia(1), qsort( pack(ia(2:), ia(2:) &gt= ia(1)) ) ]
    end if
    return
  end function qsort

end program SetAny

Shell sort

  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 &lt 4N/9 ; O(N)~NlogN 
      if ( ceiling( (9.0 * (9.0 / 4.0)**(kmax + 1) - 4.0) / 5.0 ) &gt 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) &lt= 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

友情链接