#rustfestの発表
yoshが #rustfest の発表が、すごい面白かったとツイートしているのを見ました。
Reading list:
— yosh at rustfest (@yoshuawuyts) May 26, 2018
- https://t.co/CSO8OCB3jM
- https://t.co/Zr6BBRa1ye
And more, linked in the slides: pic.twitter.com/eafHj3oTDj
B木の論文
リンクを貼ってある先が RRB-Trees: Efficient Immutable Vectors いきなりこれを読むのは辛いので、一番古い引用文献*1
[2] R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta informatica, 1(3):173–189, 1972.
をググります。2300引用されている神文献のようです。
Organization and Maintenance of Large Ordered Indexes
どうやらB木の論文のようです。
AVL木の論文
ついでに更に最古引用文献
- Adelson-Velskii, G.M., Landis, E. M. : An information organization algorithm. DANSSSR, 146, 263-266 (1962).
をあさります。
タイトルは違うのですが、著者と発表年を見るとこれのようです。 中身はロシア語なので読めませんでした。 ていうかSSSRって、何かと思ったら旧ソ連のことでした。驚きました。
AVL tree - Wikipediaを見るとAVL木の論文のようです。 AVLって何かと思ったら、Adel'son-Vel'skiiとLandisの頭文字でした。RSA的なネーミングですね。
この辺のことが話題になるということは、Rustは、新しいシステムプログラミング言語なので、まだデータ構造のライブラリが少なく、自分で実装するチャンスがあるのかもしれません。
素振るには?
アルゴリズムの解説はAVL木 - Wikipediaにありますが、理解するには実装するのが手っ取り早いです。 C言語やRustのような低レイヤーの言語で実装しないと理解できないのでしょうか? 使い慣れたJavaScriptで実装しても理解できるものなのでしょうか? と、悩んでいたら
JavaScriptで様々なデータ構造/探索アルゴリズムを実装しているリポジトリ。 "trekhleb/javascript-algorithms: Algorithms and data structures impl…" https://t.co/WmICiOfKKd
— azu (@azu_re) May 27, 2018
AVL Treeの実装も含まれていました。 これを参考にすると良さそうです。
*1:古典なので既知の情報である確率が高い上に、わざわざ引用しているので読む価値が高いと仮定