Thinking Functionally with Haskell勉強メモ: 第７章１　メモリ、計算量、`seq`

メモリと計算量のトレードオフ

Haskellの評価戦略は完全にナイーブではない：

sqr (sqr (3+4))

= (sqr (3+4)) * (sqr (3+4))

= ((3+4) * (3+4)) * ((3+4) * (3+4))

= (7 * 7) * (7 * 7)

= 49 * 49

= 2401

のようなダブった評価はしない。

sqr (sqr (3+4))

= let x = (sqr (3+4)) in x * x

= let y = (3 + 4) in let x = y * y in x * x

= let y = 7 in let x = y * y in x * x

= let x = 7 * 7 in x * x

= let x = 49 in x * x

= 49 * 49

= 2401

と3+4もsqr(7)も一回ずつしか評価せず、同じ値を代入している。

しかし以下のような式の場合、ダブった部分を自動的にletやwhereにくくり出すことはしない：

subseqs (x:xs) = subseqs xs ++ map (x:) subseqs xs

くくりだしてしまうとsubseqs xsは一回評価した後ですべての結果をメモリ上に残しておく必要が生じる。そのトレードオフはプログラマが決定し明示的にコードに表す必要がある。

`primesum`関数の定義

最小n個の素数の和：

primesum :: Int -> Int
primesum n = sum (take n primes)
             where primes = [x | x <- [2..], divisors x == [x]]
                   divisors n = [d | d <- [2..n], n `mod` d == 0]

これだとprimesumを呼び出すごとにprimesが新しく作成され評価される。

primesをwhereに入れなければprimesumを複数回呼ぶと同じprimesから要素をとっていくので、評価された部分はメモリに残る。

primesum n = sum (take n primes)
primes = [x | x <- [2..], divisors x == [x]]
divisors n = [d | d <- [2..n], n `mod` d == 0]

問題点としては、primesが関数の内部実装だとするとそれが外部に漏れているところと、メモリを圧迫しかねないところ。

前者はClosureを使うことで解決する：

primesum :: Int -> Int
primesum = \n -> sum (take n primes)
           where primes = [x | x <- [2..], divisors x == [x]]
                 divisors n = [d | d <- [2..n], n `mod` d == 0]

primesumを無名関数の名前にし、primesをその無名関数にバインドした。

これでprimesumという関数が存在し続ける限りその内部では同一のprimesリストが使われるが、関数の外部から直接primesにアクセスすることはできないし名前衝突も起こらない。

メモリに関してはキャッシュ・メモ化して計算量を減らすのか、都度都度計算してメモリ消費を抑えるのか、やはりトレードオフである。

`cp`関数の定義

リストのリストの直積を求めるcp関数は過去の章で何回かでてきた。

素直な定義：

cp :: [[a]] -> [[a]]
cp [] = [[]]
cp (xs:xss) = [x:ys | x <- xs, ys <- cp xss]

これをpythonっぽく書くと：

for x in xs:
  for ys in cp xss:
    x:ys

なので外側のループが回る度にcp xssが繰り返し評価されていることがわかる。

解決策としてはwhereを使ってcp xssをループの外に出す：

cp [] = [[]]
cp (xs:xss) = [x:ys | x <- xs, ys <- yss]
              where yss = cp xss

あるいはそれをfoldr化する：

cp = foldr f [[]]
     where f xs yss = [x:ys | x <- xs, ys <- yss]

上記二つの解決策はfoldrの性質から同義。

個人的には、このケースだと：

cp [] = [[]]
cp (xs:xss) = [x:ys | ys <- cp xss, x <- xs]

が一番簡単な気がするが・・・

`seq`による先行評価

リストの数を足し合わせる関数sumを評価してみる：

sum [1..5]

= foldl (+) 0 [1..5]

= foldl (+) (0+1) [2..5]

= foldl (+) ((0+1)+2) [3..5]

...
= foldl (+) (((((0+1)+2)+3)+4)+5) []

