週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

以前のHaskellの例外の記事を書いたときから考えていたことなのですが、ある値の要素をすべて正則評価する関数は書けるのでしょうか。値がただのIntやDoubleなどならそのままseqで評価して、タプルやリストならその要素をすべて評価するというようなものです。コードにすると次のようになります。

xがIntやDoubleなど、構造を持たない型なら
seqAll x y = seq x y
リストを引数にすると、次のようにリストの中身を正則評価します。タプルも同様。
seqAll [] y = y
seqAll (x:xs) y = x `seqAll` xs `seqAll` y
さらに、複雑なデータ型を分解します。
Data Tree a = TreeLeaf | TreeNode (Tree a) (Tree a)
seqAll TreeLeaf y = y
seqAll (TreeNode a b) y = a `seqAll` b `seqAll` y

注目してほしいのは、リストを引数としたときの右辺はseqAllになっていること。このため、リストのリストがきたときも、その中身をすべて正則評価します。

明らかに無茶なのが最後の例です。Haskellではそんな無茶なコード生成はサポートされてません。最後の例以外は何とかなるでしょうか?

コードを try や catch の引数にしておけば、その外には例外は漏れない。そう思っていた時期が(ry

以下てきとうに。ソースは見てません。でもここら辺の挙動は別にghcのソース見なくても言語レベルで決まっている気がします。どこを読めばいいのかわかりませんが。

Haskellのlazy evaluationって、ようするにHaskellの型Aはすべてocamlにおける"() -> A"に対応する、とか考えておけばいいかしらと思っています。たとえば次のコード。

result <- try $ do
                let x = f 10
                return x
ここで帰ってくるのはxではなくて、評価するとxが帰ってくるサンクです。適当な関数f 10 はreturn xの時点ではまだ評価されていません。 tryから帰ってきた後でサンクを評価して例外が発生しても、tryでは捕まえてくれません。

これはどうにかならないんでしょうか。tryは外に返すサンクにも責任を持つとか。無理そうですが。

次善策として、返値をtryの中で積極評価してしまえば大丈夫です。上の例だと、次のようにseq xを導入すればokです。

result <- try $ do
                let x = f 10
                seq x $ return x
seq :: a -> b -> bは、 第一引数を必ず評価してから第二引数を返してくれます。積極評価のための関数です。こうしておけばxは評価され、tryの外では例外は起こりません。

ここまでがnyaasanのところでのコメントの補足です。


積極評価は、xがIntやFloatなど単純な値だとよいのですが、複雑な値、たとえばリストとかタプルとかだとまた厄介です。

result <- try $ do
        let x = (f 10, f 20)
        seq x $ return x
この場合、f 10やf 20が例外をはいたとしても、それはtryではつかまりません。seq xしていてもです。

x::(Int, Int)の場合、xを積極評価しても、xの中身は評価されません。具体的にMLのように書くと、評価する前のxの型は() -> (()->Int, ()->Int)のようなもので、seq xしても現れるのは(()->Int, ()->Int)です。xがなんかタプル二つであるというところまでしか評価されません。次のように中身を丁寧に評価すれば大丈夫です。

result <- try $ do
        let x = (f 10, f 20)
        fst x `seq` snd x `seq` return x

途中経過です。詳しいことは省略。

とりあえずpattern, templateは結構酷使されることがわかったので、なるべく軽くしてみようとlistで確保。

プロファイル。例によって詳細は続きに。実行時間が17秒とか減りました。効果ありです。といってもたいした改善にはなっていません。実時間で測定したところ102秒でした。

プロファイリングで時間のかかるところがわかったとはいえ、改善はまだまだこれからの模様です。次はRNAをすぐ出力したり、searchを速くしてみたりしてみます。

ところで、プロファイルの結果に経過時間の絶対値が出ないのは、あまりよくないような気がします。コードの変更でどの程度速度が向上したかわかりません。そのような情報も出すオプションがあるかも知れませんが。

前回さらしたソースコード、ところどころ正則評価をしてみたのが残っていました。それらを除いてprofilingしてみましたが、結果は変わりませんでした。

重い箇所はmatch, replaceとのことですが、具体的にどの処理が重いのかはよくわかりません。プロファイリングの粒度を細かくすることによって原因を突き止めます。

ghcのプロファイラでは、{-# SCC "hoge" #-}というコメントを入れることによって任意の箇所での計算時間を測ることができます。これを利用。match, replaceをpattern, templateの種類ごとに分割してプロファイリングしてみます。

結果は圧縮して続きに貼りました。 プロファイルの結果、matchRやreplaceBaseが重いことがわかってきました。matchRはDNAの分割を伴うので、重いことはわかっています。一方replaceBaseは非常に軽い処理ですが、呼ばれる回数が非常に多いので全体で時間がかかっています。また、match, replaceそのものもまだ結構時間がかかっています。

次回はこのコードを速くしてみます。できれば。

プロファイリングをしてみました。

とりあえずここまでの記録としてソースをさらします。Dna2rna.hs 。コメントとか全然ないのでごめんなさい。

まず、GHCのマニュアルのプロファイリングの部分を読みながら再コンパイルします。

> ghc --make -prof -auto-all Dna2rna.hs
[1 of 1] Compiling Main             ( Dna2rna.hs, Dna2rna.o )
Linking Dna2rna.exe ...

> Dna2rna.exe +
RTS -K67108864 -p -RTS < ..\..\icfpcontest.org\endo.dna > test.rna
すると.profというファイルに結果が出てきます。結果は次のとおり。
total time  =      175.90 secs   (3518 ticks @ 50 ms)
total alloc = 51,094,671,140 bytes  (excludes profiling overheads)

COST CENTRE       MODULE   %time %alloc

matcher           Main      27.2   16.4
replacer          Main      23.1   25.6
consumeTemplate   Main      16.8   24.9
consumeNat        Main      12.3   16.1
consumePattern    Main       6.9    7.3
searchSequence    Main       4.1    4.1
executeOnceIO     Main       2.4    0.9
debugPrintTag     Main       1.4    0.1
main              Main       1.3    2.0
executeIO         Main       1.2    0.2
outputRNA         Main       1.1    0.3
quoteDNA          Main       0.7    1.1

プロファイラによると、重いのはmatchReplaceです。 しかも、そのなかでも重いのはbrute force searchをしているsearchSequenceでも、重そうに見えるprotectでもなく、matchreplace本文です。

前回の予想は外れでした。 RNAのかかわる部分であるoutputRNA, consumePattern, consumeTemplateは別に重くありませんでした。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。