[OSASK 1831] Re: [FYI]Skip Lists

[Hidemi KAWAI <kawai !Atmark! imasy.org>]

  こんにちは、川合です。


Koyanagi Masaaki さんは 2001/07/17 21:47:22 の「[OSASK 1830] [FY
I]Skip Lists」で書きました：

>"Skip Lists" というおもしろいデータ構造を見つけましたので紹介します。
>1990年にWilliam Pugh によって平衡木の代替として開発されたかなり新しい
>データ構造で、検索にかかる平均計算量が O(log n) であり、かつ実装が非常
>に簡単です。

  ありがとうございます。さっそく日本語の方を読みました。面白かっ
たです。

>OSASK の開発に役立つといいですね。

  僕が見たページの方には、

  「この平衡木の一種である AVL Tree は 『tcsh と実習でしか使わな
い』 と言われるほどの困難さで、 大抵の場合バグがある。 」

と書かれていますが、実は僕はこのAVL木をかなり究めた事があります
。・・・実は、僕は物理学的な現象のシミュレーションにおいてLRUア
ルゴリズムとAVL木を組み合わせた「キャッシュバッファ」を作り、シ
ミュレーション計算速度を最大で1000倍に高める事に成功したのです（
平均では20〜100倍程度ですが）。この成功のおかげで無事に大学院を
卒業しました（笑）。・・・10年はかかると思われていた高分子結晶の
結晶欠陥に関するシミュレーションを、現実的な時間内で終わらせるめ
どをつけたのが評価されたようです。

  ということで、僕にとってはAVL木はそんなに難しくなかったりしま
す。ちょっと面倒なだけです。

  しかし、僕はAVL木は現在のパソコンには向かないと考えています。
検索時のキャッシュヒット率が悪いです。これを改善するには、B*木が
いいと考えています。そして、OSASK内部のノード管理はB*木で管理す
る予定です。

  そんなわけで、この「Skip Lists」はすぐには使う予定はありません
。でも、B*木版だけではなくて、Skip Lists版も作ってみたいですね。
AVL木版も作りたいです。それで、いろいろベンチマークを走らせて、
一番良いのはどれかを比較検討してみたいです。・・・そんな余裕がい
つごろになったら出てくるのかは分かりませんが（笑）。


  それでは。

--
    川合 秀実(KAWAI Hidemi)
川合堂社長 / OSASK計画総指揮 / カーネル開発班
E-mail:kawai !Atmark! imasy.org
Homepage http://www.imasy.org/~kawai/