Fortranのリンクリスト

この記事に書いてあること

本記事では、どのようなデータ型でも保存できるfortranのリンクリストを紹介します。リスト内要素のソートメソッドや、各要素に同一のルーチンを適用するためのメソッドも付属しています。
なお、これらの機能の実装にはfortran2003以降のオブジェクト指向機能を用いました。ソースコードは、ここ からgit cloneできます。詳しい使い方は cloneしたフォルダの app/test_doubly_linkedlist.f90を見てください。

以下では「オブジェクト」という語を用いて表記している箇所が多数でてきます。これらは、f03以降で取り入れられたオブジェクト指向の機能を用いた type または class で定義された変数と思ってください。

Fortranでリンクリストを作る動機

数値解析を行うにあたって、データの組を複数用意する状況は無数にあります。例えば、車に関連する解析を考えた場合、タイヤ、車体、駆動方式、部品形状などの違いが解析結果に変化をもたらすでしょう。

車の一部のデータのみを変更して解析を実施したい場合、予め準備した部品データオブジェクトのリストから必要な部分のみを取り出す汎用的な仕組みがあれば、データ管理の手間が大きく軽減できます。数値解析で使う巨大配列の何番目の要素が何を意味するかという紐づけ部分のデータ管理は、データオブジェクトのメソッドとして作り上げておくのが私の方針です。

そこで、「データオブジェクト管理の汎用的な仕組み」として、ユーザ定義型を含むどのようなデータ型であっても、何も気にすることなく何個でもデータを追加できる型 t_list を定義したモジュールを公開しました。また、リスト内部の要素取り出しや値の更新を容易にするため、 t_elementptr という型を定義し、リスト内の任意の位置を指すことができる型も用意しました。これらの型を使うことで、

• 〇〇部品の物性を変えたリスト
• 組立品の部品配置に関する定義リスト
• 組み立て品の群（組立品が複数あって、それらがどのように相互に影響するかの定義）

といった階層的なデータ構造の管理がとても楽になります。構築したデータオブジェクトのリストから、数値解析を始める前に1度だけ、数値解析に適した巨大な配列に変換することで、計算負荷の大きい部分ではガリガリにf77っぽく速度チューニングすることも可能になり、オブジェクト指向の利便性とfortranの数値解析に対する優位性を両立させることが簡単になります。

利用例1(要素の追加、削除、配列ライクな扱い)

• データは、append手続きに位置を指定しなければ、処理高速化のため、常にリスト内部構造の先頭に追加されます。
• getobj()で返されるオブジェクトはclass(*)のポインタであってコピーではないので、このポインタを使った演算は、リストの要素を直接書き換えることになります。

プログラムの流れ

1. まず、doループで10個の整数をリストに追加
2. 生成されたリストを、代入演算子でコピー。なお、この代入演算子は「assign(=)」で関連付けたユーザ定義型が呼び出されています。
3. リスト一覧を showallメソッドでプロンプトに表示します。組み込み型は自動判別して表示されるようにしています。
4. リスト代入文は、繰り返し呼んでもメモリ開放とアロケートが自動的に適用されます。
5. リスト要素数分の繰り返し処理をします。（gitのオリジナル例題では、applyメソッドでも同じことができます。）
   1. リスト要素を示すelmポインタを取得。
   2. ポインタの指示先がinteger型であれば、値を2倍にする。
6. リスト要素をすべて表示。
7. リスト要素を初期化
8. リストの3,8番目要素を削除
9. リスト要素をすべて表示。

program usage1
    use iso_fortran_env
    use doubly_linkedlist 
    implicit none
    type(t_list) :: list,list_initial !define linked list data type        type(t_elementptr),dimension(:),allocatable :: as_array
    class(*),pointer :: elm => null() !要素を直接扱うための変数
    integer :: i,n
    ! generate new list      
    n=10
    do i=1,n
        call list%append(i) !ここでは整数iを追加
    end do
    !---
    list_initial=list !save initial data (t_listのメソッドをアサイン)
    !---
    print *, "Show all elements in the list"
    call list%showall()
    print '(1X,A,I5,A)', "Before 'delall' method, exist",list%count()," elements."
    !---
    ! delete all elements
    call list%delall()
    print '(1X,A,I5,A,/)', "After 'delall' method, no elements in the list. Now exist",list%count()," elements."
    call list%showall()
    !---
    ! restore initial elements
    list=list_initial !現在のリストがdeallocateされて、新しくコピーされる
    !---
    ! リストの要素を配列のように添字で表現する場合の記述例
    print *,"How to treat list like array (each element is doubled)"    as_array = list%listarray()
    do i=1,list%count()
        elm => as_array(i)%getobj()
        select type(elm)
        type is(integer)
            elm = elm *2
        end select
    end do
    call list%showall()
    !---
    ! destoroy exist elements and restore initial elements
    print *, "要素 3番目 から 8番目 をリストから削除"
    list=list_initial
    deallocate(as_array)
    as_array = list%listarray()
    ! delete 3 to 8th element
    do i=3,8
        call list%delete(as_array(i))
    end do
    call list%showall()
end program

結果は次の通り

