向量迭代排序的高效算法

Question

假设我有一个由连续整数组成的扰乱向量 1:n，比如 {3,6,2,1,4,5}。我的问题是为每个元素找到其左侧小于自身的元素数。因此，对于此示例，我希望程序 return {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 21=] 在临时向量中。下一次迭代然后将临时向量中的适当元素作为小于自身的元素的计数。我的问题是：

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

Answer 2

完全重写答案。如果内存不是问题，您可以添加另一个向量并使用如下所示的算法。附加向量用于计算排列。由于原始向量是整数 1 到 n 的排列，排列的计算时间复杂度为 O(n)。在我的计算机上使用大小为 100k 的向量，该算法平均运行 1.9 秒（100 次运行），第 0 个初始命题平均运行 2.8 秒。我推荐这个解决方案只是因为 zeroth 说他没有测试他的新解决方案，你将测试并使用最好的。

subroutine iterrank(n,invec,outvec,tempvec,ord)
    implicit none
    !
    integer :: n, i, currPos, prevPos, currOut, prevOut
    integer, dimension(n) :: invec, outvec, tempvec,ord
    !
    tempvec = 0
    do i = 1, n
        ord(invec(i)) = i
    end do
    !
    currPos = ord(1)
    tempvec(currPos) = 1
    currOut = 0
    outvec(currPos) = currOut
    ! last = 0
    do i = 2 , n
        prevPos = currPos
        currPos = ord(i)
        !
        if(currPos>prevPos)then
            currOut = currOut+sum( tempvec(prevPos:currPos) )
        else
            currOut = sum( tempvec(1:currPos) )
        end if
        !
        outvec(currPos) = currOut
        tempvec(currPos) = 1
    end do
    !
end subroutine iterrank

此解决方案的缺点是对向量 outvec 和 tempvec 的随机访问，没有充分利用高速缓存和寄存器。有可能解决这个问题并显着减少时间，可能以额外的临时向量为代价。

向量迭代排序的高效算法

Efficient algorithm for iterative ranking of a vector

fortran

ranking