Фортран: Операции над множествами

Question

Фортран: Существует два больших массива целых чисел, цель состоит в том, чтобы выяснить, имеют ли они какое-либо общее число или нет, как?
Вы можете считатьоба имеют одинаковый размер (случай 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

Как реализовать этов Фортране? обратите внимание, что массивы имеют большой размер (> 10000), и операция будет повторяться миллион раз!

Обновления: [относительно комментария к вопросу] Мы абсолютноперепробовал много способов, которые мы знали.Как уже упоминалось, метод BFS, например.Это работает, но не эффективно по двум причинам: 1) природа метода, который требует больших итераций, 2) код, который мы могли бы реализовать.Принятый ответ (от yamajun) был для нас гораздо более информативным, чем сам вопрос.Как легко внедрить Quick-Sort, Shrink и Isin, все очень хорошо продумано и элегантно реализовано.Мы ценим такое быстрое и идеальное решение.

Answer 1

Может быть, это сработает.

добавлено отсюда

Основная идея заключается в использовании встроенной функции ANY ().

1. ЛЮБОЙ (x (:) == y) возвращает .true. если скалярное значение y существует в массиве x. Когда y также является массивом, ANY (x == y) возвращает x (1) == y (1) & x (2) == y (2) & ..., поэтому мы должны использовать цикл do для каждого элемента из y.

Теперь мы пытаемся удалить дубликаты чисел в массивах.

1. Сначала мы сортируем массивы. Быстрая сортировка может быть написана лаконично в стиле Haskell. (Ссылка: Арьен Маркус, ACM Fortran Forum 27 (2008) 2-5.) Но поскольку рекурсия использует стеки, сортировка Shell может быть лучшим выбором, который не требует дополнительной памяти. В учебниках часто говорится, что Shell-сортировка работает в O (N ^ 3/2 ~ 5/4), но она работает намного быстрее, используя специальные функции разрыва. wikipedia

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