初めに
Fortranに実装されているデータ構造は非常に少なく、大体自力で実装する羽目になる。dequeもその例に漏れない。一方、stackやqueueなどの他のデータ構造はue1221さんなどを始めとして主にfortran2008を用いた実装が行われている。しかし筆者はFortranのOOPに慣れていない。そこで今回はOOPなしでのdequeの実装を行った。
dequeとは
deque(デック)とは両端キューとも呼ばれるデータ構造である。dequeは右端にも左端にもデータを積むことができ、また取り出しも両端から行える。
挿入、取り出しを同片方向から行えば最後に入れた要素が最初に出てくる => LIFO(Last In First Out)
挿入、取り出しを異片方向から行えば最初に入れた要素が最初に出てくる => FIFO(First In First Out)
などのように、dequeはstackとしてもqueueとしても使うことができる。
環境
Ubuntu 18.04.4 LTS
ifort (IFORT) 19.0.4.243 20190416
GNU Fortran (Ubuntu 7.5.0-3ubuntu1~18.04) 7.5.0
実装
module deque_mod
implicit none
type deque
integer(4),pointer:: v(:)
integer(4):: l,r
integer(4):: lmax, rmax
end type
private
public:: deque
public:: init
public:: append, appendleft
public:: pop, popleft
public:: right, left
public:: remaining_elements
public:: remain
contains
subroutine init(dq)
! 初期化
type(deque):: dq
dq%r=0; dq%rmax=1
dq%l=1; dq%lmax=-1
allocate(dq%v(dq%lmax:dq%rmax))
end subroutine
subroutine append(dq,num)
! 右端に挿入
type(deque):: dq
integer(4):: num
if (dq%r+1 > dq%rmax) call add_(dq)
dq%r=dq%r+1
dq%v(dq%r) = num
end subroutine
subroutine appendleft(dq,num)
! 左端に挿入
type(deque):: dq
integer(4):: num
if (dq%l-1 < dq%lmax) call add_(dq)
dq%l=dq%l-1
dq%v(dq%l) = num
end subroutine
subroutine add_(dq)
! arrayの延長 隠蔽して行われる
type(deque):: dq
integer(4):: l
integer(4),pointer:: tmp(:)
l = size(dq%v)
allocate(tmp(l))
tmp(:) = dq%v(:)
deallocate(dq%v)
allocate(dq%v(2*dq%lmax:2*dq%rmax))
dq%v(dq%lmax:dq%rmax) = tmp(:)
dq%lmax = 2*dq%lmax
dq%rmax = 2*dq%rmax
end subroutine
function pop(dq) result(ret)
! 右端から取り出し
type(deque):: dq
integer(4):: ret
ret = dq%v(dq%r)
dq%r=dq%r-1
end function
function popleft(dq) result(ret)
! 左端から取り出し
type(deque):: dq
integer(4):: ret
ret = dq%v(dq%l)
dq%l=dq%l+1
end function
function right(dq) result(ret)
! 右端要素を確認
type(deque):: dq
integer(4):: ret
ret = dq%v(dq%r)
end function
function left(dq) result(ret)
! 左端要素を確認
type(deque):: dq
integer(4):: ret
ret = dq%v(dq%l)
end function
function remaining_elements(dq) result(ret)
! 残りの要素数
type(deque):: dq
integer(4):: ret
ret = dq%r - dq%l + 1
end function
function remain(dq) result(ret)
! 要素が残っているかどうか
type(deque):: dq
logical:: ret
ret = remaining_elements(dq) > 0
end function
end module
実装としては
- init(初期化)
- append(右に追加)
- add_(private)
- appendleft(左に追加)
- pop(右から取り出し)
- popleft(左から取り出し)
- right(右端を見るだけ)
- left(左端を見るだけ)
- remaining_elements(残りの要素数を返す)
- remain(dequeに要素が残っているか)
の8つである。
命名については基本的にpythonのdequeに従った。pythonにないものはCでの命名を感覚でまねた。
使用例
こんなプログラムを作成した。
①1から20までの値を、4で割り切れる→右から挿入、4で割り切れない→左から挿入
②dequeが空になるまで右から取り出し、出力
program test
use deque_mod
implicit none
type(deque):: dq
integer(4):: i
call init(dq)
do i=1,20
if (mod(i,4) == 0) then
call append(dq,i)
else
call appendleft(dq,i)
end if
end do
do while(remain(dq))
print'(i0)', pop(dq)
end do
end program test
20
16
12
8
4
1
2
3
5
6
7
9
10
11
13
14
15
17
18
19
おそらく大丈夫なはず。使用回数が少ないが、今のところ使っていて気になる点はない。
その他
可変長配列様の動き(サブルーチンadd_)はue1221さんの記事を改悪した。
確保している配列のどちらかの端が埋まった状態でその方向に値を挿入しようとするとadd_ subroutineに入り、配列長が二倍になる。ただし、右端と左端が同時に伸びるのでメモリの効率は元の倍悪い(下図)。あと要素が少なくなったとしても配列は縮んでくれたりはしない。競技プログラミングで使う目的では気にならないので妥協した形。
まとめ
modern fortranの機能にあまりついていけてない人間がdequeを書いてみたよ。
使う際の注意点
- メモリ効率は気になる人は気になるかもしれない
- 初期化をしてから使用しよう
- (remain subroutineなどを用いて)要素が残っていることを確認してから取り出してね
作ってすぐこの記事を書いたのでバグがあるかも知れない
気になる点をコメントしてくれたら追記していくつもり(つもり)