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

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

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

Обратите внимание, что это решение не использует указатель, просто выделяемые массивы, что гарантирует, что утечки памяти не будут устранены. Количество перераспределений ограничено (log2 (list% 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  

Answer 2

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