Haskellの foldr と foldl と foldl'
前の記事で、Haskellでfoldlを使った場合の動作について書きました。
ここで、Haskellでfoldlを実際に使ってみて動作を確認してみようと思います。
{- fold1.hs -} import Data.List result = foldl (&&) True (map even [1..1000000]) main = print result
colinux> ghc --version The Glorious Glasgow Haskell Compilation System, version 7.0.4
colinux> ghc fold1.hs [1 of 1] Compiling Main ( fold1.hs, fold1.o ) Linking fold1 ... colinux> /usr/bin/time ./fold1 Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it. Command exited with non-zero status 2 0.58user 1.23system 0:01.91elapsed 94%CPU (0avgtext+0avgdata 361712maxresident)k 0inputs+0outputs (0major+22665minor)pagefaults 0swaps
あっという間にスタックオーバーフローしました。
代わりに foldl' を使ってみます。
{- fold1_.hs -} import Data.List result = foldl' (&&) True (map even [1..1000000]) main = print result
同じく実行してみます。
colinux> ghc fold1_.hs [1 of 1] Compiling Main ( fold1_.hs, fold1_.o ) Linking fold1_ ... colinux> /usr/bin/time ./fold1_ False 0.08user 0.00system 0:00.08elapsed 100%CPU (0avgtext+0avgdata 7328maxresident)k 0inputs+0outputs (0major+515minor)pagefaults 0swaps
ほぼ一瞬で実行が終了しました。
foldrでも試してみます。
{- fold2.hs -} import Data.List result = foldr (&&) True (map even [1..1000000]) main = print result
colinux> ghc fold2.hs [1 of 1] Compiling Main ( fold2.hs, fold2.o ) Linking fold2 ... colinux> /usr/bin/time ./fold2 False 0.00user 0.00system 0:00.00elapsed ?%CPU (0avgtext+0avgdata 5264maxresident)k 0inputs+0outputs (0major+386minor)pagefaults 0swaps colinux>
実行時間が短くて比較になりませんが、max resident sizeが若干小さくなっています(7328k -> 5264k)。
スタックオーバーフローしたfoldl版はともかく、foldl'とfoldrの実行時間が比較にならなかったので、リストのサイズを100倍にしてみました。
foldl'での実行結果
colinux> ghc fold1__big.hs [1 of 1] Compiling Main ( fold1__big.hs, fold1__big.o ) Linking fold1__big ... colinux> /usr/bin/time ./fold1__big False 3.75user 0.00system 0:03.75elapsed 100%CPU (0avgtext+0avgdata 7312maxresident)k 0inputs+0outputs (0major+514minor)pagefaults 0swaps
foldrでの実行結果
colinux> ghc fold2_big.hs [1 of 1] Compiling Main ( fold2_big.hs, fold2_big.o ) Linking fold2_big ... colinux> /usr/bin/time ./fold2_big False 0.00user 0.00system 0:00.00elapsed ?%CPU (0avgtext+0avgdata 5264maxresident)k 0inputs+0outputs (0major+387minor)pagefaults 0swaps
foldl'では実行時間がかなり延びましたが、foldrは相変わらず計測不能な時間内に終了しました。
最適化を有効にしてみると……
ちなみに、 ghc -O2 で最適化を有効にすると、foldl と foldl' の差がほとんどなくなります。
foldl(入力リストのサイズは100,000,000)
colinux> ghc -O2 fold1_big.hs [1 of 1] Compiling Main ( fold1_big.hs, fold1_big.o ) Linking fold1_big ... colinux> /usr/bin/time ./fold1_big False 1.71user 0.00system 0:01.72elapsed 99%CPU (0avgtext+0avgdata 7184maxresident)k 0inputs+0outputs (0major+506minor)pagefaults 0swaps
foldl'(同条件)
colinux> ghc -O2 fold1__big.hs [1 of 1] Compiling Main ( fold1__big.hs, fold1__big.o ) Linking fold1__big ... colinux> /usr/bin/time ./fold1__big False 1.81user 0.01system 0:01.82elapsed 100%CPU (0avgtext+0avgdata 7184maxresident)k 0inputs+0outputs (0major+506minor)pagefaults 0swaps
それでも、最適化なしのfoldrには追いつけませんでした。
