Fortranでも集合の概念を扱いたい
重複を排除したデータを作りたいこと、ありませんか？
例えば、[1,2,2,4,4,6]配列から [1,2,4,6]を作りたい、とか、["alpha", "alpha", "beta"]を["alpha", "beta"]にしたい、、という具合です。
近年活発に開発されているstdlibの hashmapを応用して、ある程度簡単に実現することができます。
整数の集合または文字列の集合を使う事例
整数[1,3,5]の集合（プログラム中ではmapという変数名）に対して
- 整数1~5が集合に含まれているかテスト
- 集合から要素を取り出す
- [5,6,7]を既存の集合に追加することを試みる
- 要素[1]を集合から削除
- 最後まで残った要素を表示
という処理をした結果のコンソール出力を下記に記します。
!=== hashmapを集合のように使う事例(intバージョン)
add values :[1,3,5,]
!-- 値が集合に含まれているかどうかのテスト
[1] is included.
[2] is not included.
[3] is included.
[4] is not included.
[5] is included.
!-- 追加した要素を取り出してループ処理
key=[1]
key=[3]
key=[5]
!-- 重複した値が無ければ集合に登録（重複があれば登録しない）
[5] は既に登録されています.
[6] を登録しました.
[7] を登録しました.
!---
[1]を削除するので、3,5,6,7が残るはずです
削除後の要素: 3, 5, 6, 7,
この出力は、下記ソースのtest_as_set_intというsubroutineを呼び出した結果です。
(test_as_set_stringというsubroutineは文字列の集合を扱うテストです。)
module sample_container
use iso_fortran_env
use stdlib_hashmaps
use stdlib_hashmap_wrappers
implicit none
private
public :: test_as_set_int,test_as_set_string
contains
subroutine test_as_set_int
type(chaining_hashmap_type) :: map
type(key_type), allocatable :: keys(:)
integer, allocatable :: int_key(:)
integer :: i
logical :: tf
call map%init(fnv_1_hasher)
print *, "!=== hashmapを集合のように使う事例(intバージョン)"
write(output_unit,fmt='(a)',advance="no") "add values :["
do i = 1, 5, 2
call map%map_entry([i])
write(output_unit,fmt="(i0,',')", advance="no") i
end do
write(output_unit,fmt='(a)',advance="yes") "]"
!--
write(output_unit,fmt='(a)',advance="yes") "!-- 値が集合に含まれているかどうかのテスト"
do i = 1, 5
call map%key_test([i], tf)
if (tf) then
write(output_unit,'("[",i0,"] is included.")') i
else
write(output_unit,'("[",i0,"] is not included.")') i
end if
end do
!-- getting all the key in the map
write(output_unit,*) "!-- 追加した要素を取り出してループ処理"
call map%get_all_keys(keys)
do i = 1, size(keys)
call get(keys(i), int_key)
write(output_unit,'("key=[",i0,"]")') int_key
end do
write(output_unit,*) "!-- 重複した値が無ければ集合に登録（重複があれば登録しない）"
do i = 5, 7
call map%map_entry([i], conflict=tf)
if (tf) then
write(output_unit,'("[",i0,"] は既に登録されています.")') i
else
write(output_unit,'("[",i0,"] を登録しました.")') i
end if
end do
write(output_unit,fmt='("!---")',advance='yes')
write(output_unit,fmt='("[1]を削除するので、3,5,6,7が残るはずです")',advance='yes')
call map%remove([1])
call map%get_all_keys(keys)
block
integer:: n
integer,allocatable :: int_keys(:)
n=size(keys)
write(output_unit,fmt='("削除後の要素: ")',advance='no')
do i=1,n
call get(keys(i), int_keys)
write(output_unit,'(i3,",")',advance='no') int_keys
end do
write(output_unit,fmt="(a)",advance='yes')
end block
end subroutine
subroutine test_as_set_string
type(chaining_hashmap_type) :: map
type(key_type), allocatable :: keys(:)
character(len=:),allocatable :: string
integer :: i
call map%init(fnv_1_hasher)
print *, "!=== hashmapを集合のように使う事例(文字列バージョン)"
call map%map_entry("alpha")
call map%map_entry("beta")
call map%map_entry("gamma")
call map%get_all_keys(keys)
do i = 1, size(keys)
call get(keys(i), string)
write(output_unit,'("key=[",A,"]")') string
end do
call check_char(map, "alpha")
call check_char(map, "beta")
call check_char(map, "gamma")
call check_char(map, "kappa")
call check_char(map, "epsilon")
end subroutine
subroutine check_char(map, txt)
type(chaining_hashmap_type) :: map
character(*) :: txt
logical :: tf
call map%key_test(txt, tf)
if (tf) then
write(output_unit,'(a,"はmapに含まれています")') txt
else
write(output_unit,'(a,"はmapに含まれていません")') txt
end if
end subroutine
end module sample_container
Fortranコード例のうち、文字列を扱うtest_as_set_stringの実行結果は次の通りです。
!=== hashmapを集合のように使う事例(文字列バージョン)
key=[alpha]
key=[beta]
key=[gamma]
alphaはmapに含まれています
betaはmapに含まれています
gammaはmapに含まれています
kappaはmapに含まれていません
epsilonはmapに含まれていません
重要な箇所だけ抜き出すと
コンソール出力のための文でやや見にくくなっていますが、
use stdlib_hashmaps
use stdlib_hashmap_wrappers
として、以下の関数などを使うのが基本となります。
call map%init(fnv_1_hasher) !初期化のおまじない。引数を変えると、内部処理の方法が変わる（らしい）
call map%map_entry(key_object) !key_objectはtype(key_type),character, int8配列,int32配列のどれか
call map%get_all_keys(keys) !keysはtype(key_type),allocatable,dimension(:)
call map%key_test(key_object, tf) ! tfが.true.なら、key_objectがすでに存在
call map%remove(key_object) ! key_objectがmapから削除される
ユーザ定義構造体の場合
構造体のビット表現をint8の配列にmytype_to_int8arrayで変換して利用する事例を紹介します。
厳密には、構造体の要素のバイト表現上の大きさ次第ではパディングが生じてうまくいかない場合が多いと思ってください。ここでは32bit実数と16bit整数が要素となっているからか、私の実行環境ではパディングが生じなかったようでうまくいきました。
本気で構造体を集合の成分として識別したければ、変数の要素をサーチしてハッシュ値を算出する関数などを作成すべきだと思います。（C++の標準ライブラリでも、自作クラスでsetを定義するときはハッシュ計算のメソッドと求められたような。。）
module user_defined_type
use iso_fortran_env
use stdlib_hashmaps
use stdlib_hashmap_wrappers
implicit none
public
type :: mytype_t
real(real32) :: x
real(real32) :: y
integer(int16) :: i
end type
contains
subroutine test_set_mytype
type(chaining_hashmap_type) :: map
type(key_type) :: key
type(key_type), allocatable :: keys(:)
integer(int8), allocatable :: int_key(:)
type(mytype_t) :: mytype
logical :: conflict
call map%init(fnv_1_hasher)
print *, "!=== hashmapを集合のように使う事例(ユーザ定義構造体バージョン)"
call map%map_entry(mytype_to_int8array(mytype_t(1d0,2d0,0)), conflict=conflict)
call map%map_entry(mytype_to_int8array(mytype_t(3d0,4d0,1)), conflict=conflict)
call map%map_entry(mytype_to_int8array(mytype_t(5d0,6d0,2)), conflict=conflict)
call show_keytest_result(map, mytype_t(1d0,2d0,1))
call show_keytest_result(map, mytype_t(3d0,4d0,1))
call map%get_all_keys(keys)
call show_keys(keys)
end subroutine
function mytype_to_int8array(mytype) result(int_key)
! keyとして受け付けられるのはint配列またはcharacterなので、構造体のバイト表現をint配列に変換する
type(mytype_t), intent(in) :: mytype
integer(int8), allocatable :: int_key(:)
integer(int8) :: int_8
integer :: size_mytype
size_mytype=storage_size(mytype)/8
int_key = transfer(source=mytype,mold=int_8,size=size_mytype)
end function
subroutine show_keytest_result(map,mytype)
type(chaining_hashmap_type) :: map
type(mytype_t) :: mytype
integer(int8), allocatable :: int_key(:)
logical :: tf
call map%key_test(mytype_to_int8array(mytype), tf)
if (tf) then
write(output_unit,*) mytype,"はmapに含まれています"
else
write(output_unit,*) mytype,"はmapに含まれていません"
end if
end subroutine
subroutine show_keys(keys)
type(key_type), intent(in) :: keys(:)
integer(int8), allocatable :: int_key(:)
type(mytype_t) :: mytype
integer :: n,i
n = size(keys)
do i = 1,n
call get(keys(i),int_key)
mytype = transfer(int_key, mytype)
print *, mytype,mytype_to_int8array(mytype)
end do
end subroutine
end module
このコードのtest_set_mytypeを実行した結果は下記の通りです。
!=== hashmapを集合のように使う事例(ユーザ定義構造体バージョン)
1.00000000 2.00000000 1 はmapに含まれていません
3.00000000 4.00000000 1 はmapに含まれています
1.00000000 2.00000000 0 0 0 -128 63 0 0 0 64 0 0 0 0
3.00000000 4.00000000 1 0 0 64 64 0 0 -128 64 1 0 0 0
5.00000000 6.00000000 2 0 0 -96 64 0 0 -64 64 2 0 0 0
同じ構造体が要素に含まれているかどうかを正しく判別できました。
簡易的にtransferを使いましたが、パディングの問題や、要素がポインタ or allocatableな時の動作は怪しくなると思います。
おわりに
stdlibのhashmapを活用して、integerやcharacter型の集合、さらに構造体の集合を作ることができました。本来、hashmapはkeyとペアになる任意のデータ型を保持できるので、「辞書」を生成できます。余力があれば辞書についても書こうかと思います。