またRustでB+Treeかいたよ

Rust標準ライブラリのBTreeMapの実装コードを参考にB+Treeをフルスクラッチで実装しました。
get, insert, remove, rangeなどの基本的な操作は実装できているので、ひとまずここに記録します。
ソースコードGitHubリポジトリに公開しています。そちらもみて見てください

github.com

どなたかのB+Treeの実装や理解の参考になれば幸いです。
(1600行程度で収まったのでstd::collections::btree_mapより追いやすくなっていればいいなと)

実装した主な操作

Rustっぽい疑似コードです。細かい仕様はソースコードみてください。

  • fn get(key) -> Option<value>
    入力に全順序なkeyを取る。もし要素が存在すれば、そのvalueを出力する。

  • fn insert(key, value) -> Option<old_value>
    入力にkeyとvalueを取る。もしkeyが既に存在すれば、値を更新し、古いvalueを出力する。

  • fn remove(key) -> Option<value>
    入力にkeyを取る。もしkeyの要素が存在すれば、その要素を削除しvalueを出力する。

  • fn iter() -> Iter<key, value>
    全要素のイテレータを出力する。

  • fn range(range) -> Range
    入力にstd::ops::Rangeを取る("0..10"などはstd::ops::Rangeの糖衣構文)。指定範囲の要素のイテレータを出力する。

  • fn keys() -> Keys
    全要素のkeyのイテレータを出力する。

  • fn values() -> Values
    全要素のvalueイテレータを出力する。

ほかにもあるが割愛

感想

前回の実装ではRc<Refcell<T>>の多用による性能悪化、key, value型のトレイト境界が厳しいことやバグの存在などの課題がありました。
今回はRust標準ライブラリのBTree実装を参考にすることで上記の課題を解決するに至りました。
BTree系のデータ構造はFileSystem,やDBMSのインデックス技術への採用で有名ですが、今回B+Treeの実装を足掛かりに私も簡単なKVSをつくってみたいですね。

RustでB+Treeかいたよ

2021年2月24日4月18日追記
新しいほうがあります。
(見返すと大分筋が悪く思えてはずかしかったので再実装しました)
totechite.hatenablog.com










素の二分木とかAVL木かいたりと細々と継続していた、アルゴリズムとデータ構造の学習の延長です。こいつ木しか書いてねえな

totechite.hatenablog.com

totechite.hatenablog.com 今見返すとその記事の頃からBtreeやるやるとかいており、氏ぬまでに実装できてよかったと思う

はじめに

B+木については自分が解説するよりこちらの記事を読んでもらうほうがわかりやすいと思います
christina04.hatenablog.com

B木の変形にB*木やB+木と呼ばれるものがありますが、B+木の実装はあまり公開されていない様にみえた為今回B+木をを書いてみました。

実装した操作はinsert(挿入), find(探索), update(更新), delete(削除), print(出力)
deleteははりきって物理削除を採用した えらいね

グチャグチャに書いてしまったので気が向いたらコメントでも書いて整理したい

gistf4ea94b6095b31d4f62e71baa48135a1

結び

以前よりRDBMSの実装には興味があり、インデックスのデータ構造の一つであるB木にはかねてより関心があったので今回実装出来て楽しかった。今後自作RDBMSとか作るときに使うと思う。
とりあえず一通り動くところまではできたが、きっと余分な処理をしていたりコードが冗長になってしまっている為その解消と、諸々の最適化には手を付けられていないことを次の課題にしたい。

参考リンク

Builderscon2019:0831メモdump

hyperloglogは面白い

リアルタイムアクセス解析システム アクセスユーザ数 アクセスcookie

