haskell-jp / beginners #26

@ has joined the channel

@川頭信之 has joined the channel

@ has joined the channel

@ has joined the channel

@T N has joined the channel

@ has joined the channel

@たぬきうどん has joined the channel

Array についての質問です。
10×10の行列が与えられ、(1,1)成分から右か下に向かって成分を足しながら進んでいくとき、(i,j)成分へ至る道のうち最も和が小さいものを求めるという問題があります。
この問題に対して以下のようなコードを書きました。

import Data.Array

main :: IO ()
main = do
    let m = listArray ((1,1),(10,10)) [i+j |i<-[1..10], j<-[1..10]]
    print $ minPath m ! (8,8)

minPath :: Array (Int,Int) Int -> Array (Int,Int) Int
minPath mat = listArray ((1,1),(10,10)) $ [ f i j | i<-[1..10], j<-[1..10]]
    where   f 1 1 = mat ! (1,1)
            f 1 j = mat ! (1,j) + minPath mat ! (1,j-1)
            f i 1 = mat ! (i,1) + minPath mat ! (i-1,1)
            f i j = if minPath mat ! (i-1,j) > minPath mat ! (i,j-1) 
                        then minPath mat ! (i,j-1) + mat ! (i,j) 
                        else minPath mat ! (i-1,j) + mat ! (i,j)

これをrunghcで実行すると私の環境 (CPU: Ryzen 5 3600, RAM: 16GB) では40秒程度かかります。
Arrayは要素へのアクセスがO(1)なので、リストのリストよりも要素へのアクセスが速いはずです。
この理解が正しければボトルネックとなっているのは要素へのアクセスではないと思うのですが、それではどこにこんなに時間がかかるのかわかりません。
1. なぜこんなに時間がかかるのでしょうか？
2. どのように改善すればよいのでしょうか？

@漆崎英一 has joined the channel