MergeSort против сглаживания - PullRequest
Новая
       39

MergeSort против сглаживания

2 голосов
/ 27 июня 2019

У меня есть следующая реализация алгоритма MergeSort в Fortran.

Мой вопрос о call merge(work(1 : half), A(half + 1:), A). Очевидно, у меня перекрывающаяся память, но, глядя на код в merge, с этим проблем не возникнет, если входные массивы отсортированы. (Которым они все равно предполагаются.)

С другой стороны, компиляторы Фортрана могут предполагать не псевдоним памяти, поэтому я всегда думаю «не делай этого».

У меня сейчас два вопроса:

  1. Когда и как я могу столкнуться с проблемами с моей подпрограммой merge.
  2. Если я не могу реализовать MergeSort таким образом, как мне это сделать, не создавая временный массив. 
!> Merge sorted arrays A and B into C while preversing order.
        subroutine merge(A, B, C)
        implicit none
        integer, intent(in) :: A(:), B(:)
        integer, intent(inout) :: C(:)

        integer :: i, j, k

        if (size(A) + size(B) > size(C)) abort

        i = 1; j = 1
        do k = 1, size(C)
          if (i <= size(A) .and. j <= size(B)) then
            if (A(i) <= B(j)) then
              C(k) = A(i)
              i = i + 1
            else
              C(k) = B(j)
              j = j + 1
            end if
          else if (i <= size(A)) then
            C(k) = A(i)
            i = i + 1
          else if (j <= size(B)) then
            C(k) = B(j)
            j = j + 1
          end if
        end do
      end subroutine merge

      recursive subroutine MergeSort(A, work)
        implicit none
        integer, intent(inout) :: A(:)
        integer, intent(inout) :: work(:)

        integer :: half
        half = (size(A) + 1) / 2
        if (size(A) < 2) then
          continue
        else if (size(A) == 2) then
          call naive_sort(A)
        else
          call MergeSort(A( : half), work)
          call MergeSort(A(half + 1 :), work)
          if (A(half) > A(half + 1)) then
            work(1 : half) = A(1 : half)
! TODO: Non aliasing rule.
            call merge(work(1 : half), A(half + 1:), A)
          endif
        end if
      end subroutine MergeSort

PS: Как вы, возможно, заметили, массив C в подпрограмме merge объявлен как параметр inout, поскольку позднее он используется с перекрывающейся памятью.

1 Ответ

0 голосов
/ 28 июня 2019

Использование псевдонимов при вызове merge ошибочно.

При 

call merge(work(1 : half), A(half + 1:), A)

фиктивный аргумент B связан с A(half+1:), а фиктивный аргумент Cс A, который понимается как перекрытие.

Этот псевдоним означает, что элементы B не могут быть определены (что дополнительно требуется намерением) и что последние несколько элементов C могутне может быть определено.

Однако, если мы посмотрим на основной цикл в merge, мы увидим, что в целом каждый элемент C появляется в выражении, похожем на C(k)=...: мы ожидаем, по крайней мере, один изэти условия внутри, чтобы быть правдой.Следовательно, это недопустимо.

Для ясности: утверждение типа C(k)=B(j) будет недопустимым определением, даже если в результате значение C(k) не изменится.

К счастью,возможно, существует простой способ создать временный массив, чтобы избежать наложения псевдонимов: дать фиктивный аргумент B атрибут value.Вы можете сделать то же самое с A и удалить массив рабочей области.

...