So-net無料ブログ作成
検索選択

Haskellのメモリ使用量(2) [Haskell]

先日の,AOJのMaximum Profitの件の続き.

まず,前回の記事で誤解しているところがあった.メモリ使用量が2.6GBとあったが,これはallocateした延べ量だった.ピークメモリ量は260kB程度だった.2.6GBはProfiling Reportから読んだ数字だが,ピークメモリ量はtimeコマンドで測定できる
% /usr/bin/time -f "%M" {コマンド}

メモリ使用量≒入力サイズということは,遅延評価のために全データがメモリに展開されているだろうと色々試行錯誤の上,ようやくAcceptされたコードが以下.
import Data.List
import System.IO

f :: (Int,Int) -> Int -> (Int,Int)
f (m,a) x =
  let m' = min m x
      a' = max a (x-m)
  in
    (m',a')

exec :: (Int,Int) -> IO (Int,Int)
exec (m,a)= do
  l <- getLine
  let i = read l :: Int
      o = (m,a) `seq` i `seq` f (m,a) i
  eof <- isEOF
  if eof
  then return o
  else exec o

main = do
  n <- getLine
  (_,o) <- exec (2000000000,-2000000000)
  print o

mapとかfoldとかHaskellっぽいものは一切使わず,1データ毎に正格評価して処理するというHaskellらしくないもの.全然気に入らないけど,他にどう書いたものか分からない...

にほんブログ村 自転車ブログ ブルベへ
にほんブログ村

Haskellのメモリ使用量 [Haskell]

Haskellで,AOJ (Aizu Online Judge)のMaximum Profitに挑戦している.

最初は演算量にも難儀してTime Limit Exceededの壁を越えられず苦労していたんだけど,こちらの方は「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」を読んでO(n)のアルゴリズムが分かったので解決.(目から鱗)

ところがMemory Limit Exceededエラーの壁を越えられない.

以下が現在のコード.
ans' m a [] = a
ans' m a (x:xs) = 
  let m' = min m x
      a' = max a (x-m)
  in
    ans' m' a' xs

ans x = 
    let (x0:x1:xs) = x
        init_max  = x1 - x0
    in
      ans' x0 init_max (x1:xs)

main = do
    n <- getLine
    c <- getContents
    let i = map read $ lines c :: [Int]
        o = ans i
    print o

これで,Case #37でメモリ使用量が2.6GBとなってしまう (制限は140MB).

うーんなんでだろう? アルゴリズム自体はメモリ量を必要とするものではないし,getContentsもLazyなはずだから必要に応じて読み出されると思うのだけど..

getContentsがバッファリングしているということだろうけど,バッファリングの量を制御する方法はあるんだろうか?


プログラミングコンテスト攻略のためのアルゴリズムとデータ構造



にほんブログ村 自転車ブログ ブルベへ
にほんブログ村

stack setupが遅い [Haskell]

Haskellのbuild環境の構築にはstackを使っているのですが,新しくセットアップしたLubuntuでstack setupしたところ,ghcのダウンロードがものすごく遅いという現象に悩まされました.

% stack setup
とするとghc-8.0.1のダウンロードが始まりますが数十kbps程度しかでず100MBのアーカイブのダウンロードに一体何時間かかるのか?という状況でした.

vmplayのネットワーク設定を疑うなど試行錯誤しましたが,結局のところ,以下の情報をもとに,proxy経由でアクセスするようにしたところ解決しました.

stack setup download incredibly slow

https_proxy=124.32.141.184:3128 stack setup

知らないproxyを通してアクセスするのは気持ち悪いですが...
タグ:Haskell Lubuntu
にほんブログ村 自転車ブログ ブルベへ
にほんブログ村

プログラミングHaskell [Haskell]

読了.訳者前書きに「この本の著者であるHutton氏は,本書を世に出すことで,Haskellは難しいというのは間違いであることを示してくれた.」とある通り,非常に分かり易い内容になっている.

Haskellの難所であるIOやMonadの説明は最低限に留め,Haskellでの関数型プログラミングをどう勧めるかを実例を通じて丁寧に説明している.200ページ強の薄い本なのでスラスラ読めるが,読後にはHaskellプログラミングを何となく掴めたような気分になる.

私にとってはこの本はReal World Haskell,すごいHaskellたのしく学ぼうに続く3冊目の本であったが,いまから思うと全く読む順が逆だったと思う.

初学者はまず「プログラミングHaskell」でHaskellプログラミングの概要を掴み,「すごいHaskellたのしく学ぼう」でHaskellの特徴的な機能について学び,最後に「Real World Haskell」で実社会の問題解決にHaskellを適用する際のアプローチについて学ぶべきだった.

今にして思うと遠回りした気がする.


プログラミングHaskell

プログラミングHaskell




すごいHaskellたのしく学ぼう!

すごいHaskellたのしく学ぼう!

  • 作者: Miran Lipovača
  • 出版社/メーカー: オーム社
  • 発売日: 2012/05/23
  • メディア: 単行本(ソフトカバー)



Real World Haskell―実戦で学ぶ関数型言語プログラミング

Real World Haskell―実戦で学ぶ関数型言語プログラミング

  • 作者: Bryan O'Sullivan
  • 出版社/メーカー: オライリージャパン
  • 発売日: 2009/10/26
  • メディア: 大型本



タグ: Haskell
にほんブログ村 自転車ブログ ブルベへ
にほんブログ村

HXT arrow lessons [Haskell]

