4

ポリモーフィック オブジェクト ツリーの多くのインスタンス間でデータを共有する必要がある状況にありますが、共有データを「ツリーごと」にする必要があるため、基本クラスで静的クラス メンバーを使用することは実際にはオプションではありません。 .

共有データへの余分なメンバー ポインターで各インスタンスに「過負荷」をかけたくないので、現在のアプローチ (ツリーを使用することを考慮) は、共有データをツリー ルート ノードのメンバーとして保持し、共有データへのアクセスごとに行うことです。 「ツリーグローバル」データがアクセスされる特定のノードの深さに応じて、間接的なチェーンを通過します。

共有データが非常に頻繁に (毎秒数百万... 少なくともそれが意図されている) アクセスされるシナリオがあるため、ルートノードに到達するための間接的なアクセスを回避するのに役立つ設計パターンがあるかどうか疑問に思います。オブジェクトのフットプリントに余分な膨張を導入しません。

共有データにアクセスするタイトなループなどのローカルとしてルート ノード ポインターを「キャッシュ」することは可能ですが、機能がツリー ノードに沿ってカスケードし、プロセス内でツリーを切り替えるシナリオも多数あるため、ルート ノード ポインターをキャッシュします。狭い文脈でのみ適用されます。

  • 静的メンバーの言及は、実装の範囲を C++ に限定するものではないことに注意してください。この時点で私はどんなアイデアにもオープンであるため、C タグも追加しました。
4

2 に答える 2

0

私が考えることができる可能性は次のとおりです。

  • ルートの数が限られている場合は、代わりにオフセットを (たとえば uint8_t に) ルートを持つ静的配列に格納します。たとえば、ルートが 5 ～ 10 個しかない場合、ノードごとになんと 64 ビットを格納する必要はありません。
  • 各「ツリー」を独自のプロセスで (OS レベルで) 実行しないのはなぜですか? このようにして、各ルートを静的データとして保存し、グローバルにアクセスできます。
  • ノードの数を制限できる場合は、特別なアロケータを使用できます。たとえば、0x0010000、0x0020000 など、特定のメモリ境界の先頭に最初にルートを割り当ててから、ルートのアドレスを取得します各ノードの単純な減算/ビットシフト? ただし、各ツリーのメモリ領域内にすべてのノードを割り当てることができるようにする必要があります。
于 2018-04-19T16:56:56.300 に答える
0

ツリー ノードと対話するすべてのメソッドは、最初のパラメーターとしてルートへのポインターを取ります。

flyweight ラッパー クラスは、この実装の詳細を隠すことができます。ここでは、実際のツリー ノード ポインターとルートへのポインターを含む不透明なクラスを介してツリー ノードにアクセスします。子供を要求すると、別のフライ級が返されます。

ツリーには追加のポインターがありませんが、インターフェイス クラスには追加のポインターがあります。

ツリー ノードが (論理的に) 不変である場合は、その状態をコピーして間接コストを削減することもできます。

template<class Data>
struct internal_tree {
  Data d;
  std::unique_ptr<internal_tree> left;
  std::unique_ptr<internal_tree> right;
};

template<class Data>
struct flyweight_tree {
private:
  internal_tree* internal = nullptr;
  internal_tree* root = internal;
  flyweight_tree(internal_tree* t, internal_tree* r):internal(t),root(r) {}
public:
  flyweight_tree() {}
  flyweight_tree(internal_tree* r):internal(r) {}
  flyweight_tree left() const { return { internal->left.get(), root }; }
  flyweight_tree right() const { return { internal->right.get(), root }; }
};

現在、実際のinternal_treeデータ構造にはルートへのポインターが格納されていません。それを使用するコードは、flyweight_treeルートへのポインタを格納する を介してアクセスしますが、そのルートへのポインタはアクセス ポイントにのみ格納され、長期間格納されることはありません。

が必要な場合は、 ( の代わりに) 親へのポインターの を格納するparentフライウェイトとして実装することもできます。これにより、ツリー ノードに別のメモリの山が保存されます (親へのポインターはありませんが、それを使用するすべての人が親を取得できます。これは、 を通じて使用するためです)。flyweight_treestd::vectorrootflyweight_tree

ほとんどの作業を に実装して、格納internal_treeする情報を引数として受け取るflyweight_treeか、ほとんどのツリー ロジックを に実装して、コンパクトな「長期保存」構造のflyweight_treeままにすることができます。internal_tree

于 2014-06-15T14:14:41.760 に答える