6

私は非常に大きい階層的に編成されたデータツリーを表すC++クラスを持っています（〜Gb、基本的にはメモリ内で逃げることができるのと同じ大きさです）。STLリストを使用して、各ノードの情報と他のノードへのイテレータを格納します。各ノードには親が1つだけありますが、0から10の子があります。抽象化すると、次のようになります。

struct node {
public:
    node_list_iterator parent;              // iterator to a single parent node
    double node_data_array[X];
    map<int,node_list_iterator> children;   // iterators to child nodes
};

class strategy {
private:
    list<node> tree;        // hierarchically linked list of nodes
    struct some_other_data;
public:
    void build();           // build the tree
    void save();            // save the tree from disk
    void load();            // load the tree from disk
    void use();             // use the tree
};

load（）とsave（）をディスクに実装したいのですが、かなり高速であるはずですが、明らかな問題は次のとおりです。

  1. サイズは事前にわかりません。

  2. データには、揮発性のイテレータが含まれています。

  3. 私のC++に対する無知は驚異的です。

誰かが純粋なC++ソリューションを提案できますか？

4

7 に答える 7

1

boost.serializationはソリューション、つまりIMHOであり、SQLite + Visitorパターンを使用してこれらのノードをロードおよび保存できますが、思ったほど簡単ではありません。

于 2010-04-26T15:02:33.990 に答える
1

boost.serializationライブラリを使用できます。これにより、イテレータも含めて、コンテナの状態全体が保存されます。

于 2010-04-26T14:58:36.717 に答える
1

次の構文でデータを保存できるようです。

File = Meta-data Node
Node = Node-data ChildCount NodeList
NodeList = sequence (int, Node)

つまり、シリアル化すると、ルートノードには直接（子）または間接（他の子孫）のすべてのノードが含まれます。フォーマットの記述はかなり簡単です。ルートノードから再帰的な書き込み関数を開始するだけです。

読むことはそれほど難しくありません。std::list<node>イテレータは安定しています。ルートノードを挿入すると、その子を挿入する場合でも、そのイテレータは変更されません。したがって、各ノードを読み取るときに、親イテレータをすでに設定できます。もちろん、これにより子イテレータが残りますが、それらは簡単です。各ノードはその親の子です。したがって、すべてのノードを読み取った後、子イテレータを修正します。2番目のノードである最初の子（最初のノードはルートでした）から開始し、最後の子まで繰り返します。次に、子Cごとに、その親と子をその親のコレクションに追加します。これは、読み取り中に子IDを脇に置く必要があることを意味しますが、これはint、単純なstd::vectorで実行できます。std::list<node>。それぞれの親のすべての子IDにパッチを適用したら、ベクターを破棄できます。

于 2010-04-26T15:12:51.847 に答える
1

ブーストシリアル化はすでに提案されており、それは確かに合理的な可能性です。

データをどのように使用するかによって大きく異なります。メモリ内でマルチウェイツリーを使用しているという事実は、必ずしもデータをマルチウェイツリーとしてディスクに保存する必要があるという意味ではありません。あなたは（明らかに）すでにメモリに保存できるものの限界を押し広げているので、明らかな問題は、必要なときに同じツリーを再構成できるようにデータをシリアル化することに興味があるのか​​、それとも何かが必要なのかということです。データベースのように、必要に応じて情報の一部をメモリにロードし、必要に応じてレコードを更新できます。

後者が必要な場合、選択の一部は、構造がどれだけ静的であるかにも依存します。たとえば、特定のノードにN個の子がある場合、その数は一定ですか、それとも変更される可能性がありますか？変更される可能性がある場合、子供の最大数に制限はありますか？

ディスク上の構造をトラバースできるようにしたい場合、1つの明らかな可能性は、それを書き出すときに、メモリで使用しているイテレータの代わりに、適切なデータのファイルオフセットを置き換えることです。

または、個々のノードのデータ（少なくともほとんど）が固定サイズであるように見えるため、固定サイズのレコードのデータベースのような構造を作成し、各レコードレコードに親/子のレコード番号を作成することもできます。 。

全体のサイズを事前に知ることは特に重要ではありません（事前に知っていたとしても、サイズをどのように使用するかは考えられません）。

于 2010-04-26T15:15:38.747 に答える
1

実際、最善の選択肢は、データ構造全体をデータベーステーブルに移動することだと思います。そうすれば、シリアル化の問題に対処したあなた（または私）よりもはるかに賢く人々の利益を得ることができます。また、構造がメモリに収まるかどうかを心配する必要がなくなります。

于 2010-04-26T16:12:57.367 に答える
0

私は以前にSOでこのような回答をしたことがあるので、要約します
。1 .データベースを使用します。
2.リンク（ポインター）の代わりにファイルオフセットを使用します。
3.データベースのように、ツリー構造なしでデータをレコードに保存します。
4. XMLを使用して、リンクの代わりにノード名を使用してツリー構造を作成します。5. SqLiteやMySQLのようなデータベースを使用した
場合、これは非常に簡単です。

「シリアル化」に多くの時間を費やし、プロジェクトの主な目的にあまり時間を費やさない場合は、データベースを使用する必要があります。

于 2010-04-26T16:55:19.143 に答える
-1

永続化のためにそれを行っている場合は、Webから使用できるいくつかのソリューションがあります。つまり、google "persist std :: list"です。または、mmapを使用して独自のソリューションをロールし、ファイルでバックアップされたメモリ領域を作成できます。

于 2020-07-28T20:40:33.680 に答える