博士

ロボ子、今日はピアツーピアの共同編集アルゴリズムについて話すのじゃ！

ロボ子

共同編集、楽しそうですね！ どんなアルゴリズムなんですか？

博士

各文字に一意の識別子を割り当てるらしいぞ。`site`、`clock`、`parent`の3つ組での。

ロボ子

`site`は作成者の識別子、`clock`はサイト固有の整数、`parent`は前の文字へのポインタですね。なんだか難しそう...

博士

難しくないぞ！`parent`は挿入位置の直前の文字を指すのじゃ。もし先頭ならnull。

ロボ子

なるほど！文字の順序はどうやって決めるんですか？

博士

先行順巡回じゃ！親を子より前に配置するのじゃ。

ロボ子

同じ親を持つ文字の順序は？

博士

`counter`値を格納して、`counter`（降順）、`site`の順にソートするらしい。

ロボ子

削除はどうするんですか？

博士

削除セットにその文字の識別子を入れるだけ！「墓石」みたいなものじゃな。

ロボ子

なるほど！最適化もあるんですね。同じサイトからの連続した挿入は、メモリ内の単一のブロックにマージするんですか。

博士

そう！メモリブロックは、ドキュメント順にソートされた単一の配列に連続して格納するのじゃ。

ロボ子

削除セットは、範囲ベースの表現で効率的に表現するんですね。

博士

メモリ使用量は合理的で、パフォーマンスもO(log n)で実装できるのが利点じゃな。

ロボ子

でも、分割とマージのロジックが複雑で、実装が難しそうですね。それに、データを削除してもメタデータのサイズは縮小されないんですか。

博士

そう、そこが欠点じゃ。でも、参考資料もたくさんあるから大丈夫！

ロボ子

参考文献、ありがとうございます！

博士

しかし、このアルゴリズム、まるで私の部屋の片付けみたいじゃな。最初は整理されてるけど、どんどんゴミが増えていく…。

ロボ子

博士、それはちょっと違いますよ！