Concurrent Clean : Finger trees
実装完了。sourceforgeのリポジトリにチェックインした。
https://cleanoptenv.svn.sourceforge.net/svnroot/cleanoptenv/trunk/Data
-
-
- -
-
String2も作って、チェックインした。
おぶじぇくとしこー : 名詞抽出法
名詞抽出法なんてものがあるのかっ。
なんていうか、くらくらするな。いままで考えたこともなかったよ。
「オブジェクト指向 = 英語の語順」な思考はこのへんにも元凶があるのかな。
-
-
- -
-
本来の使いかたは、クラスの候補を探すための手がかりとして使うという話なのだな。それなら理解できなくもない。
Java : JDBC
http://d.hatena.ne.jp/odz/20070810/1186764019
http://d.hatena.ne.jp/bleis-tift/20070812/1186847743
また危険な話題に手を出しているような気がしますが・・・
RDBというのは並行アクセスを前提としたシステムなので、トランザクション分離レベルというような概念があるわけで、そのことを忘れてはまずいのではないかと。
ResultSetで読み取っている行には、排他制御のためにロックがかかっていたりするわけで、ロックをかけている行からしかデータが読み出せないようなAPIになっているわけですよ。それを、Iterableとかにしてしまうと、
ArrayList<Record> list = new ArrayList<Record>(); for (Record rec : resultset) { list.add(rec); }
なんて書けるわけで、ロックが外れてしまった行へのアクセスオブジェクトが残ってしまって危険ですよね。
それに、一行に含まれるデータを1回ですべて転送するわけではないということもありますし。例えば、1つの列が数百MBになるBLOBデータを含むような行をfetchするようなケースは、一度に読み込んでしまうわけにはいかないですよね。また、updateXXX()のためだけに選択列に含めているという場合もあります。wasNull()は対象となっている列が読み込まれていないというケースも考慮した上でのAPIになっているのではないかと。
結果の件数も、RDBの仕組み上、前もって知ることは不可能な情報なので、ResultSetに含まれないのは仕方ないというか当然ではないかと。JOINしている全表をロックしてしまうならともかく、そうでなければ、並行して実行されているSQLによって結果の件数は変わり得るので、全部処理した後までは結果の件数は確定できないですよね。
そもそも、JDBCをビジネスロジックに直接組み込もうとか考えるからおかしなことになるのであって、使いかたに応じて適切に抽象化して使えばいいだけのことで、それはどういうプログラムでも基本的に同じことじゃないのかなぁ。
Haskell : 回文を見つけるアルゴリズム
http://johanjeuring.blogspot.com/2007/08/finding-palindromes.html
文字列に含まれる回文を線形時間で見つけることができるアルゴリズムだそうです。
Concurrent Clean : Finger trees : 正格リスト
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!]
結構修正個所が多かった。
Concurrent Clean : Finger trees : appendR
右からリストで与えられた要素を追加するというもの。
FingerTreeというのは、左の方はリストと同順で並んでいるけれど、右の方はリストと逆順で並んでいるので、右から追加するという操作はちょっと複雑な動きになる。その辺を効率よく操作したいと思って、いろいろ試行錯誤。
Concurrent Clean : Finger trees : listToTree
最近、こればっか。
リストを与えられて、そこからFinger treeを作るという関数 listToTree を作るとして、どうやって作るか。
単純には、pushLを連続的に適用して、
listToTree ls = foldr pushL Empty ls
とやって、pushLがO(1)なのでこれでもよいのだ(し、論文はこれで書いている)けれど、もっと効率よくできるはずだよね、という。
例えば、
listToTree ls # len = length ls pr = take 4 ls sf = drop (len - 4) ls md = take (len - 8) (drop 4 ls) = Deep pr (listToTree (nodes md)) sf
というのはどうか、とか思うわけだけれど、これには罠が。再帰するたびにlengthを呼んでいるのが微妙だ。もっとも、nodesがリストの長さを1/3にするので、線形であることに変わりはないのだけれど、嬉しくない。
じゃあ、こういうのはどうだろう?
listToTree ls # len = length ls (p,s) = splitAt (len / 2) ls = toTree p (reverse s) toTree [] [] = Empty toTree [a] [] = Single a toTree [] [a] = Single a toTree p s # (pr,pm) = splitAt 4 p (sf,sm) = splitAt 4 s pm = nodes pm sm = reverse_nodes sm = Deep pr (toTree pm sm) (reverse sf)
これならlengthを一回しか呼ばないし、リストの先頭にしかアクセスしないので、効率がいいんじゃないかな?