= (((((0+1)+2)+3)+4)+5)

= ((((1+2)+3)+4)+5)

...
= 10+5

= 15

一旦[1..5]の要素がすべて(0+...)式に書き出されてから評価されていくのがわかる。その時点ですべての要素はメモリに載っていなければいけない。これが「遅延評価のスペースリーク」。

このケースだと、和を求めるところだけ部分的に先行評価していきたい。そういった場合、関数seqを使う。

seqはHaskellの言語仕様レベルで提供されている関数で、「特定の評価順を指定する」ためだけに存在する。

seq :: a -> b -> b
seq n m = m

で、式の値は第二引数の値となる。ただし、第二引数が評価される前に必ず第一引数がhead normal formまで評価される（head normal formについては補足メモ１を参照）。

`foldl'`を`seq`を使って定義

さて、foldlを使うと評価過程で「最終引数であるリスト」の内部をすべて書き出した式が展開されてしまいスペースリークが起きる。

seqを使ってその問題を避けるfoldl'を定義する：

foldl' :: (b -> a -> b) -> b -> [a] -> b
foldl' f e [] = e
foldl' f e (x:xs) = y `seq` (foldl' f y xs)
                    where y = f e x

これで(foldl' f y xs)部分が展開される前にf e xがhead normal formまで評価されるようになる。

sum = foldl' (+) 0とするとO(1)スペースで総和が評価できる。

foldl'は基本的にfoldlの上位互換となるが、foldl f eのfがstrictでないと同値にならない場合があり、そういったケースでは普通のfoldlを使わざるをえないこともある。

`mean'`を`seq`を使って定義

平均を求めるmean関数：

mean :: [Float] -> Float
mean [] = 0
mean xs = sum xs / fromIntegral (length xs)

上記の定義だとsumのあとにxsの値はすべてメモリに載っていることになる（lengthでもxsを使うので）。

それを避けるために以下のように定義を変えるとする：

mean :: [Float] -> Float
mean [] = 0
mean xs = s / fromIntegral n
          where (s, n) = sumlen xs

sumlen :: [Float] -> (Float, Int)
sumlen = foldl' g (0, 0)
         where g (s, n) x = (s+x, n+1)

残念ながらこれもスペースリークを引き起こす。

評価してみると：

sumlen [1..5]

= foldl' g (0, 0) [1..5]

= x `seq` (foldl' g x [2..5])
  where x = (g (0, 0) 1)

= foldl' g (0+1, 0+1) [2..5]

= x `seq` (foldl' g x [3..5])
  where x = (g (0+1, 0+1) 2)

= foldl' g ((0+1)+2, (0+1)+1) [3..5]

...
= foldl' g ((((((0+1)+2)+3)+4)+5), (((((0+1)+1)+1)+1)+1) []

= ((((((0+1)+2)+3)+4)+5), (((((0+1)+1)+1)+1)+1)

...
= (15, 5)

展開された式がO(n)のスペースをとっていることが確認できる。

ポイントはここ：

x `seq` (foldl' g x [2..5])
  where x = (g (0, 0) 1)

= foldl' g (0+1, 0+1) [2..5]

0+1はhead normal formではないが、(0+1, 0+1)はhead normal formなのである。

sumlenの中でもseqを使って先行評価させる必要がある。Birdの最終的な解：

mean :: [Float] -> Float
mean [] = 0
mean xs = s / fromIntegral n
          where (s, n) = sumlen xs

sumlen :: [Float] -> (Float, Int)
sumlen = foldl' g (0, 0)
         where g (s, n) x = s `seq` n `seq` (s+x, n+1)

個人的には上記だとtuple内にかならず一回分のreductionを残しているので

sumlen :: [Float] -> (Float, Int)
sumlen = foldl' g (0, 0)
         where g (s, n) x = y `seq` z `seq` (y, z)
                            where {y = s+x; z = n+1}

のほうがサプライズがなくていい気がするのだがどうだろう。

計算量の算出

GHCの最適化に関してのドキュメントをまとめると：

ちゃんとプロファイルしよう
アルゴリズムが一番大事
ライブラリを使おう

とのこと。あとはType Classではなく具体的なTypeに落とし込めるところは落とし込むのと、できるところはstrictでやっていく、の二点。

ある関数fの入力量nに対する漸近的な計算量を ${T(f)(n)}$ と表すとする。ただし、 ${T}$ はfの特定の定義・実装における先行評価下の計算量とする。

遅延評価だと算出が困難なことが理由。先行評価における漸近的上限は必ず遅延評価における漸近的上限であり、また下限も多くの場合一致する。

一例としてconcatをfoldrとfoldlで定義した場合の計算量の変化を見てみる：

concat xss = foldr (++) [] xss

T(concat)(m, n) = T(foldr (++) []) (m, n) -- n長のリストm個をconcatする場合の漸近的コスト

T(foldr (++) []) (0, n) = O(1)

T(foldr (++) []) (m+1, n) = T((++))(n, mn) + T(foldr (++) []) (m, n)

T((++))(n, mn) = O(n) -- n長のリストとmn長のリストを++する場合はコストはnに比例する

T(foldr (++) [])(m, n) = ${\sum\limits_{k=0}^mO(n) = O(mn)}$

そして

concat' xss = foldr (++) [] xss

T(concat')(m, n) = T(foldl (++)) (0, m, n) -- (k, m, n)のk値はfoldlのeの長さ

T(foldr (++)) (k, 0, n) = O(1)

T(foldr (++)) (k, m+1, n) = T((++))(k, n) + T(foldl (++)) (k+n, m, n)

T((++))(k, n) = O(k)

T(foldl (++))(k, m, n) = ${\sum\limits_{j=0}^{m-1}O(k+jn) = O(km+m^{2}n)}$

T(foldl (++))(0, m, n) = ${O(m^{2}n)}$

というわけでconcatをfoldlで定義するとfoldrで書いたものよりも漸近的に遅い。concatするリストの数mに対して、foldrは ${O(m)}$ 、foldlは ${O(m^{2})}$ 。

補足メモ１：head normal form

an expression is said to be in head normal form if it is a function ... or if it takes the form of a data constructor ... applied to its arguments

Every expression in normal form (i.e. in fully reduced form) is in head normal form but not vice versa

この部分はよくわからない。いきなり矛盾しているように思える。例えば1という式はnormal formだが、functionでもdata constructor applied to its argumentsでもない。

正しくは

an expression is said to be in head normal form if it is either 1) in fully reduced form, 2) a function ... or 3) if it takes the form of a data constructor ... applied to its arguments

なのでは？

補足メモ：faster by a logarithmic factor

${O(2^{n})}$ のアルゴリズムが ${O(n2^{n})}$ より

asymptotically faster by a logarithmic factor

と書いてあって少し戸惑った。 ${O(n2^{n})}$ の ${n}$ が ${m}$ 倍になったときの計算量の増加は、 ${O(2^{n})}$ の ${n}$ が ${m log m}$ 倍になったときの増加と等しい、ってことか。

Arantium Maestum

プログラミング、囲碁、読書の話題

Thinking Functionally with Haskell勉強メモ: 第７章１　メモリ、計算量、`seq`

メモリと計算量のトレードオフ

`primesum`関数の定義

`cp`関数の定義

`seq`による先行評価

`foldl'`を`seq`を使って定義

`mean'`を`seq`を使って定義

計算量の算出

補足メモ１：head normal form

補足メモ：faster by a logarithmic factor

メモリと計算量のトレードオフ

primesum関数の定義

cp関数の定義

seqによる先行評価

foldl'をseqを使って定義

mean'をseqを使って定義

計算量の算出

補足メモ１：head normal form

補足メモ：faster by a logarithmic factor

`primesum`関数の定義

`cp`関数の定義

`seq`による先行評価

`foldl'`を`seq`を使って定義

`mean'`を`seq`を使って定義