LoginSignup
8
5

More than 1 year has passed since last update.

FortranAdvent Calendar 2021Day 24
@implicit_none

Fortranの標準ライブラリstdlibの紹介（ソート）

Last updated at Posted at 2021-12-23

概要

Fortran-langコミュニティが主導して開発しているFortraの標準ライブラリstdlibについて紹介します．紹介する内容は，stdlibの現行バージョン0.1.0に基づいています．

本記事では，stdlibに実装されているソートについて説明します．

  • stdlib_sorting

stdlib_sorting

stdlib_sortingモジュールでは，1次元配列をソートする手続を実装しています．

  • sort
  • ord_sort
  • sort_index

また，sort_indexで用いるindexの整数種別を定義したパラメータint_sizeが定義されています．

sort

sortには，quick sort, merge sort, insertion sortを組み合わせたintrosortアルゴリズムが用いられています．

sortはサブルーチンなのでcall sort(array [, reverse])として呼出します．sortは渡された配列の内容を並び替えた内容で上書きします．

引数名 型 用途
array integer(int8),dimension(:),intent(inout) 並び替えられる配列
integer(int16),dimension(:),intent(inout)
integer(int32),dimension(:),intent(inout)
integer(int64),dimension(:),intent(inout)
real(real32),dimension(:),intent(inout)
real(real64),dimension(:),intent(inout)
real(real128),dimension(:),intent(inout)
character(*),dimension(:),intent(inout)
type(string_type),dimension(:),intent(inout)
reverse logical,intent(in),optional .true.のとき降順に並び替える

stdlib-fpmブランチを利用する場合，real(real128)型の実装は生成されていません．

arrayが実数のとき，値にNaNが含まれていると動作は未定義になります．

character(*)およびstring_type配列に対しては，演算子<, <=, >, >=を利用しており，llt, lle, lgt, lgeは利用されていません．