Show all elements in the list
 Item 1/10;   10
 Item 2/10;   9
 Item 3/10;   8
 Item 4/10;   7
 Item 5/10;   6
 Item 6/10;   5
 Item 7/10;   4
 Item 8/10;   3
 Item 9/10;   2
 Item 10/10;   1
 Before 'delall' method, exist   10 elements.
 After 'delall' method, no elements in the list. Now exist    0 elements.

 How to treat list like array (each element is doubled)
 Item 1/10;   20
 Item 2/10;   18
 Item 3/10;   16
 Item 4/10;   14
 Item 5/10;   12
 Item 6/10;   10
 Item 7/10;   8
 Item 8/10;   6
 Item 9/10;   4
 Item 10/10;   2
 delete 3 to 8 elements
 Item 1/4;   10
 Item 2/4;   9
 Item 3/4;   2
 Item 4/4;   1

利用例2(異なる型の保存)

• type(t_list)の中には、どのような型でも、スカラであれば追加できます。

program usage1
    use iso_fortran_env
    use doubly_linkedlist 
    implicit none
    type(t_list) :: list,list_initial !define linked list data type
    type(t_elementptr) :: elo ! object to treat a lement
    type(mydata) :: udt ! user defined data type
    integer :: i
    print *,"! Any data type can be stored."
    print *,"! user defined type can't print data.(printed as 'unrecognised item' as default)."
    call list%append((2.0,1.0)) !complex float
    call list%append((2d0,1d0)) !double
    call list%append(.TRUE.)    !logical
    call list%append(udt) !user defined type
    call list%append("character") !character
    call list%append(4d0)       !scalar double
    call list%showall() !リスト一覧を表示(ユーザ定義型はunknownとなる)
    print *,"! user defined type can be printed (if user defined print procedure is passed)."
    call list%showall(showfun) !関数showfunを渡すとユーザ定義型を表示できる
    !3番目のデータを削除
    print *,"! delete 3rd object"
    call elo%init(list) !elo(element of list object)でlist内部を操作する為の初期化
    call elo%next() !初期化直後は最初の要素なので、次の要素を指すようにする。
    call elo%next()
    write(output_unit,'(1x,"! 3rd element of list :")',advance='no')
    call list%show(elo) !eloが指すオブジェクトを表示
    call list%delete(elo) !eloが指すオブジェクトを削除
    call list%showall(showfun) !削除後のリストを表示
    !--
    call elo%tail() !eloがリスト最後尾を指すようにする
    write(output_unit,'(1x,"! and delete tail element of list :")',advance='no')
    call list%show(elo)
    call list%delete(elo)
    call list%showall(showfun)
    !-----
    write(output_unit,'(1x,"! pointer does not break if you apply the oversize roop :")')
    call elo%tail()
    do i=1,list%count()+2 !リスト要素数を超えてnext,prev操作をしても、リスト先頭または末尾のままとなる
        call list%show(elo)
        call elo%prev()
    end do
end program

実行結果は次の通り。

! Any data type can be stored.
 ! user defined type can't print data.(printed as 'unrecognised item' as default).
 Item 1/6;   4.0000000000000000
 Item 2/6;   character
 Item 3/6;   unrecognised item
 Item 4/6;   T
 Item 5/6;   (2.0000000000000000,1.0000000000000000)
 Item 6/6;   (2.00000000,1.00000000)
 ! user defined type can be printed (if user defined print procedure is passed).
 Item 1/6;   4.0000000000000000
 Item 2/6;   character
 Item 3/6;   UserDefinedType:(hoge, 2)
 Item 4/6;   T
 Item 5/6;   (2.0000000000000000,1.0000000000000000)
 Item 6/6;   (2.00000000,1.00000000)
 ! delete 3rd object
 ! 3rd element of list : unrecognised item
 Item 1/5;   4.0000000000000000
 Item 2/5;   character
 Item 3/5;   T
 Item 4/5;   (2.0000000000000000,1.0000000000000000)
 Item 5/5;   (2.00000000,1.00000000)
 ! and delete tail element of list : (2.00000000,1.00000000)
 Item 1/4;   4.0000000000000000
 Item 2/4;   character
 Item 3/4;   T
 Item 4/4;   (2.0000000000000000,1.0000000000000000)
 ! pointer does not break if you apply the oversize roop :
 (2.0000000000000000,1.0000000000000000)
 T
 character
 4.0000000000000000
 4.0000000000000000
 4.0000000000000000

配列をリストに格納したいときは

このモジュールは、リスト要素がclass(*)なので、appendできるのはスカラ型のみです。配列をリストに追加したいときは、ユーザ定義型で

type mydata
    real(real64) :: x(100)
end type
type(mydata) :: mydatatype

などとして、mydatatype をリストにappendするのが一つの解決策となり得ます。

もしくは、リスト構造のみを定義するモジュールを新たに作り、これをextendして、格納したい配列などのデータを含む型を定義する方が良いのかもしれません。

おわりに

実用に供する際のコメントを付して終わりにします。

計算速度について

計算速度に関しては、このモジュールによるデータの追加と削除はそれほど早くありません。
ましてや、数値解析中にこのモジュールによるデータの操作を入れることは、全くオススメしません。あくまで、数値解析の前後で利用することを前提とすべきです。

ポインタを含む型をリストに入れる場合

このモジュールで定義した型については、assignment(=)等を用いてメモリリークを起こさないように気をつけたつもりです。一方、リストに入れるユーザ定義型の中にポインタが含まれる場合、その指示先がどのようになるかはプログラマの責任で記述してください。
ポインタを含む型は、assignment(=)などでコピー時のポインタの状態を規定しておくのが良いと思います。

他のリンクリストモジュール

詳しく見ていませんが、下記のようなモジュールがgithubで公開されているようです。

• Doubly Linked List for Fortran 2003
• The Fortran Template Library