fortran66のブログ

fortran について書きます。

pointer function で連想配列 改

以前、Fortran2008 の pointer function を用いて、簡単な連想配列を作ってみましたが、ハッシュ法を N.Wirth の『アルゴリズム+データ構造=プログラム』 中の方法を用いてみました。キーは散らばっているでしょうか?

関数名を配列名のように使うので、このままでは連想配列ごとに関数を定義と駄目なので、何かいい手はないものか考えたいと思います。何か物憂く面倒くさいので、考えていませんし思いついていません。ポインターが返り値という関数なので、使い方をよく理解していない気がします。

fortran66.hatenablog.com

N.Wirth, Algorithms + Data Structures = Programs

Oberon 版 無料本 第五章 Key Transformations (Hashing)

http://www.ethoberon.ethz.ch/WirthPubl/AD.pdf

Modula-2 版 訳本

アルゴリズムとデータ構造

アルゴリズムとデータ構造

Pascal 版 原本

Algorithms + Data Structures = Programs (Prentice-Hall Series in Automatic Computation)

Algorithms + Data Structures = Programs (Prentice-Hall Series in Automatic Computation)

ソース・プログラム

    module hash_m
        implicit none
     !   private
     !   public :: ia
        
        integer, parameter :: nhash = 73
        type :: t_key
            character(len = :), allocatable :: key  
        end type t_key
        type (t_key)    :: keyc(nhash)  
        integer, target :: vals(nhash) = 0  
    contains
        pure integer function ihash(text) 
            character(len = *), intent(in) :: text
            integer :: i
            ihash = 0
            do i = 1, len_trim(text)
                ihash = mod(256 * ihash + iachar(text(i:i)), nhash)
            end do
            ihash = ihash + 1
        end function ihash  
       
        
        function ia(text) result(ires)
            character(len = *), intent(in) :: text
            integer, pointer :: ires 
            integer :: key, loc, ihop
            ihop = 1
            key = ihash(text) 
            do
                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 + ihop, nhash) + 1   
                    ihop = ihop + 2
                    if (ihop == nhash) stop 'associative array exhausted!' 
                end if
            end do  
        end function ia      
    end module hash_m
    
    
    program Hash
        use hash_m
        implicit none
      
        ia('a') = 41
        print *, ia('a')
        ia('a') = 100
        print *, ia('a')
        ia('b') = 200
        print *, ia('a') + ia('b')
      
        ia('FORTRAN I') = 1957
        ia('FORTRAN II') = 1958
        ia('FORTRAN IV') = 1961
        ia('FORTRAN 66') = 1966
        ia('FORTRAN 77') = 1978
        ia('Fortran 90') = 1991
        ia('Fortran 95') = 1997
        ia('Fortran 2003') = 2004
        ia('Fortran 2008') = 2010
        ia('Fortran 2018') = 2018
        
        ia('Gold') = 1488
        ia('Silver') = 17
        ia('Platinum') = 946
        ia('Palladium') = 1590
        ia('Rhodium') = 4700
      
        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

Modern Fortran Explained: Incorporating Fortran 2018 (Numerical Mathematics and Scientific Computation)

Modern Fortran Explained: Incorporating Fortran 2018 (Numerical Mathematics and Scientific Computation)

実行結果

gfortran 7 以上で、 ifort V.17 以上くらいで行けると思います。 

          41
         100
         300
  1:                    =>         0
  2:             Rhodium=>      4700
  3:                    =>         0
  4:                    =>         0
  5:            Platinum=>       946
  6:                    =>         0
  7:                    =>         0
  8:                    =>         0
  9:           Palladium=>      1590
 10:                    =>         0
 11:                    =>         0
 12:                    =>         0
 13:                    =>         0
 14:                    =>         0
 15:                    =>         0
 16:                    =>         0
 17:                    =>         0
 18:                    =>         0
 19:                    =>         0
 20:                    =>         0
 21:                    =>         0
 22:                    =>         0
 23:                    =>         0
 24:                    =>         0
 25:                   a=>       100
 26:                   b=>       200
 27:        Fortran 2018=>      2018
 28:                    =>         0
 29:                    =>         0
 30:                    =>         0
 31:          FORTRAN 77=>      1978
 32:                    =>         0
 33:                    =>         0
 34:                    =>         0
 35:                    =>         0
 36:                    =>         0
 37:                    =>         0
 38:                    =>         0
 39:                    =>         0
 40:                    =>         0
 41:                    =>         0
 42:           FORTRAN I=>      1957
 43:                    =>         0
 44:          Fortran 90=>      1991
 45:                    =>         0
 46:                    =>         0
 47:          Fortran 95=>      1997
 48:              Silver=>        17
 49:                    =>         0
 50:                    =>         0
 51:                    =>         0
 52:                    =>         0
 53:                    =>         0
 54:                    =>         0
 55:                    =>         0
 56:                    =>         0
 57:                    =>         0
 58:          FORTRAN II=>      1958
 59:                    =>         0
 60:        Fortran 2003=>      2004
 61:                    =>         0
 62:                    =>         0
 63:        Fortran 2008=>      2010
 64:                    =>         0
 65:                    =>         0
 66:          FORTRAN 66=>      1966
 67:                    =>         0
 68:                    =>         0
 69:                    =>         0
 70:                    =>         0
 71:          FORTRAN IV=>      1961
 72:                    =>         0
 73:                Gold=>      1488