integer(int8), allocatable :: array(:)
array = [5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call sort(array)
print *, array
! 1 3 4 4 5 9 10

! 降順で並び替える．
call sort(array, reverse=.true.)
print *, array
! 10 9 5 4 4 3 1

integer(int16), allocatable :: array(:)
array = [5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call sort(array)
print *, array
! 1 3 4 4 5 9 10

! 降順で並び替える．
call sort(array, reverse=.true.)
print *, array
! 10 9 5 4 4 3 1

integer(int32), allocatable :: array(:)
array = [5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call sort(array)
print *, array
! 1 3 4 4 5 9 10

! 降順で並び替える．
call sort(array, reverse=.true.)
print *, array
! 10 9 5 4 4 3 1

integer(int64), allocatable :: array(:)
array = [5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call sort(array)
print *, array
! 1 3 4 4 5 9 10

! 降順で並び替える．
call sort(array, reverse=.true.)
print *, array
! 10 9 5 4 4 3 1

real(real32), allocatable :: array(:)
array = [real(real32) :: 5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call sort(array)
print *, array
! 1.00000000 3.00000000 4.00000000 4.00000000 5.00000000 9.00000000 10.0000000

! 降順で並び替える．
call sort(array, reverse=.true.)
print *, array
! 10.00000009.000000005.000000004.000000004.000000003.000000001.00000000

real(real64), allocatable :: array(:)
array = [real(real64) :: 5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call sort(array)
print *, array
! 1.0000000000000000 3.0000000000000000 4.0000000000000000 4.0000000000000000 5.0000000000000000 9.0000000000000000 10.000000000000000

! 降順で並び替える．
call sort(array, reverse=.true.)
print *, array
! 10.000000000000000 9.0000000000000000 5.0000000000000000 4.0000000000000000 4.0000000000000000 3.0000000000000000 1.0000000000000000

character(2), allocatable :: array(:)

! 各要素の文字列長さは同じ
array = ["fo", "rt", "ra", "n ", "FO", "RT", "RA", "N "]

! 昇順で並び替える．
call sort(array)
print *, array
! FON RARTfon rart

! 降順で並び替える．
call sort(array, reverse=.true.)
print *, array
! rtran foRTRAN FO

use :: stdlib_string_type
type(string_type), allocatable :: array(:)

! 各要素の文字列長さは異なっていてもよい
array = [string_type("fo"), string_type("rt"), string_type("ra"), string_type("n"), &
         string_type("FO"), string_type("RT"), string_type("RA"), string_type("N")]

! 昇順で並び替える．
call sort(array)
print '(*(DT"string_type"))', array
! FONRARTfonrart

! 降順で並び替える．
call sort(array, reverse=.true.)
print '(*(DT"string_type"))', array
! rtranfoRTRANFO

ord_sort

sort以外のソートアルゴリズムとして，ord_sortが実装されています．ord_sortは，slice.rsに含まれている"Rust" sortをFortranに移植した手続です．

ord_sortはsortと同様にサブルーチンなのでcall ord_sort(array [, work, reverse])として呼出します．ord_sortは渡された配列の内容を並び替えた内容で上書きします．

引数名 型 用途
array integer(int8),dimension(:),intent(inout) 並び替えられる配列
integer(int16),dimension(:),intent(inout)
integer(int32),dimension(:),intent(inout)
integer(int64),dimension(:),intent(inout)
real(real32),dimension(:),intent(inout)
real(real64),dimension(:),intent(inout)
real(real128),dimension(:),intent(inout)
character(*),dimension(:),intent(inout)
type(string_type),dimension(:),intent(inout)
work arrayと同じ型,dimension(:),intent(out),optional 実行時のスタックの使用量を削減するために使用する．
配列サイズはsize(array)/2以上．
ソート終了時の値は未定義．
reverse logical,intent(in),optional .true.のとき降順に並び替える

stdlib-fpmブランチを利用する場合，real(real128)型の実装は生成されていません．

integer(int8), allocatable :: array(:)
array = [5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call ord_sort(array)
print *, array
! 1 3 4 4 5 9 10

! 降順で並び替える．
call ord_sort(array, reverse=.true.)
print *, array
! 10 9 5 4 4 3 1

integer(int16), allocatable :: array(:)
array = [5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call ord_sort(array)
print *, array
! 1 3 4 4 5 9 10

! 降順で並び替える．
call ord_sort(array, reverse=.true.)
print *, array
! 10 9 5 4 4 3 1

integer(int32), allocatable :: array(:)
array = [5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call ord_sort(array)
print *, array
! 1 3 4 4 5 9 10

! 降順で並び替える．
call ord_sort(array, reverse=.true.)
print *, array
! 10 9 5 4 4 3 1

integer(int64), allocatable :: array(:)
array = [5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call ord_sort(array)
print *, array
! 1 3 4 4 5 9 10

! 降順で並び替える．
call ord_sort(array, reverse=.true.)
print *, array
! 10 9 5 4 4 3 1

real(real32), allocatable :: array(:)
array = [real(real32) :: 5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call ord_sort(array)
print *, array
! 1.00000000 3.00000000 4.00000000 4.00000000 5.00000000 9.00000000 10.0000000

! 降順で並び替える．
call ord_sort(array, reverse=.true.)
print *, array
! 10.00000009.000000005.000000004.000000004.000000003.000000001.00000000

real(real64), allocatable :: array(:)
array = [real(real64) :: 5, 4, 3, 1, 10, 4, 9]

! 昇順で並び替える．
call ord_sort(array)
print *, array
! 1.0000000000000000 3.0000000000000000 4.0000000000000000 4.0000000000000000 5.0000000000000000 9.0000000000000000 10.000000000000000

! 降順で並び替える．
call ord_sort(array, reverse=.true.)
print *, array
! 10.000000000000000 9.0000000000000000 5.0000000000000000 4.0000000000000000 4.0000000000000000 3.0000000000000000 1.0000000000000000

character(2), allocatable :: array(:)

! 各要素の文字列長さは同じ
array = ["fo", "rt", "ra", "n ", "FO", "RT", "RA", "N "]

! 昇順で並び替える．
call ord_sort(array)
print *, array
! FON RARTfon rart

! 降順で並び替える．
call ord_sort(array, reverse=.true.)
print *, array
! rtran foRTRAN FO

use :: stdlib_string_type
type(string_type), allocatable :: array(:)

! 各要素の文字列長さは異なっていてもよい
array = [string_type("fo"), string_type("rt"), string_type("ra"), string_type("n"), &
         string_type("FO"), string_type("RT"), string_type("RA"), string_type("N")]

! 昇順で並び替える．
call ord_sort(array)
print '(*(DT"string_type"))', array
! FONRARTfonrart

! 降順で並び替える．
call ord_sort(array, reverse=.true.)
print '(*(DT"string_type"))', array
! rtranfoRTRANFO

sort_index

sort_indexは，渡された配列の内容をord_sortを利用して並び替えます．同時に，ソート前の配列内容からソート後の配列内容を作るindexを記録した配列を返します．複数の配列を同じ順序で並び替える場合に利用します．

sort_indexはcall sort_index(array, index[, work, iwork, reverse])として呼出します．sort_indexは渡された配列arrayを並び替えた内容で上書きします．

引数名 型 用途
array integer(int8),dimension(:),intent(inout) 並び替えられる配列
integer(int16),dimension(:),intent(inout)
integer(int32),dimension(:),intent(inout)
integer(int64),dimension(:),intent(inout)
real(real32),dimension(:),intent(inout)
real(real64),dimension(:),intent(inout)
real(real128),dimension(:),intent(inout)
character(*),dimension(:),intent(inout)
type(string_type),dimension(:),intent(inout)
index integer(int_size),dimension(:),intent(out) ソート前の配列からソート後の配列を作るindex
work arrayと同じ型,dimension(:),intent(out),optional 実行時のスタックの使用量を削減するために使用する．
配列サイズはsize(array)/2以上．
ソート終了時の値は未定義．
iwork integer(int_size),dimension(:),intent(out),optional 実行時のスタックの使用量を削減するために使用する．
配列サイズはsize(array)/2以上．
ソート終了時の値は未定義．
reverse logical,intent(in),optional .true.のとき降順に並び替える

stdlib-fpmブランチを利用する場合，real(real128)型の実装は生成されていません．

integer(int32), allocatable :: array(:)
integer(int_size), allocatable :: index(:)

array = [5, 4, 3, 1, 10, 4, 9]
allocate (index(1:size(array)))

! ord_sortを利用して並び替える
! 並び替え前から後の配列を作るためのインデックスを返す．
call sort_index(array, index)
print *, array
print *, index
! 1 3 4 4 5 9 10
! 4 3 2 6 1 7 5

! indexを用いて並び替える．
array = [5, 4, 3, 1, 10, 4, 9] ! 並び替え前の配列
array = array(index)
! array(1) = array(index(1)) = array(4) = 1
! array(2) = array(index(2)) = array(3) = 3
! array(3) = array(index(3)) = array(2) = 4
! array(4) = array(index(4)) = array(6) = 4
! array(5) = array(index(5)) = array(1) = 5
! array(6) = array(index(6)) = array(7) = 9
! array(7) = array(index(7)) = array(5) = 10

print *, array
! 1 3 4 4 5 9 10

sortの使用例

sortの使用例として，2020年の各都道府県の交通事故件数をソートし，交通事故件数の多い都道府県を確認してみます．

統計データの取得

交通事故件数は，警察庁のWebサイトから統計表をダウンロードできます．2020年12月末の都道府県別交通事故発生状況を，道路の交通に関する統計から表6-2をcsv形式で（表6-2.csv）ダウンロードします．

ダウンロードした後，ファイル名をtable6-2.csvに変更しておきます．

csvファイルの内容は，単純に都道府県, 交通事故件数の順に記録されてはおらず，地域コード，管区・支局, 都道府県，交通事故件数の順に並んでいます．北海道の場合，札幌，函館，旭川，釧路，北見，計の6個のデータがあり，計が北海道での交通事故件数になっています．

都道府県のデータには地域コードが割り振られています．北海道のように支局がある場合，支局には地域コードは割り振られず，計に北海道の地域コードが割り振られます．また，管区での合計値も出されておりその合計値には地域コードは割り振られません．

地域コード 管区・支局 都道府県 交通事故件数
北海道 札幌
北海道 函館
北海道 旭川
北海道 釧路
北海道 北見
1 北海道 計
2 東北 青森
3 東北 岩手
4 東北 宮城
5 東北 秋田
6 東北 山形
7 東北 福島
東北 計

プロジェクトの作成

Fortranでcsvを読み込む場合，fortran-csv-moduleを利用すると簡単です．

アプリケーションのみのfpmプロジェクトを作成します．

fpm new csv --app

fpm.tomlを編集し，参照するプロジェクトを追加します．

name = "csv"
version = "0.1.0"
license = "license"
[build]
auto-executables = true
auto-tests = true
auto-examples = true
[install]
library = false

[dependencies]
fortran-csv-module = { git="https://github.com/jacobwilliams/fortran-csv-module.git" }
stdlib = { git="https://github.com/fortran-lang/stdlib", branch="stdlib-fpm" }

プロジェクトのルートディレクトリに，ダウンロードして名前を変更した統計データtable6-2.csvを置きます．

プログラムの作成

基本的にはcsvファイルを読み込んでソートをすることになりますが，ただcsvファイルを読んで並べ替えれば終わりという訳にはいきません．

都道府県以外の管区・支局のデータがあるため，都道府県のデータのみを抜き出す必要があります．また，都道府県名のみを利用すると，北海道の名前が"計"となってしまいます．

これらの問題に対応する方針を，下記の通り決定します．

  • 都道府県のデータは，地域コードが1以上の要素を抽出することで取得する
  • 都道府県名は，"管区・支局"-"都道府県"とする

csvファイルの読み込み

csvファイルは，fortran-csv-moduleを利用することで比較的簡単に読み込むことができます．

use :: csv_module
type(csv_file) :: f
logical :: stat

integer(int32), allocatable :: num_accidents(:) ! 交通事故発生件数

integer(int32), allocatable :: pref_code(:)   ! 地域コード
character(6)  , allocatable :: pref_name(:)   ! 都道府県名
character(6)  , allocatable :: region_name(:) ! 管区・支局名

! csvファイルの読み込み
! 4行目がヘッダ，1,2,3,65,66行はデータではないので取得しない
call f%read('table6-2.csv', header_row=4, skip_rows=[1, 2, 3, 65, 66], status_ok=stat)
call f%get(1, pref_code    , stat) ! 1列目 地域コードを配列にコピー
call f%get(2, region_name  , stat) ! 2列目 管区・支局名を配列にコピー
call f%get(3, pref_name    , stat) ! 3列目 都道府県名を配列にコピー
call f%get(4, num_accidents, stat) ! 4列目 交通事故件数を配列にコピー
call f%destroy()

地域コードが割り振られたデータの抽出

配列から地域コードが割り振られたデータのみを抽出するには，packを用います．packでは，maskで指定した条件に基づいて別の配列を作ります．

下記の処理では，pref_code >= 1となる配列要素番号と同じ配列要素番号のデータを，region_name, pref_name, num_accidentsから抽出して同じ配列に上書きします．これらの配列はallocatable属性であるため，配列要素数等を指定しない場合は右辺に応じて自動で再割付けされます．

region_name   = pack(region_name  , mask=(pref_code >= 1))
pref_name     = pack(pref_name    , mask=(pref_code >= 1))
num_accidents = pack(num_accidents, mask=(pref_code >= 1))

管区・支局名と都道府県名の連結

必要なデータのみを抽出したので，管区・支局名と都道府県名を連結します．

都道府県名の長さは不揃いなので，1要素ずつ空白を除去して連結します．この作業を配列構成子を用いて記述してみました．

character(13), allocatable :: region_pref(:)

integer(int32) :: i
region_pref = [character(13) :: (trim(region_name(i))//"-"//trim(pref_name(i)), i=1, size(region_name))]

並び替え

stdlibのsort_indexを用いて交通事故件数をソートし，その並び替えのindexを参照して都道府県名を並び替えます．

use :: stdlib_sorting
integer(int_size), allocatable :: idx(:) ! ソート前のデータがソート後にどの要素番号に移動したか

allocate (idx(size(num_accidents)))

! 交通事故件数を降順でソート
call sort_index(num_accidents, idx, reverse=.true.)

! 交通事故件数の並び替えの情報を利用して都道府県名を並び替え
region_pref = region_pref(idx(:))

実行結果

並び替えの結果を1要素ずつ表示すると下記の結果が得られました．やはり人が多い県で交通事故が多いようです．静岡の人口は上位の都道府県と比較すると少ないはずですが，主要な高速道路が通っている影響か，交通事故件数が多くなっています．

> fpm run --compiler ifort
 東京-東京           25642
 近畿-大阪           25543
 中部-愛知           24879
 九州-福岡           21495
 関東-静岡           20667
 関東-神奈川         20630
 近畿-兵庫           17352
 関東-埼玉           17115
 関東-千葉           12873
 関東-群馬            9266
 北海道-計            7898
 関東-茨城            6049
 九州-宮崎            5126
 関東-長野            4802
 中国-広島            4779
 東北-宮城            4487
 中国-岡山            4288
 近畿-京都            4118
 九州-鹿児島          4070
 関東-栃木            3939
 九州-佐賀            3758
 四国-香川            3722
 東北-山形            3328
 東北-福島            3266
 九州-熊本            3152
 関東-新潟            3076
 中部-岐阜            3052
 九州-長崎            2987
 中部-三重            2966
 近畿-滋賀            2893
 九州-沖縄            2808
 近畿-奈良            2790
 中国-山口            2641
 九州-大分            2437
 東北-青森            2436
 四国-愛媛            2404
 四国-徳島            2165
 関東-山梨            2146
 中部-石川            2025
 中部-富山            1992
 東北-岩手            1658
 近畿-和歌山          1585
 東北-秋田            1377
 四国-高知            1263
 中部-福井             868
 中国-島根             737
 中国-鳥取             628

コード全景

メインルーチンは下記のようになっています．

program main
    use, intrinsic :: iso_fortran_env
    implicit none

    character(13) , allocatable :: region_pref(:)   ! 管区・支局名＋都道府県名
    integer(int32), allocatable :: num_accidents(:) ! 交通事故発生件数

    block
        use :: csv_module
        type(csv_file) :: f
        logical :: stat

        integer(int32), allocatable :: pref_code(:)   ! 地域コード
        character(6)  , allocatable :: pref_name(:)   ! 都道府県名
        character(6)  , allocatable :: region_name(:) ! 管区・支局名

        ! csvファイルの読み込み
        ! 4行目がヘッダ，1,2,3,65,66行はデータではないので取得しない
        call f%read('table6-2.csv', header_row=4, skip_rows=[1, 2, 3, 65, 66], status_ok=stat)
        call f%get(1, pref_code    , stat) ! 1列目 地域コードを配列にコピー
        call f%get(2, region_name  , stat) ! 2列目 管区・支局名を配列にコピー
        call f%get(3, pref_name    , stat) ! 3列目 都道府県名を配列にコピー
        call f%get(4, num_accidents, stat) ! 4列目 交通事故件数を配列にコピー
        call f%destroy()

        ! 都道府県の情報（地域コードが割り振られた行）を抽出する
        region_name   = pack(region_name  , mask=(pref_code >= 1))
        pref_name     = pack(pref_name    , mask=(pref_code >= 1))
        num_accidents = pack(num_accidents, mask=(pref_code >= 1))

        block
            integer(int32) :: i
            ! 管区・支局名と都道府県名を連結し，"北海道-計"といったデータを作る
            region_pref = [character(13) :: (trim(region_name(i))//"-"//trim(pref_name(i)), i=1, size(region_name))]
        end block
    end block

    block
        use :: stdlib_sorting
        integer(int_size), allocatable :: idx(:) ! ソート前のデータがソート後にどの要素番号に移動したか

        allocate (idx(size(num_accidents)))

        ! 交通事故件数を降順でソート
        call sort_index(num_accidents, idx, reverse=.true.)

        ! 交通事故件数で並べ替え変えた順序通りに管区・支局-都道府県名を並び替える
        region_pref = region_pref(idx(:))

        ! 結果の表示
        block
            integer(int32) :: i
            do i = 1, size(region_pref)
                print *, region_pref(i), num_accidents(i)
            end do
        end block
    end block
end program main

管区・支局名をcharacter型ではなくstring_typeに変更すると，可変長の文字列を容易に扱えますが，可変長となるため表示が崩れます．

program main
    use, intrinsic :: iso_fortran_env
    use :: stdlib_string_type
    implicit none

    type(string_type), allocatable :: region_pref(:)   ! 管区・支局名＋都道府県名
    integer(int32)   , allocatable :: num_accidents(:) ! 交通事故発生件数

    block
        use :: csv_module
        type(csv_file) :: f
        logical :: stat

        integer(int32), allocatable :: pref_code(:)   ! 地域コード
        character(6)  , allocatable :: pref_name(:)   ! 都道府県名
        character(6)  , allocatable :: region_name(:) ! 管区・支局名

        ! csvファイルの読み込み
        ! 4行目がヘッダ，1,2,3,65,66行はデータではないので取得しない
        call f%read('table6-2.csv', header_row=4, skip_rows=[1, 2, 3, 65, 66], status_ok=stat)
        call f%get(1, pref_code    , stat) ! 1列目 地域コードを配列にコピー
        call f%get(2, region_name  , stat) ! 2列目 管区・支局名を配列にコピー
        call f%get(3, pref_name    , stat) ! 3列目 都道府県名を配列にコピー
        call f%get(4, num_accidents, stat) ! 4列目 交通事故件数を配列にコピー
        call f%destroy()

        ! 都道府県の情報（地域コードが割り振られた行）を抽出する
        region_name   = pack(region_name  , mask=(pref_code >= 1))
        pref_name     = pack(pref_name    , mask=(pref_code >= 1))
        num_accidents = pack(num_accidents, mask=(pref_code >= 1))

        block
            integer(int32) :: i
            ! 管区・支局名と都道府県名を連結し，"北海道-計"といったデータを作る
            region_pref = [(string_type(trim(region_name(i))//"-"//trim(pref_name(i))), i=1, size(region_name))]
        end block
    end block

    block
        use :: stdlib_sorting
        integer(int_size), allocatable :: idx(:)! ソート前のデータがソート後にどの要素番号に移動したか

        allocate (idx(size(num_accidents)))

        ! 交通事故件数で並べ替え
        call sort_index(num_accidents, idx, reverse=.true.)

        ! 交通事故件数で並べ替え変えた順序通りに管区・支局-都道府県名を並び替える
        ! region_pref = region_pref(idx(:)) ! Intel Fortranでは正しくソートされない．

        ! 結果の表示
        block
            integer(int32) :: i
            do i = 1, size(region_pref)
                print *, region_pref(idx(i)), num_accidents(i)
            end do
        end block
    end block
end program main

 東京-東京       25642
 近畿-大阪       25543
 中部-愛知       24879
 九州-福岡       21495
 関東-静岡       20667
 関東-神奈川       20630
 近畿-兵庫       17352
以下略

また，インデックスを利用して都道府県名を並べ替える処理region_pref = region_pref(idx(:))に起因して，Intel Fortranでは下記のように結果がおかしくなります．

fpm run --compiler ifort
 関東-埼玉       25642
 中部-岐阜       25543
 東北-山形       24879
 中部-富山       21495
 近畿-京都       20667
 関東-長野       20630
 九州-長崎       17352
 関東-茨城       17115
 九州-宮崎       12873
 北海道-計        9266
 東京-東京        7898
 関東-千葉        6049
以下略

そのため，明示的に並び替えないように変更しています．

8
5
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
8
5