fortran - 向量迭代排序的高效算法

Question

假设我有一个由连续整数 1:n 组成的扰乱向量，例如 {3,6,2,1,4,5}。我的问题是为每个元素找到其左侧小于自身的元素数。所以我希望程序为这个例子返回 {0,1,0,0,3,4}。这是我用 Fortran 写的:

subroutine iterrank(n,invec,outvec,tempvec)
    implicit none

    integer :: n, i, currank
    integer, dimension(n) :: invec, outvec, tempvec

    tempvec = 0
    outvec = 0
    do i = 1,n
        currank = invec(i)
        outvec(i) = tempvec(currank)
        tempvec(currank:n) = tempvec(currank:n) + 1
    end do

    return
end subroutine

它采用一个临时数组(向量)，对于循环遇到的每个数字 d，它都会向临时向量中超出位置 d 的每个元素加 1。下一次迭代然后将临时向量中的适当元素作为小于自身的元素的计数。我的问题是:

1) 我认为这是 O(n^2) 的复杂度，因为在循环的每次迭代中都有 O(n) 次写入临时向量。我说得对吗？

2) 对于较大的 n(比如 >100k)，是否有更有效的方法？

Answer 1

我相信这会更有效率，您也可以将临时整数数组减少为单个字节。

subroutine iterrank(n,invec,outvec,tempvec)
    implicit none

    integer :: n, i, currank
    integer, dimension(n) :: invec, outvec, tempvec

    tempvec = 0
    !outvec = 0 ! no need to initialize something overwritten below
    do i = 1 , n
        currank = invec(i)
        outvec(i) = sum( tempvec(1:currank) )
        tempvec(currank) = 1
    end do

end subroutine

好处是您只为每个索引写入两次，但是您最多读取元素 n*n 次。

编辑:

我还没有尝试过这个，但它应该会减少读取次数，并且可能会产生分支开销。对于非常大的数组来说它可能更快，但是我希望它对于短数组来说会更慢:

subroutine iterrank(n,invec,outvec,tempvec)
  implicit none

  integer :: n, i, currank, prevrank
  integer, dimension(n) :: invec, outvec, tempvec

  tempvec = 0
  outvec(1) = 0
  tempvec(invec(1)) = 1
  do i = 2 , n
     prevrank = invec(i-1)
     currank = invec(i)
     if ( abs(prevrank-currank) > currank ) then
        outvec(i) = sum( tempvec(1:currank) )
     else if ( prevrank < currank ) then
        outvec(i) = outvec(i-1) + sum( tempvec(prevrank:currank) )
     else
        outvec(i) = outvec(i-1) - sum( tempvec(currank:prevrank-1) )
     end if
     tempvec(currank) = 1
  end do

end subroutine iterrank