従来: ユニークユーザー数どう出すかが課題 全ての要素を覚えるひつよう(ユニークでなければいけない - O(N)必要 - abuse耐性がない

hyperloglogで解決: 確率的アルゴリズムで近似するアプローチ

cardinalityNを上位の連続したO-bitをつかう

marge scketchA + scketchB = A Bの和集合 →分散処理、並列化がやりやすい

Loglogに複数hashの平均化を加えたものがhyperloglog

Using on Redis: PFmargeが遅い(redisはシングルスレッドなのでhight traffic下で詰まる) のでPFmarge用のRedsインスタンスをつくるとよい

HyperMInHash:

まとめ: hyperloglog scketchは面白い 確率的アルゴリズムは面白い

質疑応答: HyperMinHashはRedisに入ってないのか? 入っていない。新しいデータ構造を定義しなければいけないので実装が大変

Hyperloglog++とは? Googleの再実装 論文 "Hyperloglog in practice"

Redisはソースコード読みやすい。 設計のドキュメントがしっかりしてる。

〇〇2vec再考

○○2vecをつかうことでふくざつで抽象的な情報を機械的に処理することができる

事例: 顔画像検索 ベクトル動詞の比較で「被写体の同一性」をはんていできる 画像を直接比較するのと比べて - 計算が高速 - 環境を吸収できる

グラフ構造を使ったhoge2vec

predictive Prefetching for the Web

JS bytes !== JPEG bytes 同サイズでもJSのパースのが高負荷

lazy-load

如何にしてjsのサイズを減らすか ファイルを分割する。異なるファイル同士の共通部分(importされたライブラリ等)をchuckする

Guess.js 機械学習によって次のページ遷移を予想してjsファイルをprefetchする

Chrome拡張つくってTwitterのUI変えた

最近TwitterのUIが変更された。

数日使ったものの未だ違和感がある。具体的には右手のカラム(トレンド表示されるとこ)が文字密度高くてごちゃごちゃっとなってるのが気になる。

はやく良くなってほしいがいつになるかわからんので、取り敢えずカラムを消すChrome拡張をつくった。

https://chrome.google.com/webstore/detail/hide-sidebar-column-on-tw/onpngcpnhobjhkdeijngpjbojondnlca

 

カラムのdomの読み込みを検知してからnode.remove()実行したい。
Reactの生domレンダリングはdomcontentloadedイベントでハンドルできないので、MutationObserverでReactのrootノードを監視するアプローチを取った。
ちなみにdomnodeinsertedというイベントでもハンドルできるけどdeplicatedなのでやめた

(function () {
const remove_column = (function () {
const elements = document.querySelector("div[data-testid="sidebarColumn"]");
if (elements !== null) {
elements.remove();
console.info('delete <div data-testid="sidebarColumn"></div>')
}
})
const observer = new MutationObserver(remove_column);
observer.observe(document.getElementById('react-root'), {
childList: true,
subtree: true
});
})()

やっつけ仕事なのもあり10行程度で済んだ。

 https://github.com/totechite/MinimarizeTwitterUI

国税庁法人番号公表サイトがよさげ

これです https://www.houjin-bangou.nta.go.jp

神社のデータを集めるのに役立った。
からしい住所データを大量にシュっと取得できてよい。

取れるデータは3種類あり、

このサイトでは、法人番号の指定を受けた者の
1.商号又は名称、
2.本店又は主たる事務所の所在地、
3.法人番号
(基本3情報) を公表しています。

とあって、法人施設の名称と住所のペアデータが欲しいときに丁度よさそう。

データの取得方法

以下の3つが提供されている

  1. トップページのフォームから検索
  2. 基本3情報ダウンロード|国税庁法人番号公表サイトからXMLまたはCSVデータのzipファイルをダウンロード
  3. 法人番号システム Web-API|国税庁法人番号公表サイトを叩く

少し説明すると、
まず1の方法はフォームに入力するだけなので簡単。2もダウンロードするだけなので簡単。

3がやや面倒で、まず初めに以下のフォームから利用申請する必要がある。
アプリケーションIDの発行届出フォーム|国税庁法人番号公表サイト
申請して数日待つと国税庁からAPIアクセスキーが記載された書類の封書が届くといった手続きとなっている。

国税庁法人番号管理室からの封書
こんなの

自分含め大抵の人は2の方法で事足りると思うけども、データファイルは月末更新とのことなので
最新の情報を参照する必要があればWebAPIの利用がよさそうに思う。
ちなみに申請フォームの利用用途の欄だけども自分の場合だと、「神道系宗教法人のデータがほしいです」みたいな一行作文を書いても通ったのでよほどいかがわしくなければ大丈夫じゃないかな

以上です。

おまけ

自分用にWebAPIのラッパー書いたので紹介します。 github.com これのセールスポイントですが、通常レスポンスデータはXMLCSVの二択ですがあらかじめJSONに変換して渡すのでユーザはXMLCSVのパースの必要がないとか、TypeScriptで型付けされてるのでIDEのコード補完が利いて楽できます。
よかったら使ってください。

神社の座標データセットを見つける

神社のデータを集めるために色々調べたメモ、リンク集。

「ポケGOみたいな位置情報つかったなんかつくりたい」とゆるふわな思い付きで始めたその名も寺社仏閣GOという開発テーマがあったが2週間ほどで飽いて無事プロジェクト凍結と相成った為なんらかの成果物を残そうとあがいて書いたのがモチベ。 これはその残骸で、GeoLocationAPIを利用して現在地近隣の神社をリストアップする奴です。 https://frosty-rosalind-b5f8c5.netlify.com/
供養します。

目次

  • よかった
    実際使った
  • よさそう
    役に立ちそうだが未検証、検証不十分

よかった

qiita.com オープンソースな地形データセットOpenStreetMapのデータベースにある名称や座標からなる神社のデータ数千件が一挙に手に入る。
座標の精度はそれなりに思えたが大体合ってるので取り敢えずインスタントに名称と座標の対のデータが欲しい自分には良い選択だった。
サンプルとして4月30日付のデータを載せる。 https://gist.github.com/totechite/b2c2c3063bcdb7e7418f248b0178bd6f?short_path=a99e0e4
41000行のjson(geojson)ファイルで、桁に迫力がある。

よさそう

developers.google.com GoogleMap関連のAPI。精度、網羅性ともに優秀にみえる。
1クエリに対する最大レスポンス件数が40件程度なので手元のDBで管理するデータ収集用途には向かなそう。(そもそもそれは利用規約的によいのか?)

newspat.csis.u-tokyo.ac.jp 住所を座標情報に変換できるライブラリ。Linuxで動作する。
神社庁とかの外部サービスから住所がわかればこれを利用して座標を求めることができて良さげ。C++の他にPHPPythonバインディングライブラリが存在する。

AVL木かいた

以前プレーンな二分探索木をかいたことがあって、今回もそんな感じ。
totechite.hatenablog.com

AVL構造体にinsert, search, deleteメソッドが生えてて、それぞれNode構造体の要素の挿入と探索と削除処理のインターフェースになるみたいな雰囲気。

なおこの実装にkeyはあるけれどデータを保存するvalueはない。
実際利用する上ではノードの値としてkeyとvalueがあるものだと思う。
しかし今回はAVL木の肝らしいノードの回転操作の学習が目的なのと、その回転操作においてvalueは注目されないため、シンプルさを優先してvalueを省略した。

ここで直ぐに試せる↓
https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=a3df7e708afdabc97c29765bd4de31d2

Rust-AVL木

回転操作について

rotate_l, rotate_r合わせて8か所もデータコピーしてしまい、もう少し抑えたかったお気持ち。

直線的な偏り?(left:2,right:0みたいなの)の修正が比較的かんたんで足掛かりになった。

他の人の実装みるとフラグで回転の発火を管理してるものがあった。
他人のコードは十人十色で読むの面白い

感想とか

再帰多用すると10分後には挙動忘れるのでちゃんとコメント書こうと反省した。
次こそBツリーやる

勉強になったサイト

AVL Tree by Java -- これで分かったAVL木