Fortran：稀疏数组或列表

Question

有没有在Fortran中实现稀疏数组或类似的列表呢？

在处理大数据集时，我们可能会把一个大小为n=10000的数组传递给一个子程序，让它对这些数据进行一些操作。比如，找出数组中相似的元素，并依次列出每个项目的相似项。也就是说，对于第一个项目，我们需要在整个列表（数组）中找到所有相似的项目，并把结果记录下来。由于每个元素的相似项可能很多，所以结果可能会很庞大。需要注意的是，我们用来判断相似性的标准不是对称的，这意味着我们需要对所有项目进行全面的评估。因此，结果的长度可能会根据使用的标准而不同。因此，存储所有结果就需要使用稀疏数组或列表，而在Python中可以这样实现：

R = an array             # an array
L = []                   # list initialization
for e in R:              # iteration on all elements of R 
    r = similars(e,R,criteria)  # r is array & different in size for each element
    L.append(r)          # store the ranks in list L

为了简单起见，现在我们在Fortran中使用普通数组，当n<=1000时，它的大小是n*n。如你所见，这对于更大的数据集来说是一个非常低效的做法。有没有什么解决办法呢？

Answer 1

你可能会对通过Judy-Arrays来使用ISO-C绑定感兴趣。它可以让你使用动态稀疏数组的功能。如果不想用这个，我推荐Francois Jacq的解决方案，可能还可以加一个额外的排序列表，用来对特定的值进行二分查找，如果你需要这个功能的话。根据我的经验，这两种方法都很好用。

Answer 2

这是一个不使用链表的解决方案。

在这里，我们假设向量“r”包含的是双精度值，也就是比较精确的数字。

注意，这个方案没有使用指针，只用了可分配的数组，这样可以避免内存泄漏的问题。重新分配内存的次数是有限的（大约是log2(list%n)），但我们接受分配的list%result的大小比实际需要的要大（最多可以是两倍）。

最后，向量“r”在列表中是被复制的（而在Python版本中并不是这样）。

module extendable_list

implicit none

type result_type
  double precision,allocatable :: vector(:)
end type

type list_type
  integer :: n
  type(result_type),allocatable :: result(:)
end type

contains

subroutine append(list,r)
  type(list_type),intent(inout) :: list
  double precision,intent(in)   :: r(:)
  type(result_type),allocatable :: temporary(:)
  integer :: i
  if(.not.allocated(list%result)) then
    allocate(list%result(10))
    list%n=0
  else if(list%n >= size(list%result)) then
    allocate(temporary(2*list%n))
    do i=1,list%n
      call move_alloc(list%result(i)%vector,temporary(i)%vector)
    enddo
    call move_alloc(temporary,list%result)
  endif
  list%n=list%n+1
  allocate(list%result(list%n)%vector(size(r)))
  list%result(list%n)%vector=r
end subroutine

end module

program main
  use extendable_list
  implicit none
  type(list_type) :: list
  integer :: i
  do i=1,10
    call append(list,(/1.d0,3.d0/))
    call append(list,(/7.d0,-9.d0,45.d0/))
  enddo
  do i=1,list%n
    write(*,*) list%result(i)%vector
  enddo
end program

结果：

coul@b10p5001:~/test$ ifort t65.f90
coul@b10p5001:~/test$ ./a.out
   1.00000000000000        3.00000000000000     
   7.00000000000000       -9.00000000000000        45.0000000000000     
   1.00000000000000        3.00000000000000     
   7.00000000000000       -9.00000000000000        45.0000000000000     
   1.00000000000000        3.00000000000000     
   7.00000000000000       -9.00000000000000        45.0000000000000     
   1.00000000000000        3.00000000000000     
   7.00000000000000       -9.00000000000000        45.0000000000000     
   1.00000000000000        3.00000000000000     
   7.00000000000000       -9.00000000000000        45.0000000000000     
   1.00000000000000        3.00000000000000     
   7.00000000000000       -9.00000000000000        45.0000000000000     
   1.00000000000000        3.00000000000000     
   7.00000000000000       -9.00000000000000        45.0000000000000     
   1.00000000000000        3.00000000000000     
   7.00000000000000       -9.00000000000000        45.0000000000000     
   1.00000000000000        3.00000000000000     
   7.00000000000000       -9.00000000000000        45.0000000000000     
   1.00000000000000        3.00000000000000     
   7.00000000000000       -9.00000000000000        45.0000000000000