読者です 読者をやめる 読者になる 読者になる

fortran66のブログ

fortran について書きます。

Fortran 2008 の pointer function で作った連想配列

Fortran 2008 の新機能 pointer function を用いて、簡単な連想配列 (associative array) を作ってみます。

ここでは古典的な手法で、文字列をインデックスとした整数型連想配列を作ってみます。

まず文字列を適当な整数に変換し、あらかじめ用意した配列のサイズの剰余をとって、それを実際の引数とします。このとき、単射性が無いため数値が重なることがあります(いわゆる衝突)、これが起きた場合は、適当な数を足して空いている場所が見つかるまでずらします。

文字列を数値に変換するために、まず文字列を文字配列に直し、次にそれをASCIIコードに直し、総和を取って、適当な素数で剰余を取っています。また衝突時にずらす数も素数に取れば、全ての空きを探すことになります(全射)。


ソース・プログラム

    module m_hash
      implicit none
     ! private
      integer, parameter :: nhash = 17, nd = 13
      type :: t_key
        character(len = :), allocatable :: key  
      end type t_key
      type (t_key) :: keyc(nhash)  
      integer, target :: vals(nhash) = 0  
    contains
      integer function ihash(text)
        character(len = *), intent(in) :: text
        ihash = mod(sum(iachar(transfer(text, ' ', size = len_trim(text)))), nhash) + 1
      end function ihash  
       
      function ia(text) result(ires)
        character(len = *), intent(in) :: text
        integer, pointer :: ires 
        integer :: key, loc, i
        key = ihash(text)
        do i = 1, nhash
          if (.not. allocated(keyc(key)%key)) then
            keyc(key)%key = trim(text)
            ires => vals(key)
            exit
          else if (keyc(key)%key == trim(text)) then 
            ires => vals(key)
            exit
          else ! collision
            key = mod(key + nd, nhash) + 1  
          end if
        end do  
        if (i > nhash) stop 'associative array exhausted!' 
      end function ia      
    end module m_hash
    
    program Hash
      use m_hash
      implicit none
      
      ia('a') = 41
      print *, ia('a')
      ia('a') = 100
      print *, ia('a')
      ia('b') = 200
      print *, ia('a') + ia('b')
      
      
      ia('FORTRAN77') = 1978
      ia('Fortran90') = 1991
      ia('Donald Trump') = 1
      ia('Steve Bannon') = 4
      ia('Milo Yiannopoulos') = 10
      
      block
        integer :: i
        do i = 1, nhash
          print '(i3,a,a20,a,i10)', i, ':', keyc(i)%key, '=>', ia(keyc(i)%key)
        end do    
      end block
    end program Hash

実行結果

          41
         100
         300
  1:                    =>         0
  2:           Fortran90=>      1991
  3:                    =>         0
  4:                    =>         0
  5:           FORTRAN77=>      1978
  6:                    =>         0
  7:        Donald Trump=>         1
  8:                    =>         0
  9:                    =>         0
 10:   Milo Yiannopoulos=>        10
 11:                    =>         0
 12:                    =>         0
 13:                   a=>       100
 14:                   b=>       200
 15:                    =>         0
 16:                    =>         0
 17:        Steve Bannon=>         4
続行するには何かキーを押してください . . .