夜中からの Haskell 談義

herumi @herumi

@ikegami__ ああ，申し訳ありません．コードは正しいのですが，日記の文章が間違ってました．mは固定でnを大きくしたときの話です．配列をiterateで作って捨てていくのですが，古いやつは触らないのでGCがすぐさま回収して再利用して欲しいという初心者の願望が入ってます．

Hideyuki Tanaka @tanakh

@herumi http://ideone.com/uGYyR それなりに頑張ってみまして、これで-O2 -fvia-C で 0m0.401s ぐらいです。C++版は0m0.209sでした。まだ二倍ほど遅いですが、どうも配列のコピーのコストが若干C++よりも大きい様で難しいです

めるぽん.c @melponn

Haskell で副作用のあるコードってこんな綺麗に書けるものだったのか･･･

Hideyuki Tanaka @tanakh

@gusmachine vectorはHaskellの従来の配列、ArrayとかIOArrayとかIOUArrayとかSTArrayとかを置き換えるものです。主に高速なランダムアクセスと逐次的更新が目的で、さらにByteStringと同様にStream Fusionがあります。

shelarcy（しぇらーしぃ） @shelarcy

@tanakh @gusmachine 残念ながら ByteString の現在の実装では Stream Fusion しなくなっています。 http://j.mp/f5vv0a （Text は Stream Fusion します。 http://j.mp/gaYTfd ）

shelarcy（しぇらーしぃ） @shelarcy

@tanakh @gusmachine あと、Stream Fusion だけでなくランダムアクセスの効率化を目的とした Recycling も行うのが vector の特徴ですね。（手前味噌ですが。 http://j.mp/fThJoL ）

Hideyuki Tanaka @tanakh

@shelarcy あらー、なんとー。なんででしょう…。

shelarcy（しぇらーしぃ） @shelarcy

@tanakh GHC 6.12.x では PrimMonad を使った処理は ST モナドに比べて遅いので、速いコードの例を示す場合にはその辺注意してください。（7.0.x では問題ありませんが。 ） http://j.mp/i4BCqM http://j.mp/ea2x4q

Hideyuki Tanaka @tanakh

@shelarcy なるほどー。このへんのバッドノウハウを気にせずにコードが書ける時代がやってきて欲しいものでつ…。

shelarcy（しぇらーしぃ） @shelarcy

@tanakh 経緯を追っていないので理由は想像するしかないですけれど、Stream Fusion 単体ではランダムアクセスの効率化が図れないので一文字 = 8 bit な仮定の元処理の効率化を図ろうとする ByteString には都合が悪かったのではないでしょうか？

shelarcy（しぇらーしぃ） @shelarcy

@tanakh UTF-32 ではなく UTF-16 で文字を詰めている Text ではこの辺諦められますけれど、ByteString では看過できないコストだったとそういうことだと思います。（ByteStirngが出た頃にはまだRecyclingのアイデアもありませんでしたし）

Hideyuki Tanaka @tanakh

@shelarcy うーむなるほど。その点Textは問題なかったと。

shelarcy（しぇらーしぃ） @shelarcy

@tanakh はい。UTF-16 な文字を格納するという制約上、定数時間での参照を諦めて線形時間での参照にしてますからね。 http://j.mp/fxRXoN

shelarcy（しぇらーしぃ） @shelarcy

@tanakh @herumi 配列のコピーのコストに関しては、今ちょうど安くする為の primitive を新しく取り入れようとしているところですね。 http://hackage.haskell.org/trac/ghc/ticket/4928

Hideyuki Tanaka @tanakh

@shelarcy なるほど。抜かりないですね。

shelarcy（しぇらーしぃ） @shelarcy

@herumi @melponn @tanakh vector が Haskell Platform に入れば良いんですが……最近はそんなに沢山ライブラリを提供しなくても cabal コマンドでインストールすれば良いという意見も強くなってきてるので、難しいかもしれませんね。

shelarcy（しぇらーしぃ） @shelarcy

@herumi あっ、標準しばりというのなら、GHC だけではなくて Haskell Platform （GHC 6.12.3 なら Haskell Platform 2010.2.0.0）に入っているライブラリは使用するライブラリの仲間に加えてやって下さい。と、念のため。

herumi @herumi

@tanakh ありがとうございます．あとで確認します．vector使わないバージョンは難しいのでしょうか．Project EulerをC++でやる場合でもboost, GMP(多倍長演算)などの外部ライブラリ無し，0x無し縛りでやってるので…．

herumi @herumi

@melponn そうですか．forとか定義してるし，これだけ見ると私は逆に中途半端な手続き型言語に見えました．

herumi @herumi

http://ideone.com/uGYyR を動かしてみたらSegmentation fault/access violation in generated codeで落ちた．何が悪いのかなあ．環境はWindows XP+GHC 6.12.3+vector-0.7.0.1.

めるぽん.c @melponn

@herumi うーん、これだけ手続きっぽく書けるなら書き換えある処理でも普通にHaskell使えるんじゃないかとか思ったのですが、まあパッと見の印象なのでちゃんと書く時になったら中途半端だと思うかもしれないです

herumi @herumi

あれ，もしかしてIntが64bitを仮定してるのかな．

herumi @herumi

IntをWord64にして少しいじったら動くようにはなった．http://ideone.com/dcYha でもC++版1.69secに対してHaskell 11.47sec．castし過ぎか． あ，@shelarcyさんが指摘されてたGHC6.12.xのvector遅い問題か．

herumi @herumi

@melponn なるほど．そういうことですね．

herumi @herumi

というか，11.47secなら私が日記に書いてたコード(12.45sec)とたいして変わらない…．(PentiumD 2.8GHz)