編集可能
2010年9月16日

wt-tree のバグの話題 @chaton_gauche まとめ。

あとで勉強するとき用。
0
Chaton Gauche @chaton_gauche

kazu: MIT Scheme のことで恐縮ですが、質問させて下さい。 http://bit.ly/9WU3mS

2010-09-14 17:46:24
Chaton Gauche @chaton_gauche

kazu: 質問は、「MIT Scheme に wttee というライブラリがありますが、これはどれくらいつかわれていますか?」です。 http://bit.ly/95Yb6o

2010-09-14 17:47:11
Chaton Gauche @chaton_gauche

kazu: 長いですが、背景を書いていきます。 http://bit.ly/c1E9Wq

2010-09-14 17:47:31
Chaton Gauche @chaton_gauche

kazu: Haskell には、Data.Map という finite map の実装があります。 http://bit.ly/bxlGsH

2010-09-14 17:47:50
Chaton Gauche @chaton_gauche

kazu: 内部では、weight binary search tree というバランス木が使われています。 http://bit.ly/aJIZTi

2010-09-14 17:48:46
Chaton Gauche @chaton_gauche

kazu: the art of computre programming 3 では、AVL の代替品として半ページぐらい紹介されている木です。 http://bit.ly/ahD7r2

2010-09-14 17:49:44
Chaton Gauche @chaton_gauche

kazu: 最近、Data.Map にバグが発見されました。 http://bit.ly/bhQN3w

2010-09-14 17:50:00
Chaton Gauche @chaton_gauche

kazu: 挿入はいいのですが、要素を削除すると、バランスが壊れることがあるのです。 http://bit.ly/bw1t9Q

2010-09-14 17:50:22
Chaton Gauche @chaton_gauche

kazu: これをきっかけに、weight binary search tree を研究してみて、面白いことが分かったので、現在論文を書いているところです。 http://bit.ly/aWysXC

2010-09-14 17:51:07
Chaton Gauche @chaton_gauche

kazu: 同じアルゴリズムが、MIT Scheme の wttree にも使われています。 http://bit.ly/9e4bFp

2010-09-14 17:51:34
Chaton Gauche @chaton_gauche

kazu: wttree の亜種を考えた Stephen Adams さんが、MIT Scheme のメンテナーだったみたいなので、入っていても不思議ではありません。 http://bit.ly/b7atGZ

2010-09-14 17:52:29
Chaton Gauche @chaton_gauche

kazu: Data.Map の実装も、Adams さんのテクニカルレポートに基づいています。 http://bit.ly/9147wo

2010-09-14 17:52:51
Chaton Gauche @chaton_gauche

kazu: というわけで、MIT Scheme の wttree にもバグがあります。 http://bit.ly/9v58Zy

2010-09-14 17:53:10
Chaton Gauche @chaton_gauche

kazu: 実際、実験してみたところ、やはり削除で簡単にバランスを崩すことができます。 http://bit.ly/9XwQAB

2010-09-14 17:53:41
Chaton Gauche @chaton_gauche

shiro: 実装のバグではなくアルゴリズム上のバグだったってことですか? http://bit.ly/bPTqJ5

2010-09-14 17:53:48
Chaton Gauche @chaton_gauche

kazu: 大枠のアルゴリズムはいいのですが、パラメーターの選び方がダメです。 http://bit.ly/daLrVU

2010-09-14 17:54:36
Chaton Gauche @chaton_gauche

kazu: Adams さんの wttree のパラメーターは (5,1) なんですが、これは削除のことをまったく考えていません。 http://bit.ly/bWZYrD

2010-09-14 17:55:16
Chaton Gauche @chaton_gauche

kazu: (x,y) の x は、バランスが取れてないか判断して回転させるかを決めるもの、y は回転させるときに一回転か、二回転かを決めるものです。 http://bit.ly/cHA3Hs

2010-09-14 17:56:01
Chaton Gauche @chaton_gauche

kazu: Adams さんの方式に対しては、数学的に証明を与えられていませんが、我々のテストでは (4,2) と (3,2) のときしかバランスが成り立ちません。 http://bit.ly/dBUhbw

2010-09-14 17:56:44
Chaton Gauche @chaton_gauche

higepon: slib に含まれているようですね。 http://bit.ly/biBEEA

2010-09-14 17:58:13
Chaton Gauche @chaton_gauche

kazu: Adams さんが元にしていて、TAOCP でも紹介されているオリジナルの論文の方式に対しては、我々は Coq で証明を与えられそうなところまで来ています。オリジナルの論文の方式に対する整数解は面白いことに (3,2) しか… http://bit.ly/c4JFDp

2010-09-14 17:58:19
Chaton Gauche @chaton_gauche

kazu: 興味があれば、我々の英語のスライドをお送りします。 http://bit.ly/cnH0eJ

2010-09-14 17:59:03
残りを読む(32)

コメント

コメントがまだありません。感想を最初に伝えてみませんか?