[id:lethevert:20070819:p1]であげた配列操作の中で、文字列のみと書いているのは、文字列のみ標準関数が提供されているのであるが、この実装はABCマシンで文字列専用のプリミティブが用意されていて、特別に効率よく操作できるようになっている。 で、これを一般の配列でも同じ関数を提供したいのだが、そのためには[id:lethevert:20070820:p1]であげた型クラスの制限があるので、それを意識して定義しなおす必要がある。

++と+++の違いは、++は第２引数の評価がlazyなのに対して、+++はeagerなところです。 って、そんなことでいいのかなぁ

cons 連結 n番目の要素 最初の要素 残りのリスト n番目の要素の更新 スライス Clean list ［a:aa］ aa ++ bb aa !! n hd aa tl aa updateAt n elm aa aa % (i,j) Clean array - aa +++ bb (文字列のみ） aa.[n] aa.[0] - aa := (n,elm)（文字列のみ） aa % (i,j)（文字列のみ） Haskell list a:aa aa ++ bb aa !! n…

[id:lethevert:20070815:p4] 修正版がリリースされたようです。 ftp://ftp.cs.ru.nl/pub/Clean/Clean22/linux/

[id:lethevert:20070815:p3] コンパイルしてみたら、gmp.cのコンパイルで警告が。 #include が不足しているみたいだ。 - ということで、小町算をリベンジしてみた。 [id:lethevert:20070718:p2]のプログラムとほとんど変わらない。Main.iclxが整数演算版で、MainR.iclxが有理数演算版。 実行時間は２倍くらいになって、2.3秒くらい。 $ diff Main.iclx MainR.iclx 1c1 < mod…

http://vag.wiki-site.com/index.php/UniqComb Cleanの一意型をうまく扱うためにさまざまなコンビネータを作ってみた人の記録。

[id:lethevert:20070813:p3] スタックオーバーフローだったようだ。しかし、gccがアレなせいで検知できなくて無限ループしてしまっていたらしい。

ftp://ftp.cs.ru.nl/pub/Clean/Clean22/linux/ こんなところにパッケージが。表のサイトからはリンクされてないよ？

いろいろ試しているわけですが、いまのところ、次のセッティングが一番効率がよくなるようで。 :: String2 :== String2Cons Char :: String2Cons a = ST !{#Char} | FT !(FingerTree Int String2Elem) BLOCKSIZE :== 512 :: String2Elem = {cArr :: !{#Char} ,sInd :: !Int ,eInd :: !Int } これで決まりかなー、という感…

文字列の連結に特化してテストプログラムを書いてみた 番号 内容 N=10000 N=50000 #0 文字配列 0.14 3.24 #1 文字配列 ブロック毎 0.02 0.32 #2 リスト 1.41 - #3 リスト reverse 0.00 0.01 #4 リスト ブロック毎 0.11 2.26 #5 String2 0.00 0.04 #6 String2 ブロック毎 0.00 0.03 連結要素数が増えるにしたがって、String2の速度が圧倒的になっていくわけだけ…

簡単な速度調査とかやってみて分かったのは、文字列としての文字配列の性能というのはバカにならないくらいよいということだ。それは、Cleanのような非破壊的な文字配列であってもそうなのだ。 これは、まあ、結果を見てみればそうだろうと思ったのだけれど、結果を見るまではあまり想定していなかった。やはり、実験はしてみるものだ。 とはいえ、文字配列を文字列として使うのは、使い方によっては非効率が生まれるのは実験結果にも表れているわけで、文字配列のよい所とFinger treesのよい所を…

その上で、さらに少し書き換えてみて気づいたこと。 String2ではFinger treeの要素として、 :: String2Elem = {cArr :: !{#Char} ,sInd :: !Int ,eInd :: !Int } というレコードを生成している。で、どうもこのレコードの生成・アクセスコストがかなり影響しているのではないかという気がする。 これは、String2のデータ型を :: String2 = ST !String2Elem | FT !(Finger…

http://citeseer.ist.psu.edu/nocker91concurrent.html

65536個を越える要素を追加すると、measure関数が返ってこなくなる。 - Cleanのバグ臭い。 module Test5 import StdBase, Test5Add Start = foldl add 0 (take 65536 (repeat 1)) implementation module Test5Add import StdInt add :: Int Int -> Int add a b = a + b というプログラムを作ると、65536ならば結…

テストプログラムを書いてベンチマークを取ってみているのだけれど、組み込みの方が速い。それどころか、String2の方には見えてはいけない文字列が表示されているような気が・・・組み込みの方が速いのは、メモリの再利用をしやすいプログラムになっているからで、そうでなくすれば違いが出てくると思うのだけれど、どうかけばよいものか？ - どう見てもバッファーオーバーフローだなー。 シンプルな再現プログラムが書けないかな。 - 書けた。 Windows版だと、デフォルトでインデックスチェッ…

とりあえず、 -ci -lsetの２つは、常に付けておくとよいと思う。

適当なテストプログラムを書いて、速度調査してみた。 結果は次の通り。 組み込み文字列 $ ./bench_string 10000 "tabcdeabcdeqwertabcdeabcdertabcdeabcdeqwertabcdeabcdedeqwertabcdeabcdeqwertabcdeabcdeqwertabcdeabcdetabcdeabcdeqwertabcdeabcdertabcdeab" Execution: 0.13 Garbage collection: …

最近、こればっか。 リストを与えられて、そこからFinger treeを作るという関数 listToTree を作るとして、どうやって作るか。 単純には、pushLを連続的に適用して、 listToTree ls = foldr pushL Empty lsとやって、pushLがO(1)なのでこれでもよいのだ（し、論文はこれで書いている）けれど、もっと効率よくできるはずだよね、という。 例えば、 listToTree ls # len = length ls pr = tak…

右からリストで与えられた要素を追加するというもの。 FingerTreeというのは、左の方はリストと同順で並んでいるけれど、右の方はリストと逆順で並んでいるので、右から追加するという操作はちょっと複雑な動きになる。その辺を効率よく操作したいと思って、いろいろ試行錯誤。

Finger treeの定義は、次のようにしていたのだけれど、 :: Tree v a = Empty | Single !a | Deep v !(Digit a) (Tree v (Node v a)) !(Digit a) :: Digit a :== [a]Digitの所が遅延リストだったので、不必要な非正格性が残ってしまっていた。そこで、正格リストを使って書き直してみた。 :: Digit a :== [!a!]結構修正個所が多かった。

実装完了。sourceforgeのリポジトリにチェックインした。 https://cleanoptenv.svn.sourceforge.net/svnroot/cleanoptenv/trunk/Data - String2も作って、チェックインした。

まえに、toListがあればreduceいらないけど・・・という話を書いた。 [id:lethevert:20070802:p1] reduceとtoListは表裏なのだけれど、効率のことを考えてみると（思考実験だけ） reduceは、コレクションに含まれている要素に直接関数適用していくので効率よさそうに思える。それに対し、toListとfoldrの組み合わせは一度リストを作ってしまうので、オーバーヘッドがありそうに思える。 しかし、多分、現実は逆ではないか。 というのは、高…

先の話は、ちょっと間違ってるな。 同じ高階関数でも、mapはマクロではない。マクロで定義しているのはfoldl/foldrだけだ。 そういえば、この件は、Clean入門の記事を書いていたときに、一度考察していた。 foldl/foldrは、正格性解析の結果で最適な評価順序が変わる種類の関数だったので、正格性解析を適切に機能させるためにマクロにしているのでした。 http://www.geocities.jp/lethevert/clean/gettingStarted17.h…

正格性をどの程度設定するかを検討している。 http://www.kmonos.net/wlog/76.html#_1947070805 にあるように、ある程度の非正格性を残して置く方がよいケースもあるのだけれど、一般的には正格にできるところは正格にしておく方が効率がよい。 Annotated finger treesなので、measureするところで計算が発生する。この計算は、最悪で全要素をなめるので、この計算のところで木全体が評価されてしまう。さらに、この計算は、要素の追…

基本的なところは大体実装できた。 作りながら思っていたのだけれど、これってどういうところに使うのがいいだろう？ 参考にしている論文には random-access sequences max-priority queues ordered sequences interval trees という例がある。 Finger Treeのよい所は、両端のどちらにもO(1)で要素を追加・削除できるところと、任意の場所で分割することがO(log N)でできるところ。 ただし、高階関数は効…

http://page.freett.com/shelarcy/log/2007/diary_08.html#why_we_spend_many_time_to_build_ghc 逆に言えば、既に（最適化された）GHC をインストール済みの環境で、最適化オプションを外してビルドする場合には、かなり高速にビルドを終えることができます。……といっても、それなりの時間はかかりますが。手元の環境では、extra libraries やドキュメントの生成も含め、20分ぐらいの時間でビ…

型があるということは、プログラミングの上での制約になることもあるのだけれど、型のおかげでプログラミングの柔軟性が向上することもある。Cleanの演算子は１つの典型だ。 Cleanの演算子は、使える文字の種類に制限がない。なので、次のような演算子を定義することができる。 (startsWith) infix 9 :: !String !String -> Bool でこれを使うことで、次のような式が書ける trim str startsWith prefix ただし、trimは…

なんじゃこりゃー どこらへんにConcurrent Cleanが関連しているのですか？

[id:lethevert:20070807:p1] まあ、型クラスで行う辞書渡しを手作業で実装すればいいだけですけどね。

型クラスのインスタンスにはspecialを付けることで特化関数を生成することができる。 class Deque q a instance Deque (FingerTree v) a | Monoid v special v = Int; v = Real と書くと、FingerTree v aのDeque操作に関する関数群に、一般の型に対する関数の他に、v = Int と v = Real についての特化した関数が作られる。特化関数は、関数辞書を渡す必要がないため、効率が向…