Fortranで可変長配列を実装する

Last updated at 2023-12-03Posted at 2023-12-03

誰向け?

Fortran でユーザ定義型を作りたい人向け.
Fortran で競技プログラミングに挑む人向け.
- Graph の問題で隣接リストでグラフを表現することができる.
- Stack が必要な問題で末尾に要素を加えたり, 取り除ける.

適しない人

数値計算
- 配列を可変にする必要はないだろう.

配列のサイズをてきとーに変更する

標準の関数でサイズを変更できるが…
- 自分で配列のサイズを気にして, 手動でサイズ変更するのは面倒くさい!!!
他の言語みたいな機能(push とか)付けて楽したい!!!!!!

program expand_array
  use, intrinsic :: iso_fortran_env
  implicit none
  integer, allocatable :: arr(:)
  integer(int32) :: i
  allocate(arr(4), source = [(i, i = 1, 4)])
  write(output_unit, '(*(i0, 1x))') arr(:)
  call resize(arr, 2 * size(arr))
  arr(5:) = 88
  write(output_unit, '(*(i0, 1x))') arr(:)
contains
  subroutine resize(arr, new_size)
    integer(int32), allocatable, intent(inout) :: arr(:)
    integer(int32), intent(in) :: new_size
    integer(int32), allocatable :: tmp(:)
    integer(int32) :: n
    allocate(tmp(new_size))
    n = size(arr)
    tmp(1:n) = arr(1:n)
    call move_alloc(from = tmp, to = arr)
  end subroutine resize
end program expand_array

他の言語の可変長配列の機能は?

C++ や Rust の可変長配列は末尾に値を代入するメソッドや取り除くメソッドがある.
こういうことを Fortran で再現したい.

fn main() {
    let mut v: Vec<i32> = Vec::new();
    println!("{:?}", v);
    v.push(2);
    v.push(100);
    println!("{:?}", v);
    v.pop().unwrap();
    println!("{:?}", v);
}

[]
[2, 100]
[2]

[]
[2, 100]
[2]

ユーザ定義型を使う

ユーザ定義型¹と型に紐付いた関数²を使う.-
- 利点は変数に対する操作を制限することができる.
- つまり, 自分で配列の長さを変更するのではなく, 型(を作った人)にやってもらうのである.

型を作ろう

とりあえず, 型を定義してみる.
名前は? `myvector` にしよう.
必要なものは?
- 動的に確保できる配列.
- 配列に詰め込まれている要素の数.
- 配列の実際の長さ.
で良いだろう.
外に見せるふるまいは?
- `myvector` に値を後ろに詰め込むことができる.
- `myvector` の `n` 番目の値を見る.
で, とりあえず良いだろうか?

`module` で実際に型を定義する.

module myvector_m
  use, intrinsic :: iso_fortran_env
  implicit none
  private
  public :: myvector
  type :: myvector
     private
     integer(int32), allocatable :: arr_(:) ! 動的に確保できる配列.
     integer(int32) :: size_ ! 配列の要素数.
     integer(int32) :: capa_ ! 配列の実際の長さ.
   contains
     procedure, pass, private :: resize => resize_myvector ! 初期化用
     procedure, pass :: push_back => push_back_myvector ! 値を配列の後ろに詰め込む.
     procedure, pass :: at => at_myvector ! 配列の `n` 番目を見る.
  end type myvector
contains
  pure subroutine push_back_myvector(this, val)
    class(myvector), intent(inout) :: this
    integer(int32), intent(in) :: val
    if (.not. allocated(this%arr_)) &
         call this%resize(1)
    if (this%size_ == this%capa_) &
         call this%resize(this%capa_ * 2)
    this%size_ = this%size_ + 1
    this%arr_(this%size_) = val
  end subroutine push_back_myvector
  impure integer(int32) function at_myvector(this, idx) result(res)
    class(myvector), intent(in) :: this
    integer(int32), intent(in) :: idx
    if (idx < 1 .or. idx > this%size_) &
         error stop "Index is out of bounds in `at_myvector`."
    res = this%arr_(idx)
  end function at_myvector
  pure subroutine resize_myvector(this, n)
    class(myvector), intent(inout) :: this
    integer(int32), intent(in) :: n
    integer(int32), allocatable :: tmp(:)
    if (allocated(this%arr_)) then
       allocate(tmp(n))
       tmp(1:min(n, this%size_)) = this%arr_(1:min(n, this%size_))
       call move_alloc(from = tmp, to = this%arr_)
       this%capa_ = n
       this%size_ = min(n, this%size_)
    else
       allocate(this%arr_(n))
       this%size_ = 0
       this%capa_ = n
    end if
  end subroutine resize_myvector
end module myvector_m

program test_myvector
  use, intrinsic :: iso_fortran_env
  use myvector_m
  implicit none
  integer(int32), parameter :: n = 10
  type(myvector) :: v
  integer(int32) :: i
  do i = 1, n
     call v%push_back(i * i)
  end do
  do i = 1, n
     write(output_unit, '(i0, 1x, i0)') i, v%at(i)
  end do
end program test_myvector

結論

型に紐付いた関数(type-bound-procedure)を使うことによって, 型に対する操作を制限することができる.
つまり, `v%push_back` をする人は変数 `v` が十分なサイズを持っているかを気にする必要がない.
また, この `v%at` 関数はサイズの外にある領域へのアクセスを許さない.
- つまり, プログラムが正常終了したなら配列のアクセスに異常はないことが保証される.

更なる発展

size を返す関数 `size` を実装する.
- これと `at` と `push_back` があれば `type(myvector), alloctable :: g(:)` でグラフの問題に対処できる.
`push_back` 操作の対の `pop_back` を実装する.
一番後ろの要素を返す関数 `back` を実装する.
- これで stack の機能を表現できる.
`arr_(:)` を public にして, 配列の整合性を犠牲に利便性を確保する.

参考

型結合手続き

move_alloc

マイライブラリvector

User-defined-type ↩
type-bound-procedure 型束縛手続き? ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up