Фортран: разреженные массивы или списки - PullRequest
Новая
       12

Фортран: разреженные массивы или списки

2 голосов
/ 13 января 2012

Есть ли реализация разреженных массивов или эквивалентных списков в 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

Для простоты теперь мы используем обычные массивы в Фортране, где для n<=1000 это n*n. Как видите, это очень неэффективная идея для больших размеров. Любое решение?

Ответы [ 2 ]

4 голосов
/ 13 января 2012

Решение без связанного списка.

Здесь предполагается, что векторы "r" содержат значения двойной точности.

Обратите внимание, что в этом решении не используются указатели, а только размещаемые массивы, что позволяет избежать утечек памяти. Количество перераспределений ограничено (log2 (список% n)), но можно согласиться выделить список% результата с размером, который больше необходимого (максимум в два раза)

Наконец, векторы "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
0 голосов
/ 13 января 2012

Вас может заинтересовать использование Judy-Arrays через ISO-C-Binding. Он предоставляет вам функциональность динамических разреженных массивов. В противном случае я бы рекомендовал решение Francois Jacq, возможно, с добавлением дополнительного отсортированного списка записей, чтобы выполнить бинарный поиск по заданным значениям, если вам это нужно. В моем опыте оба подхода работают достаточно хорошо.

...