以前書いたように,ブルベ用のGPSデータを作るのに,RideWithGPSでルートを引いた後,轍で間引いてカシミール3Dに変換する,という手順をとっているのだけど,これが結構面倒くさい.特に轍~カシミール3Dのところは単純作業なのでバッチ処理できるようにしたい.

gpxファイルの中身をみたところ,trkファイルもrteファイルもどちらもシンプルXMLファイルなので,変換自体は簡単そう.間引きには多少アルゴリズムの要素が入るがそれもそんなに難しくないだろう.

ただ,せっかく作るならばHaskellで作ってみたい.

HaskellでXMLを扱うならば,HXT (Haskell XML Toolkit)を使うのが良さそうである.が,XMLライブラリの常で,対象を汎用的,抽象的に扱おうとするから,自分がやりたいことに対して大げさでとっつきにくい.

...と困っていたところ,最初の一歩としては良いチュートリアルを見つけた.
HXT arrow lessons
XML documentを扱う基本的な演算であるArrowについて何となく理解できた.

にほんブログ村 自転車ブログ ブルベへ
にほんブログ村

Learn You a Haskell for Great Good! [Haskell]

Haskellを勉強するならばLearn You a Haskell for Great Good!がおすすめ.

私の場合でいうと,最初 Real World Haskellを手にしたんだけど,どうにも読み進められず積ん読状態になってしまっていました.

ところが,Learn You a Haskell for Great Good!を知って読み始めたところ,分かりやすくて面白い!

最初,オリジナルのhtml版を読んでいたんだけど,mobi版を見つけてKindleアプリで読むようにしたら,さらにスムーズに読むことができた.
タグ:Haskell
にほんブログ村 自転車ブログ ブルベへ
にほんブログ村

ghcid [Haskell]

Haskellのbuild環境としてstackを利用するようにした.

stackではbuild環境でのツールのバージョン管理を徹底させるために,環境ごとにコマンドやライブラリをインストールして使用するようになってるのだけど,そのためにstackでのbuildの環境とemacsのflymakeの実行環境が異なるためにerrorの出方が違うようになってしまった.

flymakeの設定を直そうかと調べたところ,最近はghcid -- "GHCi as a daemon", "GHC + a bit of an IDE"というものが使われているらしい.

ndmitchell / ghcid

端末で起動しておくと自動でソースの変更を検知して,buildの実行結果を表示するというもの.IDEというよりbuild daemonみたいだけど,やりたいことはflymakeと同じだし,editor非依存のghcidの方がいいかもしれない.

というわけで使ってみた.
% stack install ghcid
でinstallできて
% ghcid --height 16
でbuildが自動実行される.(heightは端末の行数)

はずなんだけど,emacsでファイルを編集すると以下のように言って止まっちゃう.
ghcid: /xx/xx/.#Lib.hs: getFileStatus: does not exist (No such file or directory)

emacsの一時ファイルにアクセスしようとしているところで一時ファイルが消えたので困っているのは間違いない.

調べると,#Lib.hsというのはemacsが作成するLockファイルのようで,.emacsで 'create-lockfilesをnilに設定すると作られなくなるらしい.というわけで.emacsで以下のようにして対策.
(add-hook 'haskell-mode-hook
          '(lambda ()
             (turn-on-haskell-doc-mode)
             (turn-on-haskell-indentation)
             (turn-on-haskell-indent)
             (font-lock-mode)
             (setq create-lockfiles)))



タグ:Haskell
にほんブログ村 自転車ブログ ブルベへ
にほんブログ村

Haskell QuickCheck [Haskell]

リストxの要素数がn以上の場合にはxの先頭n個の要素の平均を返し、nに満たない場合にはNothingを返す関数mavgを書いた。
take'::Int -> [a] -> Maybe [a]
take' n [] =
  if n == 0
  then Just []
  else Nothing
take' n (x:xs) =
  if n == 0
  then Just []
  else
    let rest = take' (n-1) xs
    in  rest >>= (\r -> Just (x:r))
mavg::Int -> [Double] -> Maybe Double
mavg 0 _ = Nothing
mavg n x =
  let xh = take' n x
      sumMay = foldM ( fmap . (+) ) 0
  in case xh of
    Nothing -> Nothing
    Just a -> (sumMay $ sequence $ xh) >>= (\s -> Just(s / fromIntegral(n)))

で、これをQuickCheckでテストしてみたところはまり中。
prop_mavg n x =
  let a = mavg n x
      b = ( sum $ take n x ) / fromIntegral(n)
  in
    if n > 0 && n <= length(x)
    then       
      let a' = fromJust a
      in  a' == b
    else a == Nothing
 main = do
   quickCheck prop_mavg
   let n = 3
       x = [0.0, 0.0, 5.0e-324] :: [Double]
       a = mavg n x
       b = (sum $ take n x) / fromIntegral(n) :: Double
   putStrLn $ show(a == Just b)
   putStrLn $ show(n > 0)
   putStrLn $ show(n <= length(x))
   putStrLn $ show(prop_mavg n x)


*** Failed! Falsifiable (after 29 tests and 1086 shrinks):
3
[0.0,0.0,5.0e-324]
True
True
True
Flase


n=3, x=[0.0,0.0,5.0e-324]でfailしているとのことだけど、prop_mavgの中で計算するa, bを別途計算し比較するとTrueになる。でもprop_mavg 3 [0.0, 0.0. 5.0-e324]を実行するとやっぱりFalseになる。

たぶん、浮動小数の演算誤差だと思うんだけど。。。。
にほんブログ村 自転車ブログ ブルベへ
にほんブログ村