Atree: シンプルで効率的なポインタレス Tree 実装

• C++ による Apter Trees
• ノード値と親インデックスの 2 つのベクタだけを使ってシンプルに表現したツリー
• ほとんどのツリーは二分木のように実装され、各ノードが自分の値と左/右の子ノードへのポインタを含む
• このようなデータ構造は再帰で実装する必要があり、キャッシュ挙動や頻繁な malloc() のために遅くなることがある
• どのツリーノードを誰が「所有」するのかという概念は、マルチレイヤーのソフトウェアでは複雑になりうる
• Apter ツリーははるかに高速で、推論しやすく、実装もしやすい

仕組み

• 同じサイズの 2 つの配列で実装する
  • データのベクタ（配列） d
  • 親インデックスのベクタ p。d ベクタのインデックスがキーとして使われる (c)
  • 多くの場合、キー/インデックス c は整数型
• Coco が Molly と Arca の親で、Arca に Cricket という子がいるなら、構造は次のようになる
  tree.d = ["Coco", "Molly", "Arca","Cricket"]
tree.p = [0,0,0,2]
• 親が 0 で、かつキーが 0 のノードがルートノード（Apter ツリーではルートノードが必須、または -1 が「親なし」を意味するが、ここでは無視する）
• コンピュータはベクタを非常に高速に操作できる。ポインタ演算よりはるかに速いため、アルゴリズムのビッグ O 記法を比較しても実際にはあまり意味がない

重要性

• この実装方式は、これまで見たツリー実装の中で最もエレガント
• 適切なベクタ演算ライブラリを使えば理解しやすく、バグも見つけやすい
• シンプルなので、ほかの利用シナリオにも簡単に適用できる
• 親インデックスベクタを無視して値を高速に反復でき、これは追加コストなしで使える Deep Map のようなもの
• GPU フレンドリーで、組み込み環境でも使いやすい
• ベクタのサイズが一定以上に増えないようにすることで、セキュリティを維持しやすい

起源

• この技術の発明者を探しているところで、60 年代から 70 年代のベクタ指向の時代にはすでに名前があったのではないかと推測している
• Apter が説明した形で初めて完全な説明を見たが、K3 でも広く文書化されていた
• APL は伝統的な方法でツリーを実装するが、ベクタグラフについては似た技術を使っている
• J ユーザーにも知られており、Rosetta Code には J 言語によるツリー実装の説明がある
• John Earnest はベクタツリー実装についてさらに詳しく説明しており、「オフセットインデックス」方式を含めて削除項目について解説している
• より複雑なアプローチとして、各項目の深さを追跡する方法もある

その他の一般的なツリー実装

• FreeBSD のカーネルツリー実装、klib のツリー、Ruby のツリークラス、Python の宣言的ツリークラスなどがある
• これらは Apter ツリーとまったく同じ機能を提供するわけではなく、一部は汎用化のためにはるかに大きい

このコードの現状

• C++17 を学ぶために、これを実装してみる試み
• まだ実運用の準備はできておらず、C++ についてさらに学ぶ必要がある

GN⁺の見解

• Apter Trees は既存の複雑なツリー構造を単純化し、高速で効率的なデータ管理を可能にする
• ベクタベースのツリー実装はメモリオーバーヘッドを最小限に抑え、線形アクセスによって性能を向上させられる
• この記事は、ソフトウェアエンジニアリングにおけるデータ構造への革新的なアプローチを探るうえで興味深い内容

[GN⁺]

Hacker Newsの意見

• あるユーザーは、自分の仕事がHacker Newsにリンクされているのを見て驚いたと述べている。彼は軽量な配列ベースのデータ構造に強い関心があり、特に3Dモデルのスキニング向けノードツリーでよく使われる実装方式に言及している。親ノードが子ノードより前に来るよう配列を並べ替えると、すべてのノードのワールド変換の再計算を単純なループで処理できると説明している。
• 別のユーザーは、この種のツリースタイルでは子ノードの反復が O(N) になるというコメントに対し、「最初の子」と「次の兄弟」を指すポインタを追加することで atree の設計を一般化するのは実際には簡単だと述べている。また、必要な処理を支援するためにデータ構造を変更することを勧めている。
• あるユーザーは、ノードを配列に格納し、インデックスをポインタとして使うことはツリーアルゴリズム実装に不可欠だと主張している。特にノードの子にアクセスする必要がある場合、メモリ節約のために内部ノードと葉ノードで別々の構造を検討すべきだと助言している。
• 別のユーザーは、親配列でツリーを表現する方式がHacker Newsで大きな関心を集めているのはやや奇妙だと述べている。これは、優れたプレゼンテーションが基本的なアイデアをどれほど先まで押し進められるかを示していると考えている。
• あるユーザーは、このプロジェクトはシステムポインタを独自のポインタに置き換えているだけだと指摘している。
• 別のユーザーは、malloc の回数を減らしデータ局所性を高めたいのであれば、ノードプールを使う従来型のツリー実装を試してみることを提案している。
• Aaron Hsu による APL を使った説明を参照することを勧めるコメントもある。
• あるユーザーは、ノードのすべての子をまとめてパックするよう構造を変更することを提案している。こうすれば二分探索でノードの子一覧全体を見つけられ、キャッシュフレンドリーな特性も得られると述べている。
• 配列内のインデックスを「ハンドル」または「インデックスハンドル」と呼ぶことに関するコメントもあり、このツリー表現はヒープや素集合データ構造のような古典的データ構造を思い起こさせると述べている。
• 最後に、配列インデックスも一種の「ポインタ」と言えるのであり、従来のツリー実装が malloc を必要とするのはノードを動的に追加・削除する必要があるためだと説明するコメントがある。ツリーのサイズに制限があり、削除も頻繁でないなら、配列実装が適している可能性があると述べている。