博士

ロボ子、今日はRDXについて話すのじゃ。あのエッシャーもびっくりなデータ構造らしいぞ！

ロボ子

エッシャーですか、あの錯視の？データ構造とどう関係があるんですか？

博士

RDXは、JSONみたいなドキュメント形式で、バイナリシリアライゼーションもできるし、LSMキーバリューストアでもあるらしいのじゃ。それに、ローカルファーストデータ同期システムで、Merkleグラフデータストアでもあるらしいぞ！

ロボ子

盛りだくさんですね。全部入りみたいな。

博士

そうそう。で、librdxっていう実装が、たったの20KLoCらしいのじゃ。パーサーコードを含めても、じゃぞ！

ロボ子

それはミニマルですね。どうやって実現してるんですか？

博士

JDRパーサーっていうのを開発して、JDRベースのテストフレームワークを作ったらしいのじゃ。RDXマージルールを体系的にテストしたとか。

ロボ子

マージルールですか。データの競合を解決する仕組みですね。

博士

そうそう。パーサーは、入力の正規化にマージと順序付けルールを使うらしいぞ。独自のeBNFルールのパーサーを生成するパーサージェネレーターも使ってるみたいじゃ。

ロボ子

柔軟性がありますね。

博士

RDXタプルは、集合をマップに変換したり、空のタプルをnullishな値にしたり、1つのタプルのタプルを削除されたデータのプレースホルダー（墓石）にしたりするらしいのじゃ。

ロボ子

墓石ですか。削除されたデータを覚えておくことで、整合性を保つんですね。

博士

N個の構造の場合、インタラクションの数は最適にはO(N^2)（ペアワイズ）、悲観的にはO(2^N)と推定されるらしいぞ。

ロボ子

相互作用の数が爆発的に増える可能性があるんですね。

博士

C++やRustよりもCを使う理由は、Cの方がNが小さいかららしいのじゃ。

ロボ子

え、どういうことですか？

博士

たぶん、Cの方がコードが短くて済むから、Nが小さくなるってことじゃないかの？

ロボ子

なるほど、そういう解釈もできますね。

博士

バッファ（4つのポインタ）はメモリを所有し、スライス（2つのポインタ）はメモリを所有しないというルールがあるらしいぞ。

ロボ子

メモリ管理の基本ですね。

博士

librdxは、$$u8cfeed1()みたいな代数的な関数命名規則を使ってるらしいのじゃ。

ロボ子

ちょっと読みにくいですね…。

博士

SKIPu8feed()などのスキップリストテンプレートでは、ブロックサイズが重要なパラメータらしいぞ。SKIPu8の場合、スキップログ（append-only skiplist）には、ブロックのサイズという重要なパラメータがあるらしいのじゃ。

ロボ子

スキップリストの性能に影響するんですね。

博士

経験豊富な開発者は、経験の浅い開発者が陥る状況を解決できるらしいぞ。

ロボ子

それはそうですね。経験は大切です。

博士

というわけで、RDXはなかなか面白いデータ構造みたいじゃな。ロボ子も、いつか作ってみると良いぞ！

ロボ子

はい、機会があればぜひ。

博士

そういえば、RDXって、まるで私の部屋みたいじゃな。色んなものが詰め込まれてるけど、一応整理されてる…つもり！

ロボ子

博士の部屋は、RDXよりもカオスな気がします…。